注意: 最新版のドキュメントをご覧ください。この第1版ドキュメントは古くなっており、最新情報が反映されていません。リンク先のドキュメントが現在の Rust の最新のドキュメントです。

スタックとヒープ

Rustはシステム言語なので、低水準の操作を行います。 もしあなたが高水準言語を使ってきたのであれば、システムプログラミングのいくつかの側面をよく知らないかもしれません。 一番重要なのは、スタックとヒープと関連してメモリがどのように機能するかということです。 もしC言語のような言語でスタックアロケーションをどのように使っているかをよく知っているのであれば、この章は復習になるでしょう。 そうでなければ、このより一般的な概念について、Rust流の焦点の絞り方ではありますが、学んでゆくことになるでしょう。

ほとんどの物事と同様に、それらについて学ぶにあたって、まず簡略化したモデルを使って始めましょう。 そうすることで、今は無関係な枝葉末節に足を取られることなく、基本を把握できます。 これから使う例示は100%正確ではありませんが、現時点で学ぼうとするレベルのための見本になっています。 ひとたび基本を飲み込めば、アロケータがどう実装されているかや仮想メモリなどの発展的なトピックを学ぶことによって、この特殊な抽象モデルが取り漏らしているものが明らかになるでしょう。

メモリ管理

これら2つの用語はメモリ管理についてのものです。スタックとヒープは、いつメモリをアロケート・デアロケートするのかを決定するのを助ける抽象化です。

大まかに比較してみましょう:

スタックはとても高速で、Rustにおいてデフォルトでメモリが確保される場所です。 しかし、このアロケーションはひとつの関数呼び出しに限られた局所的なもので、サイズに制限があります。 一方、ヒープはより遅く、プログラムによって明示的にアロケートされます。 しかし、事実上サイズに制限がなく、広域的にアクセス可能です。

スタック

次のRustプログラムについて話しましょう:

fn main() { let x = 42; } 
fn main() {
    let x = 42;
}

このプログラムは変数 x の束縛をひとつ含んでいます。 このメモリはどこかからアロケートされる必要があります。 Rustはデフォルトで「スタックアロケート」、すなわち基本的な値を「スタックに置く」ということをします。 それはどういう意味でしょうか。

関数が呼び出されたとき、関数中のローカル変数とそのほかの多少の情報のためにメモリがいくらかアロケートされます。 これを「スタックフレーム」と呼びますが、このチュートリアルにおいては、余分な情報は無視して、アロケートするローカル変数だけを考えることにします。 なので今回の場合は、 main() が実行されるとき、スタックフレームとして32ビット整数をただ1つアロケートすることになります。 これは、見ての通り自動的に取り扱われるので、特別なRustコードか何かを書く必要はありません。

関数が終了するとき、スタックフレームはデアロケートされます。これもアロケーションと同様自動的に行われます。

これが、この単純なプログラムにあるものすべてです。 ここで理解する鍵となるのは、スタックアロケーションはとても、とても高速だということです。 ローカル変数はすべて事前にわかっているので、メモリを一度に確保できます。 また、破棄するときも同様に、変数をすべて同時に破棄できるので、こちらもとても高速に済みます。

この話でよくないことは、単一の関数を超えて値が必要でも、その値を保持しつづけられないことです。 また、「スタック」が何を意味するのかについてまだ話していませんでした。 その点について見るために、もう少し複雑な例が必要です。

fn foo() { let y = 5; let z = 100; } fn main() { let x = 42; foo(); } 
fn foo() {
    let y = 5;
    let z = 100;
}

fn main() {
    let x = 42;

    foo();
}

