これは、GLOBISアドベントカレンダー16日目の記事です。前回は、@chrojuさんのDocker build を GitHub Actions に最適化するという記事でした。
はじめに
弊社ではRuby内部実装を知ることを目的に、@_ko1さんがWEB+DB PRESSで連載されていた「Rubyのウラガワ ── Rubyインタプリタに学ぶデータ構造とアルゴリズム」の社内勉強会を開いています。
社内勉強会を通してガベージコレクション(以降、GCと呼ぶ)に興味を持ち、マークスイープGCを実装しました。
本記事は、RubyのベースGCアルゴリズムであるマークスイープGCについて紹介しようと思います。
前提知識
オブジェクト
アプリケーションによって確保されたデータ
生きているオブジェクト
アプリケーションから参照されているオブジェクト
死んでいるオブジェクト
アプリケーションから参照されなくなったオブジェクト
ヒープ
動的にオブジェクトを配置するためのメモリ領域
GCとは
GCの役割は、アプリケーションから参照されていないメモリを探索し再利用可能にすることです。
GCのないプログラミング言語では、プログラマーがメモリの管理を行う必要があります。C言語を触ったことのある人なら、mallocやfreeでメモリ確保や解放をしたことがあるのではないでしょうか。
メモリ解放を適切に行わなければ、メモリリークやダンブリングポインタを引き起すリスクがあります。計算機にメモリ管理を任せるGCによって、プログラマーはメモリ管理の複雑さから解放されます。
GCはメリットだけではありません。
GC中はアプリケーション処理を停止するため、GC発生した分だけ処理時間が長くなります。ロボットや車など一部のみ処理時間が大幅に伸びることを許容できない開発では困ってしまいます。
マークスイープGCについて
マークスイープGCは、生きているオブジェクトをマーキングするマークフェーズとマークしていないオブジェクトを回収し再利用可能にするスイープフェーズに分かれています。
オブジェクトのポインタを辿る起点となるルートから到達可能なオブジェクトを生きているオブジェクト。それ以外を死んでいるオブジェクトとして扱います。下の図では、A,B,C,Dが生きているオブジェクト。E,Fが死んでいるオブジェクトです。
グローバル変数、コールスタックやレジスタなどがルートになります。
マークスイープGCの実装
マークスイープGCを実装しました。
型ある言語を使ってみたいという理由からRubyではなく、Goで実装しています。
実装例を提示し、マークフェーズとスイープフェーズの詳細について説明します。
https://github.com/imaharu/mark_and_sweep_gc
実装の前提
- 実際のメモリに対するGCを実行しない。free処理は、ポインタ(Object.ptr)が空配列に書き換えることとします。
- 扱うオブジェクトはIntとArrayのみ。
- オブジェクト型がArrayの時、Object.ptrは要素のポインタ。オブジェクト型がIntの時、Object.ptrは数値。
マークフェーズ
マークフェーズは、ルートから辿れるオブジェクトのmarked fieldをtrueにします。
Arrayのようなオブジェクトが別オブジェクトを参照している場合は、再帰的にmarkを実行します。
type Object struct {
marked bool
object_type ObjectType // Int or Array
ptr []string // オブジェクト型がArrayの時、Object.ptrは要素のポインタ。オブジェクト型がIntの時、Object.ptrは数値。
size int
next_free_index int
}
type ObjectType string
var roots []int
func mark_phase() {
for i := range roots {
var heap_index = roots[i]
mark(&heap[heap_index])
}
}
func mark(o *Object) {
o.marked = true
if o.object_type == "Array" {
for i := range o.ptr {
index, _ := strconv.Atoi(o.ptr[i])
mark(&heap[index])
}
}
}
どのようにマークされていくのか図で示します。
ヒープ領域には、Intオブジェクトが4オブジェクト。Arrayオブジェクトが1オブジェクトあるとします。ルートから辿れるオブジェクトは、Arrayオブジェクトのみとします。
root = []int{1}
heap[0] = Object{marked: false, object_type: int_type, ptr: []string{"1111"}}
heap[1] = Object{marked: false, object_type: array_type, ptr: []string{"2", "3"}}
heap[2] = Object{marked: false, object_type: int_type, ptr: []string{"2222"}}
heap[3] = Object{marked: false, object_type: int_type, ptr: []string{"3333"}}
heap[4] = Object{marked: false, object_type: int_type, ptr: []string{"3333"}}
初回マークフェーズでは、オブジェクトが全てマークされていない状態から開始します。
マークフェーズは、ルートから辿れるオブジェクトに対してマークすることでした。ルートから辿れるのは、Arrayオブジェクトなのでマーキングされます。
マークされているオブジェクトから辿ることのできるオブジェクトもマークします。mark関数の再帰処理が該当処理です。
マークフェイスが終了すると以下のような状態になります。
heap[0]
=> Object{marked: false, object_type: int_type, ptr: []string{"1111"}}
heap[1]
=> Object{marked: true, object_type: array_type, ptr: []string{"2", "3"}}
heap[2]
=> Object{marked: true, object_type: int_type, ptr: []string{"2222"}}
heap[3]
=> Object{marked: true, object_type: int_type, ptr: []string{"3333"}}
heap[4]
=> Object{marked: false, object_type: int_type, ptr: []string{"4444"}}
スイープフェーズ
スイープフェーズは、ヒープの端から端までオブジェクトを総なめしmarkされていないオブジェクトを回収します。
また、再利用可能なオブジェクトを探すことができるように、free_listと呼ばれる片方向リンクリンスに連結します。新しいオブジェクトを生成する際は、free_listから利用可能なヒープ領域を探すことになります。
func sweep_phase() {
free_list = -1 # -1をNULLとする
for i := range heap {
if heap[i].marked == true {
heap[i].marked = false
} else {
free_obj(&heap[i])
heap[i].next_free_index = free_list
free_list = i
}
}
}
func free_obj(o *Object) {
o.ptr = []string{""}
}
スイープフェーズの開始時点で、freelistはNULLを指します。
最初のスイープ対象オブジェクトは、heap[0]です。heap[0].next_free_indexをfreelistは指してるポインタ、つまりNULLになります。freelistは、スイープしたオブジェクトのポインターになります。
スイープが終了した時の状態は、以下のようになります。
heap[0]
=> Object{marked: false, object_type: int_type, ptr: []string{""}}
heap[1]
=> Object{marked: false, object_type: array_type, ptr: []string{""}}
heap[2]
=> Object{marked: false, object_type: int_type, ptr: []string{"2222"}}
heap[3]
=> Object{marked: false, object_type: int_type, ptr: []string{"3333"}}
heap[4]
=> Object{marked: false, object_type: int_type, ptr: []string{""}}
まとめ
GCは、メモリの手動管理を計算機に任せることだ。
マークスイープGCは、GCアルゴリズムの一つ。
マークスイープGCは、マークフェーズとスイープフェーズに分かれている。
マークフェーズは、生きているオブジェクトをマーキングする
スイープフェーズは、マークしていないオブジェクトを回収し再利用可能にする。
GCに興味を持った人がいれば、「Rubyのウラガワ ── Rubyインタプリタに学ぶデータ構造とアルゴリズム」やRubyのgc.cを読んでみて下さい。