スタックとヒープ
Stack and Heap ・ スタックとヒープ
プログラムがメモリを使う2つの領域。呼び出しに合わせて積み崩れるスタックと、自由だが管理が要るヒープ。
✦ 30秒で試す — 航海関数はもう終わったのに、中で作ったデータが消えずに残るこの再帰は、最後まで動くか？予想してみる概要
スタックとヒープは、実行中のプログラム（プロセス）がデータを置くために使う2種類のメモリ領域です。スタックは関数の呼び出しに合わせて自動的に積まれ・片付けられる整然とした領域で、関数の引数やローカル変数、呼び出し元へ戻る場所（戻り先アドレス）が置かれます。ヒープは「必要なときに必要な大きさを確保し、要らなくなったら返す」自由な領域で、大きさが実行時まで分からないデータや、関数を抜けたあとも生き続けるデータが置かれます。
この使い分けは、ほとんどの言語でプログラマが意識しなくても動くように隠されています。しかし「なぜ再帰しすぎるとスタックオーバーフローで落ちるのか」「なぜメモリリークが起きるのか」「なぜガベージコレクションが必要なのか」といった疑問は、すべてこの2つの領域の性質の違いに答えがあります。
なお、ここでいうヒープは、優先度付きキューを実現するデータ構造の「ヒープ」（二分ヒープなど）とは名前が同じだけで、関係はありません。
なぜ生まれたか
初期のプログラミング言語（1950年代の FORTRAN など）では、変数の置き場所はコンパイルの時点で固定の番地に決め打ちされていました。単純で速い方式ですが、これでは関数の再帰呼び出しができません。同じ関数が同時に何段も実行中になると、1つしかない固定の置き場所を取り合ってしまうからです。1960年に定められた ALGOL 60 は再帰を認め、その実装として「関数を呼ぶたびに作業領域を積み、戻るときに降ろす」後入れ先出しの仕組み — コールスタック — が広まりました。関数呼び出しの入れ子の形と、スタックというデータ構造の性質がぴったり一致していたのです。
一方、スタックだけでは足りない場面もすぐに現れました。スタック上のデータは関数を抜けた瞬間に消えるので、「関数の中で作って、呼び出し元に返したあとも使い続けたいデータ」や「実行してみないと大きさが分からないデータ」を置けません。そこで、寿命も大きさも自由に決められる領域としてヒープが用意されました。同じころ LISP は、リストを実行中に次々と作っては捨てる言語として、ヒープと、使われなくなった領域を自動で回収するガベージコレクションを持ち込みました。自動で片付く規律の領域と、自由だが後始末が要る領域 — この分業が、以後ほぼすべての言語処理系の基本設計になっています。
詳細
スタックフレームの積み下ろし
関数が呼ばれるたびに、その関数専用の作業領域「スタックフレーム」がスタックの先端に積まれます。フレームには引数、ローカル変数、そして「戻ったらどこから実行を再開するか」を示す戻り先アドレスが入ります。関数が return すると、フレームはまるごと捨てられ、スタックの先端は呼び出し元のフレームに戻ります。確保も解放も「先端の位置を示すポインタを1つ動かすだけ」なので極めて速く、解放し忘れも原理的に起きません。
図のように、スタック上の変数からヒープ上のデータを「参照」（その箱の番地）で指すのが典型的な構図です。箱の本体はヒープにあり、スタックに載っているのは番地だけです。
値はどこに置かれるか — 言語による違い
「数値のような小さな値はスタック、オブジェクトはヒープ」と説明されることがありますが、これは一部の言語の、しかもローカル変数に限った話です。C や C++ では、関数の中で普通に宣言した変数はスタックに、malloc や new で確保したものはヒープに置かれ、どちらを使うかをプログラマが決めます。Java では、int などの基本型のローカル変数はフレームに置かれますが、オブジェクトの本体はヒープです（ただし実行時コンパイラが「このオブジェクトは関数の外に漏れない」と見抜けば、ヒープに置かずに済ませる最適化 — エスケープ解析 — をします）。Go もコンパイラがエスケープ解析で置き場所を決め、関数の外へ参照が逃げる値はヒープに移します。Python では整数も含めてすべての値がヒープ上のオブジェクトで、スタックのフレームには参照だけが並びます。
つまり、スタックかヒープかは「値の種類」ではなく「寿命と大きさが呼び出しの形に収まるかどうか」で決まり、その判断を誰がするか（プログラマか、コンパイラか、処理系か）が言語によって違う、と捉えるのが正確です。
下の部品では、いちばん上のフレームで「呼ぶ・new・return」を押してプログラムを動かし、参照の矢印を押して切ることができます。フレームが消えても参照された箱は残ること、どこからもたどれなくなった箱が灰色になり GC で回収されることを確かめてください。
- main()
いちばん上のフレーム（いまは main）の上にある 呼ぶ・new・return を押してプログラムを動かしてみてください。まず「呼ぶ」で関数を呼び、そこで「new」してから「return」します。
スタックの限界 — スタックオーバーフロー
スタックは速い代わりに大きさが限られています（OSやスレッドの設定によりますが、Linux のメインスレッドで既定 8MB ほど、ほかのスレッドではもっと小さいことが多い）。関数呼び出しが深くなりすぎる — 典型的には終了条件を誤った無限の再帰 — とフレームが積み上がって上限を超え、「スタックオーバーフロー」でプログラムは強制終了します。有名なQ&Aサイト Stack Overflow の名前の由来でもあります。再帰の深さがデータの大きさに比例するような処理（深い木をたどるなど）は、ループと自前のスタックに書き換えるのが安全です。
また、フレームは関数を抜ければ消えるので、ローカル変数への参照を外に持ち出すと、消えた領域を指す「ダングリングポインタ」になります。C言語で悪名高いバグの一つで、Rust の所有権と借用の仕組みはまさにこれをコンパイル時に禁止するためのものです。
ヒープの自由と代償 — リークと断片化
ヒープは寿命も大きさも自由ですが、その代償として管理のコストを払います。まず速度です。空き領域を探し、管理台帳を更新する必要があるので、確保と解放はスタックよりずっと遅くなります（メモリアロケータはこれを速くするための専用の工夫の塊です）。次に「解放し忘れ」の問題があります。使い終わったのに解放されないメモリが溜まり続けるのがメモリリークで、長時間動き続けるサーバのプロセスが少しずつメモリを食いつぶして倒れる古典的な障害の原因です。逆に、まだ使っているのに解放してしまえばダングリングポインタになります。さらに、大小さまざまな確保と解放を繰り返すと空き領域が細切れになる断片化が起き、合計では十分空いているのに大きな連続領域が取れない、という状態に陥ります。
「解放の責任を誰が持つか」という難問への現代的な答えがガベージコレクションです。スタックの変数などの「ルート」から参照をたどれなくなったヒープのデータを、処理系が自動で回収します。Java・Python・JavaScript などのプログラマがヒープをほとんど意識せずに済むのはこのおかげですが、GC による一時停止や、要らなくなった参照を配列やキャッシュに握ったままにすることによる「GC があってもリーク」は残ります。2つの領域の区別は、GC のある言語でも実務の教養です。
スレッドとの関係
もう一つ重要なのが、スレッドとの関係です。1つのプロセスの中で、ヒープは全スレッドに共有されますが、スタックはスレッドごとに1本ずつ別に持ちます。関数呼び出しの深さはスレッドごとに違うのだから当然の設計ですが、ここから並行処理の基本原則が導かれます。ローカル変数（スタック上）はそのスレッド専用なので取り合いにならない。一方で、ヒープ上の共有データへのアクセスはぶつかり得るので排他制御が要る — 「スレッドセーフかどうか」を考える出発点は、そのデータがどちらの領域にあり、誰から参照されているかです。
試問
左にスタック（関数を呼ぶたびに1段積まれるフレーム）、右にヒープ（new で作る箱の置き場）があります。いちばん上のフレームで「呼ぶ」「new」「return」を押してプログラムを動かし、矢印を押すと参照を切れます。フレームの変数 a は、そのフレームで new した箱を指し、return すると呼び出し元の変数 r に渡されます。
- main()
いちばん上のフレーム（いまは main）の上にある 呼ぶ・new・return を押してプログラムを動かしてみてください。まず「呼ぶ」で関数を呼び、そこで「new」してから「return」します。