Stack とは？関数呼び出しのためのメモリ

stack は、関数が呼び出されて return するにつれて伸び縮みするメモリ領域で、ローカル変数と管理情報を last-in, first-out の順序で格納します。

プログラムが関数を呼び出すたびに、その呼び出しのローカル変数、引数、そしてどこへ return するかを保持する「stack frame」を push します。関数が return すると、その frame は pop されます。この last-in, first-out の規律が stack を非常に高速にしますが、同時にサイズが固定でもあり、それが深い、あるいは暴走した再帰がオーバーフローを起こしうる理由です。

call stack の仕組み

関数呼び出しは frame を push し、return がそれを pop します。frame はローカル変数、パラメータ、return アドレスを保持します。確保はポインタを動かすだけなので、stack の操作はほぼ無料で、heap の確保よりはるかに安価です。

stack と heap

stack は寿命が短く関数スコープのデータを厳密な順序で格納し、return 時に自動的にクリーンアップされます。heap は寿命が長く動的なサイズのデータを格納し、手動または garbage collector によって管理されます。ほとんどのプログラムは両方を常に使います。

stack に何が乗るか

現在実行中の関数のローカル変数。
値渡しされた関数の引数。
呼び出し後に実行を再開できるようにする return アドレス。
保存されたレジスタと小さな管理情報。

なぜ stack は制限されるのか

stack は OS または runtime が定めた固定の最大サイズを持ちます。各呼び出しがその一部を消費し、frame は return 時にのみ解放されます。無制限の再帰は上限に達するまで frame を push し続け、stack overflow を引き起こします。

簡単な例

基底ケースなしに自分自身を呼ぶ関数は、呼び出しごとに新しい frame を push し、決して return しないため、stack はオーバーフローするまで増え、プログラムは stack overflow エラーで crash します。

CI における stack

stack overflow は通常ロジックのバグ（まずい再帰）を指すため、決定的であり retry しても役に立ちません。CI はそれらが最初に現れる場所であることが多いです。Latchkey のようなマネージドプラットフォームは、決定的な crash と一時的なインフラの失敗を区別し、後者だけを retry するため、本物のバグはきちんと表面化します。

重要なポイント

stack は関数呼び出しとローカルを last-in, first-out の順序で格納し、とても高速です。
サイズが固定なので、深いまたは無限の再帰はそれをオーバーフローさせます。
stack overflow は決定的なロジックのバグであり、retry すべき一時的な失敗ではありません。