このプログラムには変数が foo() に2つ、 main() に1つで、全部で3つあります。 前の例と同様に main() が呼び出されたときは1つの整数がスタックフレームとしてアロケートされます。 しかし、 foo() が呼び出されたときに何が起こるかを話す前に、まずメモリ上に何が置いてあるかを図示する必要があります。 オペレーティングシステムは、メモリをプログラムに対してとてもシンプルなものとして見せています。それは、0からコンピュータが搭載しているRAMの容量を表現する大きな数までのアドレスの巨大なリストです。 たとえば、もしあなたのコンピュータに1ギガバイトのRAMがのっていれば、アドレスは0から1,073,741,823になります。 この数値は、1ギガバイトのバイト数である230から来ています。1

このメモリは巨大な配列のようなものです。すなわち、アドレスは0から始まり、最後の番号まで続いています。そして、これが最初のスタックフレームの図です:

Address Name Value
0 x 42

この図から、 x はアドレス 0 に置かれ、その値は 42 だとわかります。

foo() が呼び出されると、新しいスタックフレームがアロケートされます:

Address Name Value
2 z 100
1 y 5
0 x 42

0 は最初のフレームに取られているので、 1 と 2 が foo() のスタックフレームのために使われます。 これは、関数呼び出しが行われるたびに上に伸びていきます。

ここで注意しなければならない重要なことがいくつかあります。 0, 1, 2 といった番号は単に解説するためのもので、コンピュータが実際に使うアドレス値とは関係がありません。 特に、連続したアドレスは、実際にはそれぞれ数バイトずつ隔てられていて、その間隔は格納されている値のサイズより大きいこともあります。

foo() が終了した後、そのフレームはデアロケートされます:

Address Name Value
0 x 42

そして main() の後には、残っている値も消えてなくなります。簡単ですね!

「スタック」という名は、積み重ねたディナープレート（a stack of dinner plates）のように働くことに由来します。 最初に置かれたプレートは、最後に取り去られるプレートです。 そのため、スタックはしばしば「last in, first out queues」（訳注: 最後に入ったものが最初に出るキュー、LIFOと略記される）と呼ばれ、最後にスタックに積んだ値は最初にスタックから取り出す値になります。

3段階の深さの例を見てみましょう:

fn bar() { let i = 6; } fn foo() { let a = 5; let b = 100; let c = 1; bar(); } fn main() { let x = 42; foo(); } 
fn bar() {
    let i = 6;
}

fn foo() {
    let a = 5;
    let b = 100;
    let c = 1;

    bar();
}

fn main() {
    let x = 42;

    foo();
}

いいですか、まず、 main() を呼び出します:

Address Name Value
0 x 42

次に、 main() は foo() を呼び出します:

Address Name Value
3 c 1
2 b 100
1 a 5
0 x 42

そして foo() は bar() を呼び出します:

Address Name Value
4 i 6
3 c 1
2 b 100
1 a 5
0 x 42

ふう、スタックが高く伸びましたね。

bar() が終了した後、そのフレームはデアロケートされて foo() と main() だけが残ります:

Address Name Value
3 c 1
2 b 100
1 a 5
0 x 42

そして foo() が終了すると main() だけが残ります:

Address Name Value
0 x 42

ついに、やりとげました。コツをつかみましたか? 皿を積み重ねるようなものです。 つまり、一番上に追加し、一番上から取るんです。

ヒープ

さて、このやり方は結構うまくいくのですが、すべてがこのようにいくわけではありません。 ときには、メモリを異なる関数間でやりとりしたり、1回の関数実行より長く保持する必要があります。 そのためには、ヒープを使います。

Rustでは、Box<T> 型を使うことで、メモリをヒープ上にアロケートできます。

fn main() { let x = Box::new(5); let y = 42; } 
fn main() {
    let x = Box::new(5);
    let y = 42;
}

main() が呼び出されたとき、メモリは次のようになります:

Address Name Value
1 y 42
0 x ??????

