『ガベージコレクションのアルゴリズムと実装』

https://gyazo.com/f7e2375e58e0bacfb9b4251537176046

著者

2013-12-24出版

監修者まえがき

本書のレビューを終えて

序章

はじめに

GCとは

ゴミのリサイクル

GCが行う2つのこと

GCの恩恵

GCのない世界

GCのある世界

GCの歴史

GCは古い技術

マークスイープGC

参照カウント

コピーGC

GCの根本は50年前から変わっていない

夢の4つ目のアルゴリズム

なぜ今GCなのか

当たり前にあるGC

さまざまな処理系実装

メモリの使い方を意識する

枯れない技術

そんなことより、GCは面白い

読者対象

本書の表記

図中の矢印

擬似コード

命名規則

空ポインタ・真偽値

関数

インデント

ポインタ

フィールド

forループ

スタックとキュー

特殊な関数

謝辞

筆者二人からの謝辞

中村成洋からの謝辞

相川光からの謝辞

第1部 アルゴリズム編

第1章　GCを学ぶ前に

1.1　オブジェクト/ヘッダ/フィールド

1.1.1　ヘッダ

1.1.2　フィールド

1.2　ポインタ

1.3　ミューテータ

1.4　ヒープ領域

1.5　生きている/死んでいるオブジェクト

1.6　アロケーション

1.7　チャンク

1.8　ルート

1.9　評価項目

1.9.1　スループット

1.9.2　最大停止時間

1.9.3　ヒープ領域の使用効率

1.9.4　参照の局所性

第3章　参照カウント（Reference Counting）

3.1　参照カウントのアルゴリズム

3.1.1　カウンタの値の増減

3.1.2　new_obj()関数

3.1.3　update_ptr()関数

3.2　メリット

3.2.1　ゴミがすぐに回収できる

3.2.2　ミューテータの最大停止時間が短い

3.2.3　ポインタをたどる必要がない

3.3　デメリット

3.3.1　カウンタの値の増減処理が重い

3.3.2　カウンタに多くのビットが必要

3.3.3　実装が煩雑

3.3.4　循環参照が回収できない

3.4　遅延参照カウント法(Deferred Reference Counting)

3.4.1　遅延参照カウントとは

3.4.2　dec_ref_cnt()関数

3.4.3　new_obj()関数

3.4.4　scan_zct()関数

3.4.5　メリット

3.4.6　デメリット

3.5　Sticky参照カウント法

3.5.1　Sticky参照カウント法とは

3.5.2　何もしない

3.5.3　マークスイープGCを利用して管理

3.6　1ビット参照カウント(1bit Reference Counting)

3.6.1　1ビット参照カウントとは

3.6.2　copy_ptr()関数

3.6.3　delete_ptr()関数

3.6.4　メリット

3.6.5　デメリット

3.7　部分マークスイープ法(Partial Mark & Sweep)

3.7.1　部分マークスイープ法とは

3.7.2　前提

3.7.3　dec_ref_cnt()関数

3.7.4　new_obj()関数

3.7.5　scan_hatch_queue()関数

3.7.6　paint_gray()関数

3.7.7　scan_gray()関数

3.7.8　collect_white()関数

3.7.9　探索対象の限定

3.7.10　paint_gray()関数の重要なポイント

3.7.11　部分マークスイープ法の限界

第4章　コピーGC(Copying GC)

4.1　コピーGCとは

4.1.1　copy()関数

4.1.2　new_obj()関数

4.1.3　実行過程

4.2　メリット

4.2.1　優れたスループット

4.2.2　高速なアロケーション

4.2.3　フラグメンテーションが生じない

4.2.4　キャッシュメモリとの相性が良い

4.3　デメリット

4.3.1　ヒープ領域の使用効率が悪い

4.3.2　保守的GCとの相性が悪い

4.3.3　再帰的関数呼び出し

4.4　Cheneyのコピー法

4.4.1　copy()関数

4.4.2　実行過程

4.4.3　隠されたキュー

4.4.4　メリット

4.4.5　デメリット

