スタックとヒープ

概要

スタックとヒープは、実行中のプログラム（プロセス）がデータを置くために使う2種類のメモリ領域です。スタックは関数呼び出しに合わせて自動的に積まれ・片付けられる整然とした領域で、ローカル変数や戻り先アドレスが置かれます。ヒープは「必要なときに必要なサイズを確保し、要らなくなったら返す」自由な領域で、サイズが実行時まで分からないデータや、関数を抜けても生き続けるデータが置かれます。

この2つの使い分けは、ほとんどの言語でプログラマが直接意識しなくても動くように隠されています。しかし「なぜ再帰しすぎるとスタックオーバーフローで落ちるのか」「なぜメモリリークが起きるのか」「なぜガベージコレクションが必要なのか」といった疑問はすべて、この2領域の性質の違いに答えがあります。低レイヤから高レイヤまで、メモリにまつわる話題の土台になる区別です。

なぜ生まれたか

初期のプログラミングでは、変数の置き場所はコンパイル時に固定番地で決め打ちされていました。しかしこの方式では関数の再帰呼び出しができません。同じ関数が同時に複数回実行中になると、1つしかない固定の置き場所を取り合ってしまうからです。そこで「関数を呼ぶたびに作業領域を積み、戻るときに降ろす」後入れ先出しの仕組み — コールスタックが生まれました。関数呼び出しの入れ子構造とスタックというデータ構造の性質が完全に一致していたのです。

一方、スタックだけでは足りない場面もすぐに現れました。スタック上のデータは関数を抜けた瞬間に消えるため、「関数の中で作って、呼び出し元に返した後も使い続けたいデータ」や「実行してみないとサイズが分からないデータ」を置けません。そこで、寿命もサイズも自由に決められる領域として、明示的に確保・解放を行うヒープが用意されました。自動で片付く規律の領域と、自由だが自己管理が要る領域 — この分業が、以後ほぼすべての言語処理系の基本設計になっています。

詳細

スタックフレームの積み下ろし

関数が呼ばれるたびに、その関数専用の作業領域「スタックフレーム」がスタックの先端に積まれます。フレームには、引数、ローカル変数、そして「戻ったらどこから実行を再開するか」を示す戻り先アドレスが入ります。関数が return すると、フレームはまるごと破棄され、スタックの先端は呼び出し元のフレームに戻ります。確保も解放も「先端の位置を示すポインタを1つ動かすだけ」なので極めて高速で、解放漏れも原理的に起きません。

図のように、スタック上の変数からヒープ上のデータを「参照」で指すのが典型的な構図です。多くの言語では、数値のような小さな値はスタックに直接置かれ、オブジェクトや配列の本体はヒープに置かれて、スタックにはその参照だけが載ります。

このフレームの積み下ろしとヒープに残るデータの動きは、小さなプログラムを実際に1行ずつ実行してみると腑に落ちます。

1main():
2  name = "ほし"
3  msg = greet(name)
4  print(msg)
5 
6greet(name):
7  text = makeMessage(name)
8  return text
9 
10makeMessage(n):
11  s = new String("こんにちは、" + n)
12  return s
13 
14countdown(n):               # 暴走用
15  return countdown(n - 1)   # base case がない！

スタックの限界 — スタックオーバーフロー

スタックは高速な代わりにサイズが小さく固定です（OSやスレッド設定にもよりますが通常1〜8MB程度）。関数呼び出しが深くなりすぎる — 典型的には終了条件を誤った無限再帰 — とフレームが積み上がって上限を超え、「スタックオーバーフロー」でプログラムは強制終了します。有名なQ&AサイトStack Overflowの名前の由来でもあります。また、フレームは関数を抜ければ消えるため、ローカル変数への参照を外に持ち出すと消えた領域を指す「ダングリングポインタ」になります。C言語で悪名高いバグの一つで、Rustの所有権システムはまさにこれをコンパイル時に禁止するための仕組みです。

ヒープの自由と代償 — リークと断片化

ヒープは寿命もサイズも自由ですが、その代償として管理コストを払います。まず速度面では、空き領域の探索や管理台帳の更新が必要なため、確保・解放はスタックよりずっと遅くなります。次に「解放し忘れ」の問題があります。使い終わったのに解放されないメモリが溜まり続けるのがメモリリークで、長時間動くサーバプロセスが徐々にメモリを食いつぶして倒れる古典的な障害原因です。逆に、まだ使っているのに解放してしまえば前述のダングリングポインタになります。さらに、大小さまざまな確保と解放を繰り返すと空き領域が細切れに分断される断片化が起き、合計では空きが十分あるのに大きな連続領域が取れない、という状態に陥ります。

この「解放の責任を誰が持つか」という難問への現代的な回答がガベージコレクションです。どこからも参照されなくなったヒープ上のデータを処理系が自動で回収することで、リークとダングリングの大部分を言語レベルで防ぎます。JavaやPython、JavaScriptなどGC付き言語のプログラマがヒープをほぼ意識せずに済むのはこのおかげですが、GCの一時停止や、参照を握りっぱなしにすることによる「GCがあってもリーク」は残るため、2領域の区別は依然として実務の教養です。

スレッドとの関係

もう一つ重要な構図が、スレッドとの関係です。1つのプロセス内で、ヒープは全スレッドに共有されますが、スタックはスレッドごとに1本ずつ独立して持ちます。関数呼び出しの深さはスレッドごとに異なるのだから当然の設計ですが、ここから並行処理の基本原則が導かれます。ローカル変数（スタック上）はそのスレッド専有なので競合しない、一方でヒープ上の共有データへのアクセスは競合し得るため排他制御が要る — 「スレッドセーフかどうか」を考えるときの出発点は、そのデータがどちらの領域にあるかなのです。