2つの変数のために、スタック上に領域がアロケートされます。 通常通り、 y は 42 になりますが、 x はどうなるのでしょうか? x は Box<i32> 型で、ボックスはヒープ上のメモリをアロケートします。 このボックスの実際の値は、「ヒープ」へのポインタを持ったストラクチャです。 関数の実行が開始され、 Box::new() が呼び出されると、ヒープ上のメモリがいくらかアロケートされ、そこに 5 が置かれます。 すると、メモリはこんな感じになります:

Address Name Value
(230) - 1 5
... ... ...
1 y 42
0 x → (230) - 1

今考えている1GBのRAMを備えた仮想のコンピュータには (230) - 1 のアドレスがあります。 また、スタックはゼロから伸びていますから、メモリをアロケートするのに一番楽なのは、反対側の端の場所です。 ですから、最初の値はメモリのうち番号が一番大きい場所に置かれます。 そして、 x にある構造体はヒープ上にアロケートした場所への生ポインタを持っているので、 x の値は、今求めた位置 (230) - 1 です。

ここまでの話では、メモリをアロケート・デアロケートするということのこの文脈における意味を過剰に語ることはありませんでした。 詳細を深く掘り下げるのはこのチュートリアルの目的範囲外なのですが、ここで重要なこととして指摘したいのは、ヒープは単にメモリの反対側から伸びるスタックなのではないということです。 後ほど例を見ていきますが、ヒープはアロケート・デアロケートをどの順番にしてもよく、その結果「穴」のある状態になります。 次の図は、とあるプログラムをしばらく実行していたときのメモリレイアウトです。

Address Name Value
(230) - 1 5
(230) - 2
(230) - 3
(230) - 4 42
... ... ...
3 y → (230) - 4
2 y 42
1 y 42
0 x → (230) - 1

この場合では、4つのものをヒープにアロケートしていますが、2つはすでにデアロケートされています。 アドレス (230) - 1 と (230) - 4 の間には、現在使われていない隙間があります。このような隙間がなぜ、どのように起きるかの詳細は、どのようなヒープ管理戦略を使っているかによります。 異なるブログラムには異なる「メモリアロケータ」というメモリを管理するライブラリを使うことができます。 Rustのプログラムはこの用途にjemallocを使います。

ともかく、私たちのプログラムの例に戻ります。 この（訳注: x のポインタが指す）メモリはヒープ上にあるので、ボックスをアロケートした関数よりも長い間生存しつづけることができます。 しかし、この例ではそうではありません。2 関数が終了したとき、 main() のためのスタックフレームを解放する必要があります。 しかし、Box<T>には隠れた仕掛け、Dropがあります。 DropトレイトのBoxへの実装は、ボックスが作られたときにアロケートされたメモリをデアロケートします。すばらしい! なので x が解放されるときには先にヒープ上にアロケートされたメモリを解放します。

Address Name Value
1 y 42
0 x ??????

その後スタックフレームが無くなることで、全てのメモリが解放されます。

引数と借用

ここまででスタックとヒープの基本的な例をいくつか学び進めましたが、関数の引数と借用についてはどうでしょうか? ここに小さなRustプログラムがあります:

fn foo(i: &i32) { let z = 42; } fn main() { let x = 5; let y = &x; foo(y); } 
fn foo(i: &i32) {
    let z = 42;
}

fn main() {
    let x = 5;
    let y = &x;

    foo(y);
}

処理が main() に入ると、メモリはこんな感じになります:

Address Name Value
1 y → 0
0 x 5

x は普通の 5 で、 y は x への参照です。そのため、 y の値は x のメモリ上の位置で、今回は 0 です。

引数として y を渡している関数 foo() の呼び出しはどうなるのでしょうか?

Address Name Value
3 z 42
2 i → 0
1 y → 0
0 x 5

スタックフレームは単にローカルな束縛のために使われるだけでなく、引数のためにも使われます。 なので、この例では、引数の i とローカル変数の束縛 z の両方が必要です。 i は引数 y のコピーです。 y の値は 0 ですから、 i の値も 0 になります。

