マークスイープガベージコレクションを実装してみた

これは、[GLOBISアドベントカレンダー](https://qiita.com/advent-calendar/2022/globis)16日目の記事です。前回は、@chrojuさんの[Docker build を GitHub Actions に最適化する](https://qiita.com/chroju/items/d98ea757f906a9b5d683)という記事でした。

# はじめに

弊社ではRuby内部実装を知ることを目的に、[@_ko1](https://twitter.com/_ko1)さんがWEB+DB PRESSで連載されていた「[Rubyのウラガワ ─⁠─ Rubyインタプリタに学ぶデータ構造とアルゴリズム](https://gihyo.jp/magazine/wdpress/archive/2019/vol110)」の社内勉強会を開いています。
社内勉強会を通してガベージコレクション(以降、GCと呼ぶ)に興味を持ち、マークスイープGCを実装しました。
本記事は、RubyのベースGCアルゴリズムであるマークスイープGCについて紹介しようと思います。

# 前提知識
## オブジェクト
アプリケーションによって確保されたデータ
## 生きているオブジェクト
アプリケーションから参照されているオブジェクト

## 死んでいるオブジェクト

アプリケーションから参照されなくなったオブジェクト

## ヒープ

動的にオブジェクトを配置するためのメモリ領域
![heap-ページ1 (8).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/69bf326e-0367-6967-2aaf-8c57e7489e02.png)

# GCとは

GCの役割は、アプリケーションから参照されていないメモリを探索し再利用可能にすることです。
GCのないプログラミング言語では、プログラマーがメモリの管理を行う必要があります。C言語を触ったことのある人なら、mallocやfreeでメモリ確保や解放をしたことがあるのではないでしょうか。

メモリ解放を適切に行わなければ、メモリリークやダンブリングポインタを引き起すリスクがあります。計算機にメモリ管理を任せるGCによって、プログラマーはメモリ管理の複雑さから解放されます。

GCはメリットだけではありません。
GC中はアプリケーション処理を停止するため、GC発生した分だけ処理時間が長くなります。ロボットや車など一部のみ処理時間が大幅に伸びることを許容できない開発では困ってしまいます。

# マークスイープGCについて

マークスイープGCは、生きているオブジェクトをマーキングするマークフェーズとマークしていないオブジェクトを回収し再利用可能にするスイープフェーズに分かれています。
オブジェクトのポインタを辿る起点となるルートから到達可能なオブジェクトを生きているオブジェクト。それ以外を死んでいるオブジェクトとして扱います。下の図では、A,B,C,Dが生きているオブジェクト。E,Fが死んでいるオブジェクトです。
グローバル変数、コールスタックやレジスタなどがルートになります。

![heap-ページ1 (7).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/9f98ff2e-74bd-4aa8-f339-211c6b98ee73.png)


# マークスイープGCの実装

マークスイープGCを実装しました。
型ある言語を使ってみたいという理由からRubyではなく、Goで実装しています。
実装例を提示し、マークフェーズとスイープフェーズの詳細について説明します。
[https://github.com/imaharu/mark_and_sweep_gc](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を実行します。

```go
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オブジェクトのみとします。

```go
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"}}
```

初回マークフェーズでは、オブジェクトが全てマークされていない状態から開始します。
![heap-ページ1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/6f45c0a5-4bbe-206d-1110-cd80d6e9d0e4.png)
マークフェーズは、ルートから辿れるオブジェクトに対してマークすることでした。ルートから辿れるのは、Arrayオブジェクトなのでマーキングされます。
![heap-ページ1 (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/2e0a66ba-f3ea-ea46-0c3c-83908da39281.png)
マークされているオブジェクトから辿ることのできるオブジェクトもマークします。mark関数の再帰処理が該当処理です。
![heap-ページ1 (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/d6f7df46-2e24-9f42-a6d4-f11bc12edb26.png)
マークフェイスが終了すると以下のような状態になります。

```go
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"}}
```
![heap-ページ1 (3).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/f4e7b380-172c-46ab-eeed-34697e9e76b1.png)
## スイープフェーズ

スイープフェーズは、ヒープの端から端までオブジェクトを総なめしmarkされていないオブジェクトを回収します。
また、再利用可能なオブジェクトを探すことができるように、free_listと呼ばれる片方向リンクリンスに連結します。新しいオブジェクトを生成する際は、free_listから利用可能なヒープ領域を探すことになります。

```go
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-ページ1 (4).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/6c99f40d-7fec-c6be-68f3-c393100682a5.png)
最初のスイープ対象オブジェクトは、heap[0]です。heap[0].next_free_indexをfreelistは指してるポインタ、つまりNULLになります。freelistは、スイープしたオブジェクトのポインターになります。
![heap-ページ1 (5).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/a25c4fd3-0740-5ee0-4026-de3da50dba49.png)
スイープが終了した時の状態は、以下のようになります。

```go
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{""}}
```

![heap-ページ1 (6).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2954609/f7557302-5b39-0b82-1899-8517b10ffdea.png)
# まとめ
GCは、メモリの手動管理を計算機に任せることだ。
マークスイープGCは、GCアルゴリズムの一つ。
マークスイープGCは、マークフェーズとスイープフェーズに分かれている。
マークフェーズは、生きているオブジェクトをマーキングする
スイープフェーズは、マークしていないオブジェクトを回収し再利用可能にする。

GCに興味を持った人がいれば、「[Rubyのウラガワ ─⁠─ Rubyインタプリタに学ぶデータ構造とアルゴリズム](https://gihyo.jp/magazine/wdpress/archive/2019/vol110)」やRubyの[gc.c](https://github.com/ruby/ruby/blob/v1_7_1/gc.c)を読んでみて下さい。

# 参考文献
- [Rubyソースコード完全解説 第5章 ガ－ベージコレクション](https://i.loveruby.net/ja/rhg/book/gc.html)
- [Rubyのしくみ -Ruby Under a Microscope](https://www.amazon.co.jp/dp/4274050653)
- [D言語 ガベージコレクション](https://dlang.org/spec/garbage.html)
- [D言語 ガベージコレクション日本語](http://www.kmonos.net/alang/d/garbage.html)
- [Javaパフォーマンス](https://www.amazon.co.jp/dp/4873117186)
- [ガベージコレクションのアルゴリズムと実装](https://tatsu-zine.com/books/gcbook)
- [一般教養としてのGarbage Collection](http://matsu-www.is.titech.ac.jp/~endo/gc/gc.pdf)