4.5　近似的深さ優先探索法

4.5.1　CheneyのコピーGC（おさらい）

4.5.2　前提

4.5.3　実行過程

4.5.4　実行結果

4.6　複数空間コピー法

4.6.1　multi_space_copying()関数

4.6.2　mark_or_copy()関数

4.6.3　copy()関数

4.6.4　実行過程

4.6.5　メリット

4.6.6　デメリット

第5章　マークコンパクトGC（Mark Compact GC）

5.1　マークコンパクトGCとは

5.1.1　Lisp2アルゴリズムにおけるオブジェクト

5.1.2　概要

5.1.3　1. forwardingポインタの設定

5.1.4　2. ポインタの更新

5.1.5　3. オブジェクトの移動

5.2　メリット

5.2.1　ヒープ領域を有効に利用可能

5.3　デメリット

5.3.1　重いコンパクション処理

5.4　Two-Fingerアルゴリズム

5.4.1　前提

5.4.2　概要

5.4.3　1. オブジェクトの移動

5.4.4　2. ポインタの更新

5.4.5　メリット

5.4.6　デメリット

5.5　テーブルアルゴリズム

5.5.1　概要

5.5.2　1. （前半）—オブジェクト群の移動

5.5.3　1. （後半）—ブレイクテーブルの構築

5.5.4　2. ポインタの更新

5.5.5　メリット

5.5.6　デメリット

5.6　ImmixGC

5.6.1　概要

5.6.2　ヒープ領域の構成

なぜマーク用に1バイトも必要なの？

5.6.3　オブジェクトの分類

5.6.4　アロケーション

5.6.5　アロケーション時のマーク操作

5.6.6　ステップ1—Fromブロック候補の選定

5.6.7　ステップ2—探索フェーズ

5.6.8　ステップ3—スイープフェーズ

5.6.9　メリット

5.6.10　デメリット

第6章　保守的GC（Conservative GC）

6.1　保守的GCとは？

6.1.1　不明瞭なルート（Ambiguous roots）

6.1.2　ポインタと非ポインタの識別

6.1.3　ポインタのような非ポインタ（False pointer）

6.1.4　不明瞭なデータ構造（Ambiguous data structures）

6.2　メリット

6.2.1　言語処理系がGCに依存しない

6.3　デメリット

6.3.1　ポインタと非ポインタの識別によるコスト

6.3.2　ポインタの誤識別によるヒープの圧迫

6.3.3　使用できるGCアルゴリズムが制限される

6.4　正確なGC（Exact GC）

6.4.1　正確なルート（Exact roots）

6.4.2　タグ付け

6.4.3　レジスタ、スタック等をルートとしない

6.4.4　メリット

6.4.5　デメリット

6.5　間接参照

6.5.1　ハンドラ経由のオブジェクト参照

6.5.2　メリット

6.5.3　デメリット

6.6　MostlyCopyingGC

6.6.1　概要

6.6.2　ヒープ構造

6.6.3　アロケーション

6.6.4　new_obj()関数

6.6.5　add_pages()関数

6.6.6　GC実行過程

6.6.7　mostly_copying()関数

6.6.8　promote_page()関数

6.6.9　page_scan()関数

6.6.10　copy()関数

6.6.11　メリット・デメリット

6.7　ブラックリスト

6.7.1　ポインタの誤識別による被害

6.7.2　ブラックリスト

6.7.3　ブラックリスト内のアドレスへのアロケーション

6.7.4　メリット・デメリット

第7章　世代別GC（Generational GC）

7.1　世代別GCとは

7.1.1　オブジェクトの年齢

7.1.2　新世代オブジェクトと旧世代オブジェクト

7.2　Ungarの世代別GC

7.2.1　ヒープ領域の構成

7.2.2　記憶集合（Remembered set）

7.2.3　ライトバリア（Write barrier）

7.2.4　オブジェクトの構造

7.2.5　アロケーション

7.2.6　マイナーGC（Minor GC）

生存領域があふれたら？

7.2.7　メジャーGC（Major GC）

7.3　メリット