これは、変数を借用してもどのメモリもデアロケートされることがないことのひとつの理由になっています。 つまり、参照の値はメモリ上の位置を示す単なるポインタです。 もしポインタが指しているメモリを取り去ってしまうと、ことが立ちゆかなくなってしまうでしょう。

複雑な例

それでは、次の複雑な例をステップ・バイ・ステップでやっていきましょう:

fn foo(x: &i32) { let y = 10; let z = &y; baz(z); bar(x, z); } fn bar(a: &i32, b: &i32) { let c = 5; let d = Box::new(5); let e = &d; baz(e); } fn baz(f: &i32) { let g = 100; } fn main() { let h = 3; let i = Box::new(20); let j = &h; foo(j); } 
fn foo(x: &i32) {
    let y = 10;
    let z = &y;

    baz(z);
    bar(x, z);
}

fn bar(a: &i32, b: &i32) {
    let c = 5;
    let d = Box::new(5);
    let e = &d;

    baz(e);
}

fn baz(f: &i32) {
    let g = 100;
}

fn main() {
    let h = 3;
    let i = Box::new(20);
    let j = &h;

    foo(j);
}

まず、main()を呼び出します:

Address Name Value
(230) - 1 20
... ... ...
2 j → 0
1 i → (230) - 1
0 h 3

j, i, h のためのメモリをアロケートします。 i が束縛されるボックスが確保する領域はヒープ上にあるので、 i はそこを指す値を持っています。

つぎに、 main() の最後で、 foo() が呼び出されます:

Address Name Value
(230) - 1 20
... ... ...
5 z → 4
4 y 10
3 x → 0
2 j → 0
1 i → (230) - 1
0 h 3

x, y, zのための空間が確保されます。 引数 x は、渡された j と同じ値を持ちます。 j は h を指しているので、値は 0 アドレスを指すポインタです。

つぎに、 foo() は baz() を呼び出し、 z を渡します:

Address Name Value
(230) - 1 20
... ... ...
7 g 100
6 f → 4
5 z → 4
4 y 10
3 x → 0
2 j → 0
1 i → (230) - 1
0 h 3

f と g のためにメモリを確保しました。 baz() はとても短いので、 baz() の実行が終わったときに、そのスタックフレームを取り除きます。

Address Name Value
(230) - 1 20
... ... ...
5 z → 4
4 y 10
3 x → 0
2 j → 0
1 i → (230) - 1
0 h 3

次に、 foo() は bar() を x と z を引数にして呼び出します:

Address Name Value
(230) - 1 20
(230) - 2 5
... ... ...
10 e → 9
9 d → (230) - 2
8 c 5
7 b → 4
6 a → 0
5 z → 4
4 y 10
3 x → 0
2 j → 0
1 i → (230) - 1
0 h 3

その結果、ヒープに値をもうひとつアロケートすることになるので、(230) - 1から1を引かなくてはなりません。 そうすることは、単に 1,073,741,822 と書くよりは簡単です。 いずれにせよ、いつものように変数を準備します。

bar() の最後で、 baz() を呼び出します:

Address Name Value
(230) - 1 20
(230) - 2 5
... ... ...
12 g 100
11 f → (230) - 2
10 e → 9
9 d → (230) - 2
8 c 5
7 b → 4
6 a → 0
5 z → 4
4 y 10
3 x → 0
2 j → 0
1 i → (230) - 1
0 h 3

こうして、一番深い所までやってきました! ふう! ここまで長い過程をたどってきて、お疲れ様でした。

baz() が終わったあとは、 f と g を取り除きます:

Address Name Value
(230) - 1 20
(230) - 2 5
... ... ...
10 e → 9
9 d → (230) - 2
8 c 5
7 b → 4
6 a → 0
5 z → 4
4 y 10
3 x → 0
2 j → 0
1 i → (230) - 1
0 h 3

