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

内容紹介

本書は次の2つのテーマを扱います。

• GCのアルゴリズム(アルゴリズム編)
• GCの実装(実装編)

アルゴリズム編では、これまでに考案されてきた数多くのGCアルゴリズムの中から、重要なものを厳選して紹介します。伝統的かつ基本的なものから、やや高度なアルゴリズムを選定しています。GC独特の考え方や各アルゴリズムの特性などを理解していただくのがアルゴリズム編の最大の目的です。

実装編では、筆者らが選定した言語処理系のGCを読み進めていきます。アルゴリズム編では理論をしっかり学び、実装編で理論がどのように使われているのか、実際に見てみようというわけです。

（※本書は2010年3月に(株)秀和システムより発行された『ガベージコレクションのアルゴリズムと実装』(ISBN:9784798025629)を、著者原稿を元に電子書籍として再編集・発行したものです。）

書誌情報

• 著者: 中村 成洋, 相川 光, 竹内 郁雄(監修)
• 発行日: 2013-12-24
• 最終更新日: 2014-06-20
• バージョン: 1.0.0
• ページ数: 601ページ(PDF版換算)
• 対応フォーマット: PDF, EPUB
• 出版社: 達人出版会

対象読者

GCの好きな方。言語処理系のアルゴリズムと実装に興味のある方

著者について

中村 成洋

株式会社ネットワーク応用通信研究所 研究員
5年前まで田舎のアイス工場に勤めていたのだが、ひょんなことからGCが好きになってしまった。人からはよく「なんでGCが好きなの？」と聞かれるが、本人もよくわかっていないので、「運命です」と答えている。
現在はCRubyのコミッタとして日々、GCの改善に勤しんでいる。
本書では主に「実装編」を執筆した。

相川 光

東京大学大学院情報理工学系研究科 修士二年生（執筆時点での情報）
京都大学在学中からGCの研究をはじめる。
GCは好きだが掃除は大嫌い。GC以外ではカレーライスをこよなく愛する。
本書では主に「アルゴリズム編」を執筆した。

竹内 郁雄

東京大学大学院情報理工学系研究科教授（監修時点での情報）
バグのため、再利用されることなくお亡くなりになった(リークした)オブジェクトの供養を行ったこともあるオブジェクト思い。10年ほど前に33MHzの専用マシンで割込み反応遅延が130マイクロ秒という並行ゴミ集めを80ビット水平マイクロプログラムで実装したことが自慢。でも、本職(?)のオーディオマニアではケーブルなどのアナログ性に没頭。

目次

目次

監修者まえがき

本書のレビューを終えて

序章

• はじめに
• 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章　インクリメンタルGC（Incremental GC）

• 8.1　インクリメンタルGCとは
• 8.1.1　三色マーキング（Tri-color marking）
• 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　参考文献

• 論文
• 書籍