7.3.1　スループットの改善

7.4　デメリット

7.4.1　一部のプログラムでは逆効果

7.5　世代間の参照を記録する方法

7.5.1　カードマーキング

7.5.2　ページマーキング（Page marking）

7.6　複数世代管理GC（Multi-generational GC）

7.7　トレインGC（Train GC）

7.7.1　ヒープ領域の構成

7.7.2　マイナーGC

7.7.3　メジャーGC

7.7.4　ライトバリア

記憶集合のオーバーフロー

7.7.5　メリット

7.7.6　デメリット

8.1　インクリメンタルGCとは

8.1.2　マークスイープGCの分割

8.1.3　ルートスキャンフェーズ

8.1.4　マークフェーズ

8.1.5　ライトバリア

8.1.6　スイープフェーズ

8.1.7　アロケーション

8.2　メリット：最大停止時間の短縮

8.3　デメリット：スループットの低下

8.4　Steeleのアルゴリズム

8.4.1　mark()関数

8.4.2　ライトバリア

8.5　湯淺のアルゴリズム

8.5.1　マークフェーズ

8.5.2　黒オブジェクトから白オブジェクトへのポインタ

8.5.3　ライトバリア

8.5.4　アロケーション

8.6　各ライトバリアの比較

第2部 実装編

第9章　PythonのGC

9.1　はじめに

9.1.1　Pythonとは

9.1.2　Pythonのソースコード

9.1.3　PythonのGCアルゴリズム

9.2　オブジェクト管理

9.2.1　オブジェクトの構造

9.3　Pythonのメモリアロケータ

9.3.1　メモリ構造

9.4　第0層 汎用的な基礎アロケータ

9.5　第1層 Python低レベルメモリアロケータ

9.5.1　メモリ構造

9.5.2　アリーナ

9.5.3　プール

9.5.4　new_arena()

9.5.5　usable_arenaとunused_arena_objects

9.5.6　第1層まとめ

9.6　第2層 Pythonオブジェクトアロケータ

9.6.1　ブロック

アドレスのアラインメントを利用したハック

9.6.2　usedpools

9.6.3　トリッキーな usedpools

9.6.4　ブロックの状態管理

9.6.5　PyObject_Malloc()

9.6.6　（A）usedpoolからプール取り出し

9.6.7　(B)プール内のブロック返却

9.6.8　(C)new_arena()呼び出し

9.6.9　(D)使用済みプールの初期化

9.6.10　(E)プールを初期化してブロック返却

9.6.11　(F)空プールの初期化

9.6.12　PyObject_Free()

9.6.13　(A)freeblock に解放対象のブロックをつなぐ

9.6.14　(B)プールをアリーナに返却

9.6.15　(C)アリーナ解放

9.6.16　(D)usable_arenas の先頭に移動

9.6.17　(E)usable_arenas のソート

9.6.18　(F)プールの挿入

9.6.19　アリーナ＆プールの解放戦略

9.6.20　ブロックからプールを見つけるテクニック

9.7　第3層 オブジェクト特有アロケータ

9.7.1　アロケータまとめ

9.8　参照カウント

9.8.1　インクリメント

9.8.2　Q:カウンタのオーバーフローがおきないの？

9.8.3　デクリメント

9.8.4　ファイナライザ

9.8.5　カウント処理の挿入

9.9　参照の所有権

9.9.1　参照の所有権を渡す(戻り値)

9.9.2　参照の所有権を貸す(戻り値)

9.9.3　参照の所有権乗っ取り(引数)

9.9.4　参照の所有権を貸す(引数)

9.9.5　参照カウントを使うとバグを埋め込みやすい？

機械的なカウント処理

9.10　循環参照をもつゴミオブジェクトへの対応

9.10.1　循環参照GCのアルゴリズム

9.10.2　コンテナオブジェクト

9.10.3　コンテナオブジェクトの生成

9.10.4　コンテナオブジェクトの追跡

9.10.5　コンテナオブジェクトの追跡終了

9.10.6　世代別コンテナオブジェクトリスト