次に、 bar() から戻ります。 ここで d は Box<T> 型なので、 d が指している (230) - 2 も一緒に解放されます。

Address Name Value
(230) - 1 20
... ... ...
5 z → 4
4 y 10
3 x → 0
2 j → 0
1 i → (230) - 1
0 h 3

その後、 foo() から戻ります:

Address Name Value
(230) - 1 20
... ... ...
2 j → 0
1 i → (230) - 1
0 h 3

そして最後に main() から戻るところで、残っているものを除去します。 i が Drop されるとき、ヒープの最後の残りも除去されます。

他の言語では何をしているのか?

ガベージコレクタを備えた多くの言語はデフォルトでヒープアロケートします。 つまり、すべての値がボックス化されています。 そうなっている理由がいくつかあるのですが、それはこのチュートリアルの範囲外です。 また、そのことが100%真であると言えなくなるような最適化もいくつか行われることがあります。 メモリの解放のためにスタックと Drop を頼りにするかわりに、ガベージコレクタがヒープを取り扱います。

どちらを使えばいいのか?

スタックのほうが速くて管理しやすいというのであれば、なぜヒープが要るのでしょうか? 大きな理由のひとつは、スタックアロケーションだけしかないということはストレージの再利用にLIFOセマンティクスをとるしかないということだからです。 ヒープアロケーションは厳密により普遍的で、ストレージを任意の順番でプールから取得したり、プールに返却することが許されているのですが、よりコストがかさみます。

一般的にはスタックアロケーションを選ぶべきで、そのためRustはデフォルトでスタックアロケートします。 スタックのLIFOモデルはより単純で、基本的なレベルに置かれています。 このことは、実行時の効率性と意味論に大きな影響を与えています。

実行時の効率性

スタックのメモリを管理するのは些細なことです: 機械は「スタックポインタ」と呼ばれる単一の値を増減するだけです。 ヒープのメモリを管理するのは些細なことではありません: ヒープアロケートされたメモリは任意の時点で解放され、またヒープアロケートされたそれぞれのブロックは任意のサイズになりうるので、一般的にメモリマネージャは再利用するメモリを特定するためにより多く働きます。

この事柄についてより詳しいことを知りたいのであれば、こちらの論文がよいイントロダクションになっています。

意味論への影響

スタックアロケーションはRustの言語自体へ影響を与えており、したがって開発者のメンタルモデルにも影響しています。 Rust言語がどのように自動メモリ管理を取り扱うかは、LIFOセマンティクスに従っています。 ヒープアロケートされユニークに所有されたボックスのデアロケーションさえも、スタックベースのLIFOセマンティクスに従っていることは、この章を通して論じてきたとおりです。 非LIFOセマンティクスの柔軟性（すなわち表現能力）は一般的に、いつメモリが解放されるべきなのかをコンパイラがコンパイル時に自動的に推論できなくなることを意味するので、デアロケーションを制御するために、ときに言語自体の外部に由来するかもしれない、動的なプロトコルに頼らなければなりません。（Rc<T> や Arc<T> が使っている参照カウントはその一例です。）

突き詰めれば、ヒープアロケーションによって増大した表現能力は（例えばガベージコレクタという形の）著しい実行時サポートか、（Rustコンパイラが提供していないような検証を必要とする明示的なメモリ管理呼び出しという形の）著しいプログラマの努力のいずれかのコストを引き起こすのです。

  1. 「ギガバイト」が指すものには、 109 と 230 の2つがありえます。国際単位系 SI では「ギガバイト」は 109 を、「ギビバイト」は 230 を指すと決めることで、この問題を解決しています。しかしながら、このような用語法を使う人はとても少なく、文脈で両者を区別しています。ここでは、その慣習に則っています。 ↩

  2. （「変数からのムーブアウト」とも呼ばれることもある）所有権の移動によって、メモリをより長い間生存させられます。 より複雑な例は後ほど解説します。 ↩