メモリとスタックとヒープとプログラミング言語

2017-04-30

κeenです。今回の話は別にRustに限ったものではないのですが、よくRustを始めたばかりの人がスタックとヒープが分からないと言っているのをみかけるので少しメモリの話をしますね。厳密な話というよりは雰囲気を掴んで欲しいという感じです。

メモリは配列

プログラム（プロセス）のメモリには実行するプログラム（機械語）やグローバル変数/定数、関数の引数やローカル変数、その他プログラムで使うデータ領域などを置きます。プロセスに割り当てられるメモリというのは、1つの巨大なのっぺらな配列みたいなものです。サイズも決まってます。64bit OSなら2^64 byteです。

0                        2^64
+---------------     ----+
|  |  |  |  |    ~~   |  |
+---------------     ----+

これは仮想的なメモリなので実際の物理メモリに2^64 byteの配列がドンと確保される訳ではなくて、使った(使いたい)分だけ占有します。OSが賢いですね。

ただまあこれだけだと使いづらいのである程度区切って「この辺にこれ系のデータを置く」みたいな使われ方をします。プログラムを置く text領域 、初期化されたグローバル変数を置く data領域 、初期化されていない（データ領域だけ確保された）グローバル変数を置く bss領域 、関数の引数やローカル変数を置く stack領域 、プログラムのデータを置く heap領域 です。グローバル変数って言っちゃいましたけど実はそれに限らなくて、例えばRustの文字列リテラルなんかもdata領域に置かれます。

text、 data、 bssは実行する前からサイズが分かっているので問題ないのですが、heapとstackはプログラムの実行中にサイズが変わるものなのでどこにどう置いたら上手く配分できるか分かりませんね。そこで以下のようにstackとheapを両端に配置して使いたい分だけ使用領域を伸ばせるようになってます。

// 簡略化するために嘘ついてたりしますがまあ、だいたい合ってます
+-------+ 2^64
| stack |
|   |   |
|   V   |
|       |
|   ^   |
|   |   |
| heap  |
+-------+
| bss   |
+-------+
| data  |
+-------+
| text  |
+-------+ 0

text、data、bssはそのままなのでstackとヒープについて話します。

Stackと関数

Stackは関数呼び出しのために使われます。ネストした関数の呼び出しの系譜を関数の「コールスタック」と呼んだりするように、関数呼び出しはスタック構造になってますね。なのでスタックを用いて管理すると具合が良いのです。

+--------+
| func 1 |
+--------+
| func 2 |
+--------+
| func 3 |
+--------+
| func 4 |

さて、折角特別に用意したこのstackにはただの関数の呼び出し履歴だけではなく他のデータも入れたいですよね？例えば関数ローカルな変数だとか。データの次にまた別のデータが置かれるのでサイズを変えたりはできませんが。

+--------+
| func 1 |
|--------|
| data 1 |
|--------|
| data 2 |
+--------+
| func 2 |
|--------|
| data   |
| ...    |
+--------+
| func 3 |
|--------|
| data   |
| ...    |
+--------+
| func 4 |
|--------|
| data   |
| ...    |

データの解放は簡単です。スタックを巻き戻せば自動的に消えます。

+--------+
| func 1 |
|--------|
| data 1 |
|--------|
| data 2 |
+--------+
| func 2 |
|--------|
| data   |
| ...    |
+--------+
|        |
|        |
|        |
|        |
|        |
|        |
|        |

逆にいうと関数から抜けたら消えてしまうということでもありますが。

という訳で、「条件が限られるけど高速に扱えるデータ領域」がstackです。

因みに、メモリは使った分だけしか確保されないと言いましたが、スタックを伸ばしすぎると確保されていない領域に到達してエラーが出ます。スタックオーバーフローです。

Heapとデータ

heapにはstackに置けないデータが置かれます。これの扱いは少し面倒です。何故ならデータの確保や解放の順番がバラバラなので、歯抜けな状態になってしまうからです。