9.10.7　循環参照GC実行タイミング

9.10.8　循環参照GC

9.10.9　gc_list_merge()

9.10.10　update_refs()

9.10.11　subtract_refs()

9.10.12　move_unreachable()

9.10.13　move_finalizers()

9.10.14　move_finalizer_reachable()

9.10.15　delete_garbage()

9.10.16　handle_finalizers()

9.10.17　循環参照におけるファイナライザの問題

9.10.18　ライトバリアはいらないの？

9.11　パフォーマンスチューニングのヒント

9.11.1　gc.set_debug()

9.11.2　gc.collect()

9.11.3　gc.disable()

第10章　DalvikVMのGC

10.1　はじめに

10.1.1　Androidとは

10.1.2　Android アーキテクチャ

10.1.3　DalvikVM の特徴

10.1.4　Androidはマルチタスク

10.1.5　bionic

10.1.6　ashmem

10.1.7　dlmalloc

10.2　mmap再入門

10.2.1　mmap とはなにか

10.2.2　アロケーションへの活用

10.2.3　デマンドページング

10.2.4　共有マッピング・プライベートマッピング

10.2.5　コピーオンライト(Copy-On-Wirte)

10.3　DalvikVMのソースコード

10.3.1　ソースコード入手

10.3.2　ソース構成

10.4　DalvikVMのGCアルゴリズム

10.5　オブジェクト管理

10.5.1　オブジェクトの種類

10.5.2　オブジェクト構造

10.5.3　DalvikVMのメモリ構造

10.5.4　dvmHeapSourceStartup()

10.5.5　addNewHeap()

10.5.6　オブジェクトビットマップ

10.5.7　dvmHeapBitmapInit()

10.5.8　DalvikVMのVMヒープ領域へ割り当て

10.5.9　オブジェクトビットマップへのマーク

10.5.10　インスタンスのアロケーション

10.6　マークフェーズ

10.6.1　GC起動タイミング

10.6.2　マークの手順

10.6.3　保守的なルート

10.6.4　DalvikVMはレジスタマシン

なぜDalvikVMはレジスタマシンなのか？

10.6.5　VMのコールスタック

なぜ保守的GCなのか？

10.6.6　イニシャルマーキング

10.6.7　ビットマップへのマーキング

10.6.8　非ポインタとオブジェクトを指すポインタの区別

10.6.9　オブジェクトスキャン

10.6.10　dvmHeapScanMarkedObjects()

10.6.11　dvmHeapBitmapXorWalk()

10.6.12　scanBitmapCallback()

10.6.13　scanObject()

10.6.14　processMarkStack()

10.7　スイープフェーズ

10.7.1　スイープを見る前に

10.7.2　スイープの始まり

10.7.3　dvmHeapSweepUnmarkedObjects()

10.7.4　dvmHeapBitmapXorWalk()

10.7.5　sweepBitmapCallback()

10.7.6　dvmHeapSourceFree()

10.8　Q&A

10.8.1　ファイナライザは？

10.8.2　なぜ2つビットマップを用意するの？

10.8.3　フラグメンテーションの問題は？

10.8.4　なんでビットマップマーキングなの？

第11章　RubiniusのGC

11.1　はじめに

11.1.1　Rubiniusとは

なぜRubiniusのGC解説を？

11.1.2　ソースコード入手

11.1.3　ソース構成

11.2　RubiniusのGCアルゴリズム

GCと言語処理系

11.3　オブジェクト管理

11.3.1　オブジェクトの構造

11.3.2　コピーGC用メモリ空間

11.3.3　オブジェクトアロケータ

11.3.4　コピーGCアロケータ

11.4　正確なGCへの道

11.4.1　ルート

11.4.2　CRubyは保守的GC

11.4.3　CRubyのC拡張ライブラリ

11.4.4　C拡張ライブラリ（正確なGC編）

11.4.5　Rubiniusの解決法

11.4.6　Hello Hello World

11.4.7　Rubiniusのハンドラ管理

11.4.8　GCとの関係

