class: title # ガベージコレクション ## 自動的メモリ管理を構成する理論と実装 --- # 目次 .double-column.small[ 第1章：.wrap[イントロダクション] 第2章：.wrap[マークスイープガベージコレクション] 第3章：.wrap[マークコンパクトガベージコレクション] 第4章：.wrap[コピーガベージコレクション] 第5章：.wrap[参照カウントガベージコレクション] 第6章：.wrap[ガベージコレクター間の比較] 第7章：.wrap[アロケーション] 第8章：.wrap[ヒープの分割] 第9章：.wrap[世代ガベージコレクション] 第10章：.wrap[他の分割手法] 第11章：.wrap[ランタイムインターフェース] 第12章：.wrap[言語特有の問題点] 第13章：.wrap[並行処理の予備知識] 第14章：.wrap[並列ガベージコレクション] 第15章：.wrap[並行ガベージコレクション] 第16章：.wrap[並行マークスイープ] 第17章：.wrap[並行コピーと並行コンパクション] 第18章：.wrap[並行参照カウント] 第19章：.wrap[リアルタイムガベージコレクション] ] --- # 第1章 イントロダクション 動的メモリ割り付け - オブジェクトサイズを動的に決められる - 再帰的データ構造を定義利用できる - オブジェクトを呼び出し元に返せる - 関数を返す関数 ヒープのオブジェクトは参照を用いてアクセスする - オブジェクトへのポインタ - オブジェクトを指すハンドルを指すポインタ - オブジェクトの再配置が容易 --- # 1.1 明示的な解放 動的に確保したメモリのうち、不要なものになったものを回収する - 明示的解放 - `free` (C) や `delete` (C++) - ランタイムによる自動的回収 - 参照カウント法 - 追跡型GC --- # 明示的解放に関するエラー - 宙ぶらりんポインタ (dangling pointer) - 解放が早すぎて、まだ参照が残っている - 検出法の例: ファットポインタ (fat pointer) - メモリリーク - 解放し忘れ 両者は同時に起こりうる  --- # メモリ管理は難しい オブジェクトが(特にスレッド間で)共有されると難しい - 並行プログラミングはますます日常的 - 並行プログラミングの問題は難しい オブジェクトの活性はグローバルだが解放の決定はローカル - 各スレッドのうち誰が共有オブジェクトを解放すべき？ 解決策: - 所有権を一貫したやり方で扱う - スマートポインタ --- # 1.2 自動的な動的メモリ管理 GCは - 宙ぶらりんポインタを防止する - 原則的にすべてのゴミを解放する - ゴミの定義は決定可能なものに限る - 効率のために回収しないことがある GCはメモリ管理をインターフェイスから切り離す --- # GCができること・できないこと GCが全てのメモリエラーを解決するわけではない - メモリリークの可能性は減らせるが根絶はしない - 宙ぶらりんポインタは生じない - 先の図の状況は起きない - 二度とアクセスされなくても到達可能であればリークする メモリ以外の資源は管理しない - GCとは別の何かで管理する --- # 1.3 ガベージコレクションアルゴリズム間の比較 全ての場合に「最も良い」GCを決めることはできない GCを比較するための尺度: - 安全性 - スループット - 完全性と即時性 - 停止時間 - 空間的オーバーヘッド - 特定の言語への最適化 - スケーラビリティとポータビリティ --- # GCの比較の尺度 (1/2) - 安全性 - 生きているオブジェクトは回収しない - スループット - mark/cons (コレクタ/ミューテータ) 比 - 完全性 - すべてのゴミを回収する - 即時性 - ゴミが発生したら直ちに回収する - 停止時間 - プログラムの実行の邪魔を最小限にしたい --- # GCの比較の尺度 (2/2) - 空間的オーバーヘッド - 管理に必要な余分なメモリの量 - 特定の言語への最適化 - 特定の言語パラダイムの活用 - スケーラビリティ - マルチコアハードウェアの活用 - ポータビリティ - 特定のOSやハードウェアのサポートへの依存 --- # 1.4 性能上の欠点？ GCは性能上のペナルティがあるが、それほど大きくない - アプリケーションやハードウェアに依存する - `malloc`/`free` にもコストはある 十分に大きなヒープがあればGCは互角に戦える --- # 1.5 実験の手法 GC界隈の実験手法の水準は低く、改善の余地あり (研究者向けの内容) --- # 1.6 用語と表記法 (教科書参照)