本稿では, ガベージコレクションのアルゴリズムの一つであるmark & sweep法のアルゴリズムを解説します.
初めに
ヒープ領域のメモリ管理を自動的に行うソフトウェアであるガベージコレクション(ガベコレ)はpythonやGo, Javaなど, 多くのプログラミング言語で採用されています.
ガベコレと聞くと難しそうという印象を覚えがちですが, 今回紹介するガベコレのアルゴリズムの一種であるmark & sweep法の考え方は非常にシンプルです.
実際, Rustで簡単なガベコレを実装したところ, 100行程度で書くことができました. (実装例: https://github.com/speed1313/gomicollector)
本稿では, mark & sweep法のアルゴリズムをみていきます!
背景
初めに, ガベコレがなぜ必要になるかを知っておきましょう.
プログラムを実行する際には, メモリが必要になります.
プログラム実行時, プログラムが使うことのできるメモリ領域は基本的に以下のような構成になっています.
| テキスト領域 |
|---|
| データ領域 |
| ヒープ領域 |
| ↓ |
| ↑ |
| スタック領域 |
注目すべき点は, ヒープ領域とスタック領域です. スタック領域とヒープ領域は実行時に動的に伸びたり縮んだりします.
スタック領域とヒープ領域を使い分けることで, メモリを効率的に使うことができます.
スタック領域
現代のプログラムは, 基本的にスタックマシンという, スタックを用いて計算を行う計算モデルに従って動作します.
例えばスタックマシンで5+3を計算する場合, 以下のようにスタックに引数(5, 3)をpushし, その後スタックの上から引数をpopしてそれらを用いて加算演算をして, 計算結果をpushするという処理をします.
| + | |||
| 3 | |||
| 5 | 5 | 8 | |
| ・ | ・ | ・ | ・ |
| ・ | ・ | ・ | ・ |
| ・ | ・ | ・ | ・ |
| スタックの底 | スタックの底 | スタックの底 | スタックの底 |
時間→
このようにスタックを用いることで, (5+3)(32)といった加減乗除が組み合わさった式や, 論理演算などが可能になります.
関数や再帰, ifなどもスタックマシンによって行うことができます.
このように, 基本的にプログラムの実行はスタックマシンのモデルに従って行われています.
プログラムの動作のより詳細な仕組みについてはOSやコンパイラ等の本を参照ください (参考: 辻野, コンパイラ, Rui Ueyama, 低レイヤを知りたい人のためのCコンパイラ作成入門).
ヒープ領域
前節でスタック領域が必要なことを述べました. では, ヒープ領域はなぜ必要なのでしょうか.
それは, プログラムにおいて動的にメモリを確保したいことがあるからです. そしてそれはコンパイル時に割り付け順序やサイズが決まっているスタック領域ではできません.
スタック領域に割り当てられるメモリの制約として, メモリ領域の確保及び解放のタイミングはスタックのpushとpopの時であり, メモリのサイズも静的に決まっている必要があります.
それに対し, ヒープ領域を用いる場合, メモリの確保及び解放のタイミングやサイズはピープ領域の範囲内において自由です.
例えば動的にサイズが決まる木は, ヒープ領域にメモリを確保する必要があります.
このように便利なヒープ領域ですが, ハープ領域のメモリを使用する際には, メモリの確保と解放を正しく行う必要があります.
例えば以下のようなことを守らなければなりません.
- 不要になったメモリは忘れずに解放する → ヒープ領域は有限であるため解放しないとメモリがオーバーフローする
- 解放されたメモリを指すポインタは使用できない → 意図しない値を得る, または書き込んでしまう原因になる
- メモリは二重に解放しない → 別に割り当てられたメモリを勝手に解放してしまう可能性がある
このようなことを守らないと, 想定と異なる挙動をしてしまいます.
ピープ領域のメモリの解放は非常に厄介で, 歴史的に長い間プログラマを悩ませてきました. 実際, バグの多くがメモリに起因すると言われます.
莫大な行数の複雑なプログラムにおいて, どこでメモリを確保して, どこでメモリを解放すべきか正確に把握するのは難しいのです.
このような問題に対して, ガベコレは自動でメモリの確保・解放を行ってくれます.
ガベコレによりプログラマはメモリ管理に頭を悩ませる必要がなくなったのです. (ガベコレでもオーバーヘッドによる速度低下などの問題はあります. 情報科学ではトレードオフが至る所で存在します.)
アルゴリズム
ガベコレを実現するためのアルゴリズムは現在に至るまでに数多く発明されてきました.
代表例に参照カウント法とmark & sweep法があります.
参照カウント法
オブジェクトを参照するポインタの数を数え、参照するポインタの数がゼロになったら解放する方法。循環参照の問題がある。解放が集中したときに、単純な実装だと停止時間が長くなる。 (https://ja.wikipedia.org/wiki/ガベージコレクションより引用)
mark & sweep法
オブジェクトから別のオブジェクトへの参照をたどり、到達できないオブジェクトを破棄する方法。(https://ja.wikipedia.org/wiki/ガベージコレクションより引用)
ここではmark & sweep法について具体例を添えて解説します.
mark & sweep法
mark & sweep法は, ヒープ領域のオブジェクトのうち, ルートからオブジェクトを再帰的にたどり, その過程でmarkをつけ, 再帰が終了した時点でmarkがついていないものは不要とみなして破棄および回収するというものです.
アルゴリズムは以下の流れで行われます.
- ヒープ領域のうち現在使用できる領域のindexを保存するリスト(free_list)を見る. リストにindexが存在していればその中から一つpopしてメモリを割り当てる. なければ以下を行いゴミを回収して再利用する.
- 初期化: ヒープ領域のオブジェクトを全てmarked=falseにする.
- markフェーズ: rootからオブジェクトを再帰的にたどっていき, 辿る過程でmarked=trueにしていく
- sweepフェーズ: ヒープ領域の先頭からオブジェクトを見ていき, marked=falseのindexをfree_listに登録
- free_listからindexを一つpopして返す. なければ割り当てられる領域はないためエラーを返す.
今回提示したアルゴリズムはmark & sweep法の実装の一例にすぎません. 実際, ピープ領域は伸びるにも関わらず固定長のvectorのようにしています.
一概にmark & sweep法といってもやり方はいろいろあります. ただどれも本質となるロジックは共通しています.
具体例
以下のように5つの領域が存在するヒープ領域があるとしましょう.
以下のテーブルは固定長ですが, これを生のメモリを指すindexテーブルと解釈すれば実際のメモリは可変長にできます. または固定長のメモリ領域しか割り当てられないとしても良いです.
| root | |||
|---|---|---|---|
| index | marked: bool | object名 | points to |
| 0 | |||
| 1 | |||
| 2 | |||
| 3 |
最初はヒープ領域が使用されていないため, Noneで初期化されています(Noneは省略).
rootはガベコレ時にマークをつける際のスタート地点であり, スタック領域にある変数です. C言語であればピープ領域を指すポインタに当たります.
rootはC言語のポインタがいくらでも定義できるようにいくつあっても良いのですが, 今回は簡単のため一つにします.
mark時に探索する最初のポイントの集合をroot_setと呼びます.
root_setのデータの持ち方として, 例えばプログラムのネストに応じてハッシュマップのスタックにピープを指すポインタ変数をinsertし, ネストから抜けた時にpopしていくことが考えられます.
このようにすることで, ネストから抜けた際にポインタも同時に解放されることを表現できます.
解放されたポインタがさすメモリは, 他にそれを指すポインタが存在しなければマークフェーズで辿れず探索されないためゴミとして回収されることになります.
ただハッシュマップもピープ領域に格納されるデータ構造であるため, この方法だと鶏と卵のようなことになってしまいそうです.
ヒープ領域を使わない別のデータ構造を用いるなどの方法があるかと思います. より深い考察は専門書に譲ります.
rootが指すオブジェクトは現在使用されている領域であり, ガベコレにおいて回収されません.
ヒープ領域のうち使用できるindexが保存されたfree_listも用意しておきます. はじめは使用できる領域がわからないため空になっています.
free_list: []この状態で, 以下のようにobj1のメモリが確保されました.
obj1_id = gc.allocate()すると, gcはfree_listに空き領域がないかチェックします.
free_list: []今回はfree_listが空なので, heap領域からゴミを回収するフェーズに入ります.
まずは全てmarked=falseにします.
| root | |||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | ||
| 1 | false | ||
| 2 | false | ||
| 3 | false |
続いてmark処理を行います.
mark処理では現在使用中のオブジェクトを全て見つけてmarkして行きます.
rootから再帰的に辿っていくのですが, 今回rootが指しているindexは存在しないため, mark処理は１つもオブジェクトを見つけず終了です.
続いてsweep処理を行います.
sweep処理ではピープ領域のうち未到達つまり不要な領域を回収してfree_listに保存します.
今回はindexを0から辿り, どれもmarked=falseなので
free_list: [0, 1, 2, 3]となります.
最後にfree_listの後ろから一つindexをpopします.
今回はobj1に3を割り当てられます.
| root | |||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | ||
| 1 | false | ||
| 2 | false | ||
| 3 | false | obj1 |
これでobj1にメモリが割り当てられました.
ただ残念ながら今のところobj1は誰からもポイントされていません. このままではメモリがいっぱいになったら回収されるでしょうから覚えておいてください.
続いてこの状態で
obj2_id = gc.allocate()をすると, free_listに以下のようにまだ空きがあるので
free_list: [0, 1, 2]ゴミの回収は行わずobj2に2が割り当てられます.
その結果ヒープは以下のようになります.
| root | |||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | ||
| 1 | false | ||
| 2 | false | obj2 | |
| 3 | false | obj1 |
allocate()をさらに二回繰り返すと, 以下のようにheap領域が全て割り当てられた状態になります.
| root | |||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | obj4 | |
| 1 | false | obj3 | |
| 2 | false | obj2 | |
| 3 | false | obj1 |
free_list: []この状態でallocate()すると, 現在free_listが空になっているためメモリを回収する必要があり, ガベコレはmark & sweep法に従って, ゴミを回収します.
またしてもrootは何も指していないためmark()後にmarkedはどれもfalseになり, スイープ後のfree_listは
free_list: [0, 1, 2, 3]になります.
これはすなわち, obj1, … , obj4といった誰からもポイントされていない到達不可能なオブジェクトは不要であるためガベコレにより自動的に解放されるということを意味します.
その後free_listからindexがポップされobj5には3番目の領域が割り当てられます.
| root | |||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | ||
| 1 | false | ||
| 2 | false | ||
| 3 | false | obj5 |
確かにガベコレが不要な領域を回収して新たにメモリを割り付けていますね.
では次にobj5を割り当てる直前の状態に戻りましょう. 以下のヒープ領域が全て割り当てられた状態です.
| root | |||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | obj4 | |
| 1 | false | obj3 | |
| 2 | false | obj2 | |
| 3 | false | obj1 |
この状態で,
root = *heap[obj1_id]とrootがobj1を指してみることにします.
| root | obj1 | ||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | obj4 | |
| 1 | false | obj3 | |
| 2 | false | obj2 | |
| 3 | false | obj1 |
この状態でobj5にallocate()をすると, mark()終了時点で以下のようになります.
| root | obj1 | ||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | obj4 | |
| 1 | false | obj3 | |
| 2 | false | obj2 | |
| 3 | true | obj1 |
root→obj1
となっているため, mark(root)を呼ぶと, obj1だけmarked=trueされるのです.
そのため, sweep()後にはfree_listは以下のようになります.
free_list: [0, 1, 2]これは, 到達可能なオブジェクトは回収しないことを意味します.
ガベコレはまだ到達可能, 即ち必要なものを回収しないのです.
そしてobj5割り付け後ヒープ領域およびfree_listは以下のような構成になっています.
| root | obj1 | ||
|---|---|---|---|
| index | marked | object名 | points to |
| 0 | false | ||
| 1 | false | ||
| 2 | false | obj5 | |
| 3 | true | obj1 |
free_list: [0, 1]以上の例から, ガベコレは到達可能なオブジェクトと到達不可能なオブジェクトをmarked=true, falseで判断し, ゴミを回収してヒープ領域を最大限使用できるようにしていることがわかりました.
今回はヒープの構造をベクターに置き換えるなどかなり単純化しています.
実際のallocationの仕方については以下の動画等を参照ください.
以下の動画ではmalloc()の内部動作を非常に丁寧に説明されている動画です.
The 67th Yokohama kernel reading party
まとめ
本稿ではガベージコレクションの代表的なアルゴリズムであるmark & sweep法を解説しました.
名前だけ聞くと難しそうなガベコレですが, mark & sweep法は
オブジェクトをたどりながら到達できるものにmarkをつけ, markされていないものは不要と判断してメモリ解放する
という単純なアルゴリズムであることがわかりました.
より詳細な仕組みについては, mark & sweep GCをRustで100行程度で実装してみたので読んでみてください. よければStarもお願いします🤲
今回紹介したものはガベコレの触りです.
実用的なものにするためには, ゴミ回収のタイミングを工夫したり, ヒープ領域のコンパクションをしたり, 並行処理化したりなど, より複雑なトピックがたくさんあります(私は主なトピックの名前以外まだ何も知りません).
ぜひdeep diveしてみてください.