|        |
| data 4 |
+--------+
| data 3 |
+--------+
|        |
+--------+
| data 1 |
+--------+

そこで「どかが使われていてどこが空いているか」を管理するシステムを導入します。 C言語ではmallocという関数をインターフェースとして管理しているので管理システム自体もmallocと呼ぶことが多いようです。この実装方法はフリーリストを使った単純なものからサイズ毎のバケツを用意して〜といった方法まで様々にあるので気になる人は調べてみて下さい。大抵、「メモリがこのくらい欲しい」と言われたら今管理している中からそれっぽい空きを捜してそこを渡してあげるような作りになっています。

ちなみにこの領域管理には(mallocの場合)そこそこのコストが掛かります。でもその代わり自由に確保/解放できる他、サイズの変更もできるので自由度が高いです。

という訳で「自由度が高いが少しコストがかかるデータ領域」がheapです。

プログラミング言語とメモリ

では、具体的な言語がどのようにメモリを使っているかを簡単に紹介します。

1つ注意しないといけないのが、ガーベジコレクション（GC）のある言語ではheapの上に構築した自前のメモリ管理システムのことをヒープと呼んでいたりするので両者をちゃんと区別しましょう。同じく、スタックの使い方も言語独自でコールスタックと引数のスタックを分けたりもするので気をつけましょう。

C言語

先程説明したとおり、データ領域にheapを、関数呼び出しや関数ローカルなデータにstackを使っています。

メモリの領域管理は先述のmalloc, freeなどをプログラマが手で書きます。手で管理するのでバグります。

Ruby

データ領域にはheapにmallocで確保した領域にヒープを確保し、その上にメモリ管理システム(GC)を構築して管理しています。

関数呼び出しにはstackではなくheapに確保した自前のスタックを用意しています。 stackを使わないのはどうしてもC言語がstackを使うのでRubyも交ぜて使ってしまうと(Ruby自体C言語の上で動いていますね)問題が起こるだとかデータ構造として扱いづらいだとかGCとの兼ね合いだとかの理由だと思います。また、そもそもRubyのメソッドとC言語の関数は別物という話もあります。

また、実行用にスタックはありますが、データの実体はRubyのヒープに置かれます。Rubyのプログラムから高速なスタック領域を使うことができないのです。残念ですね。

メモリの領域管理にはGCシステムを採用し、メモリ管理をユーザがすることはありません。 GCはmallocに少しデータを足したようなMark and Sweepです。メモリ確保はほぼmallocと同じで、気が向いたときに使っているデータにマークを付けていって、マークの付いていないデータを一括でfreeしてくれます。メモリ確保（やポインタの扱い）がmallocに似ているのでC言語と協調するときに楽です。RubyはNative Extentionが作りやすいように設計されていますね。

1つ注意しておくと、Rubyを実行するときにもメモリにtextやbss、dataなどの領域がありますが、それは「Rubyを実行するVMのための領域」であって「実行しているRubyスクリプトのための領域」ではありません。

PythonやPHP

Rubyと同じようにヒープもスタックもheapに確保していると思います（面倒なのでソースを追っていない）。メモリ管理システムはGCを使いますが、Rubyとは違って参照カウント方式を採用しています。

参照カウントは、メモリ確保はmallocに似ていますが、確保した後の扱いが異なります。値を参照する度にカウントを増やし、使わなくなったら参照を減らし、参照が0になったらfreeされます。言語レベルでは意識するすることはありませんが、C言語のレイヤーでは一々参照の操作をしてあげないといけないので手間がかかります（たまに扱いを間違ってバグります）。また、循環参照という問題もあって、たまに解放されないメモリがあったりします。（そのために結局たまにMark and Sweepのようなものが必要だったりします）

Java

Rubyと同じようにヒープもスタックもheapに確保しています(JVMのメモリについて調べてみると色々出てきます)。 30億のデバイスで走らせるための工夫ですね。