11.4.9　RubiniusとC拡張ライブラリのやりとり

C++とCのギャップを埋める

11.4.10　RubiniusのRubyC-APIは実用可能？

11.4.11　FFI(Foreign Function Interface)

FFIとRuby/DLはどう違う？

11.4.12　埋め込みオブジェクトとポインタの区別

11.5　コピーGC

11.5.1　全体の流れ

11.5.2　collect()

11.5.3　(1)記憶集合から参照されるオブジェクトのスキャン

11.5.4　ライトバリア

11.5.5　(2)ルートから参照されるオブジェクトコピー

11.5.6　saw_object()

11.5.7　(3)コピー済みオブジェクトのスキャン

11.5.8　copy_unscanned()

11.5.9　scan_object()

11.5.10　(4)ゴミオブジェクトの後処理

11.6　Q&A

11.6.1　それぞれのGCの起動タイミングは？

11.6.2　コピーGCを行うクラスの名前はなぜBakerGCなの？

11.6.3　なぜ正確なGCなの？

11.6.4　ImmixGCの実装は説明しないの？

11.6.5　なぜ記憶集合に旧世代のオブジェクトを記憶するの？

第12章　V8のGC

12.1　はじめに

12.1.1　Google Chromeとは

12.1.2　V8とは

V8の名前の由来

12.1.3　ソースコード入手

12.1.4　ソース構成

12.2　V8のGCアルゴリズム

12.3　オブジェクト管理

12.3.1　異なるアロケータをもつ2種類のクラス

12.3.2　Mallocedクラス

12.3.3　Objectクラス

12.3.4　その他の特殊なクラス

12.3.5　VMヒープ

12.3.6　旧世代ポインタ空間の構造

12.3.7　オブジェクトアロケータ

12.4　正確なGCへの道（V8編）

12.4.1　ハンドルスコープ

12.4.2　ハンドルスコープの有効範囲

12.4.3　ハンドルスコープの切り替え

12.4.4　タグ付け

12.4.5　オブジェクト内フィールド制御

12.4.6　型に対応したアクセサ

12.4.7　フィールド位置と正確なGC

12.5　マークコンパクトGC

12.5.1　GCアルゴリズム

12.5.2　GCの起動タイミング

12.5.3　GC概要

マークスイープGCとマークコンパクトGCの実装クラス

12.6　マークフェーズ

12.6.1　マークフェーズ概要

12.6.2　マークスタック作成

12.6.3　ルートマーク

12.6.4　オブジェクトマーク

12.6.5　子オブジェクトマーク

12.6.6　マークスタックを使った深さ優先マーク

12.6.7　マークスタックのオーバーフロー

12.6.8　オブジェクトのマークビット

12.7　コンパクションフェーズ

12.7.1　コンパクションフェーズ概要

12.7.2　(1)forwardingポインタ設定

12.7.3　コピー先アドレス情報

12.7.4　mapアドレス情報

12.7.5　EncodeForwardingAddresses()

12.7.6　EncodeForwardingAddressesInRange()

12.7.7　EncodeForwardingAddressInPagedSpace()

12.7.8　(2)ポインタの更新

12.7.9　UpdatingVisitor

12.7.10　GetForwardingAddressInOldSpace()

12.7.11　(3)オブジェクトの移動

12.7.12　(4)記憶集合更新

12.7.13　記憶集合の構造

12.7.14　RebuildRSets()

12.7.15　UpdateRSetVisitor

12.7.16　SetRSet()

12.8　Q&A

12.8.1　Androidで動くって聞いたけど？

12.8.2　ファイナライザは？

付録1　補遺

簡単言語入門：Python編

組み込みデータ型

数値型

シーケンス型

マップ型

クラス

簡単言語入門：Java編

プリミティブ型と参照型

配列

クラス

簡単言語入門：Ruby編

すべてがオブジェクト

クラス

簡単言語入門：JavaScript編

プリミティブ型と参照型

オブジェクト

GCを作ってみませんか

付録2　あとがき

電子書籍の出版に寄せて

付録3　参考文献

論文

書籍