同じくGCを使いますが、今度はCopy GC方式を採用しています（厳密にいうとHotSpot VMでの複数種類ある方式のうちの1つですが）。 Copy GCは面白くて、ヒープを2つに分割します。同時に使うのは1つだけです。メモリを確保するときは、使われていない領域などは無視して新たなスペースを確保します。これはわざわざ空き領域を捜す必要がないので非常に高速です。

+---------------------------------+
| data1 | data 2 | data 3 | ->    |
+---------------------------------+
+---------------------------------+
|                                 |
+---------------------------------+

そしてメモリが一杯になったら使っているデータだけもう1つの領域にコピーします。このとき、使っていなかった分は詰めます。

+---------------------------------+
|       | data 2 |                |
+---------------------------------+
+---------------------------------+
| data1 | data 3 | ->             |
+---------------------------------+

使っていなかったdata 2の存在を忘れて、2つを入れ替えたらメモリの回収完了です。

+---------------------------------+
| data1 | data 3 | ->             |
+---------------------------------+
+---------------------------------+
|                                 |
+---------------------------------+

ヒープが半分しか使えないだとかデータが移動してしまうので扱いが難しいだとかの問題はあるのですが、確保が非常に高速で解放もかなり速い方式です。

この方式はJavaの他にOCamlやHaskellなどの関数型言語でよく使われます。データを頻繁にアロケートするのでメモリ確保が高速なこの方式が好まれるようです。

Rust

RustはC言語と同じくデータ領域にheapを、関数呼び出しや関数ローカルなデータにstackを使っています。

メモリの領域管理はmalloc, freeなどをコンパイラが自動で発効してくれます。なのでプログラマが自分で管理する必要はありません。

高速なメモリの使い方

まず、一番速い方法は「そもそもメモリを確保しない」です。これはコストが掛からないので高速です。「何をふざけたことを」と思うかもしれませんが、プログラミングする上で「余計に確保しない」を意識するという意味で重要です。

次はstackを使うと高速です。これはそもそもstackを意識して使える言語でないと選べない方法ですね。

最後の手段としてheapを使います。

GCのある言語ではGCの特性によってヒープの使い方も考える必要があります。 Mark and Sweepは生死に関らず確保したオブジェクトの数に比例してメモリ解放コストが掛かりますが、Copy GCでは生きているオブジェクトに比例してコストが掛かりますので、生きているオブジェクトを減らすと速くなります。例えば使わないけど変数に束縛されているものがあるなら変数のスコープを狭めるだとか変数にnullを代入するだとか。よほどメモリのせいで遅くなっていない限りあまりやりませんが（ゲームの人はよくやるらしい？）。

また、最近の多くのGC（RubyもJavaも）には世代別GCといって、新しいデータと古いデータを分けて管理する方式が採用されているので作ったデータをすぐさま使ってすぐさま不要にすると速くなったりします。例えばデータ列に対して個々のデータに処理1、2、3を適用したいなら処理1のループ、2のループ、3のループ、とするよりもループの中で処理1、2、3と適用した方が速くなります。最近Scalaの次期コンパイラが高速化のためにそのような構成（phase fusioning）にしたらしいですね。使っている言語でOld領域、New領域などの単語を聞いたことがあるなら多分世代別GCが使われています。

まとめ

スタックとヒープの話、そしてなぜスタックとヒープを意識したいかを説明しました。ついでに、比較のためにGCのある言語についても少しだけ紹介しました。けっこうふわふわとした説明なので「分かった気分」になりたいだけならこの記事で十分かと思いますが、もう少し踏み込んだことが知りたければ個別に調べてみて下さい。また、メモリレイアウトについてはおおまかには合っているものの、結構嘘ついているのであまり鵜呑みにしないで下さい。

参考

仮想メモリ空間のメモリマップを調べる - th0x4c 備忘録。
malloc(3)のメモリ管理構造 | VA Linux Systems Japan株式会社。
rubyのメモリ確保にmallocを使っている部分。
rubyのスタックの定義部分。これは引数スタックかな？コールスタックどこだろう…