Mark Sweep GCについて
tryangle勉強会 2019/3/13
あとでブログに書き直す(かも)
スライドにして見てね
大まかな目次
動機
GCとは
短所への対策
用いられている言語の例
終わり
動機
この辺の本を読んでいる
GC (Garbage Collection) とは
自動でメモリ上のゴミを回収し、再利用できるようにしてくれるやつ
主にヒープ上の話
メモリ界のこんまり
GCがないとどうなるか
手動でメモリを管理しないといけない
mallocとかfreeとかするやつ
起きそうな問題
メモリリーク
ダングリングポインタの参照
使用中のメモリの誤解放
GCのない言語
C, C++, Rust, etc.
モダンな言語にはだいたい入ってる
弱点もある
GC中はプログラムが停止する
stop the world
基礎的なGC
以下の4つが基本的なもの
Mark Sweep GC ← 今回話すやつ
Refeence Counting GC
Copying GC
Mark Compact GC
それ以外のGC
さっきの4つのいずれかの組み合わせ
割といっぱいある
etc.
Mark Sweep GC の話
Mark Sweep GCの概要
世界初のGC
John McCarthy, 1960年
2つのフェーズから成る
Mark Phase
Sweep Phase
Mark Phase
生きているオブジェクト全てにマークを付ける
深さ優先探索が用いられることが多い
キャッシュを利用をしやすい
メモリの使用効率が良い
生きているオブジェクトの数に比例して時間がかかる
手順
1. ルートから辿れるオブジェクトにマークを付ける
2. さらにそこから辿れるオブジェクトにマークを付ける
Sweep Phase
マークが付いていないオブジェクトを回収する
その後、マークが付いているものはマークを外す
ヒープのサイズに比例して時間がかかる
図で見てみよう
Aはルートオブジェクト
緑はマークを付けたオブジェクト
Work List はアルゴリズム上つかうもので、マーク付けてないやつをメモっておくもの
矢印は参照を表す
ポイントは深さ優先探索してるとことか
ex.
例えば以下の例ではオブジェクトAがBとGを参照している
Aはルートオブジェクト
深さ優先探索なのでGではなく、Cをマークした
Work ListにDとEをメモ
マークを付けたのでWork ListからDを消して、次のEを入れた
マークを付けたのでWork ListからEを消した
一番深くまで来たので、上へ戻る
JとかLとかは辿れないので無視
Hをマーク
HはGを参照しているが、すでにマークしているのでなにもしない
Mark Phaseが終わった
この時点で絶対にWork Listは空になる
ここからSweep Phaseへ入る
死んでるオブジェクトを回収してフリーリストに入れる
次のGCへ備えてマークを外しておいた
ここまでずっとStop the World状態
ここでやっとミューテータへ実行権を移す
さっきのスライドをもう一度見てみる
Mark Phase
生きているオブジェクト全てにマークを付ける
深さ優先探索が用いられることが多い
キャッシュを利用をしやすい
メモリの使用効率が良い
生きているオブジェクトの数に比例して時間がかかる
手順
1. ルートから辿れるオブジェクトにマークを付ける
2. さらにそこから辿れるオブジェクトにマークを付ける
Sweep Phase
マークが付いていないオブジェクトを回収する
その後、マークが付いているものはマークを外す
ヒープのサイズに比例して時間がかかる
Q. どこにマークすんねん
A. オブジェクトのヘッダの中です
ONかOFFなので1bitでいける
用語の説明
チャンク
フリーリスト
チャンクとは
「塊」という意味
初期状態はヒープ全体が一つのチャンク
「メモリくれ」って言われたら、ここから適切なサイズを切り出して渡す
チャンクを分割しすぎるとフラグメンテーションの原因になる
フリーリストとは
回収されたチャンクを管理する片方向リンクリスト
チャンクのサイズはばらばら
主にメモリアロケート時に使う話
「メモリくれ」と言われたら、この中から適切なサイズのチャンクを探して切り出して渡す
Mark Sweep GC の長所
実装が簡単
ミューテータの読み出し、書き出し操作にオーバーヘッドがかからない
Mark Phase のスループットが高い
ヒープの空間的使用量の効率が良い
保守的GCとの相性がいい
短所
フラグメンテーション起こりがち
アロケートのたびにフリーリストを探索するので時間がかかる
コピーオンライト(CoW) との相性が悪い
せっかくメモリ共有してるのにMark Phaseで生きてるオブジェクト全てにマークを付けるので不必要にコピーされまくる
CoWとは→前にブログに書いた
短所への対策
Multiple free-list
Big Bag Of Pages(BiBOP法)
Bitmap Marking
Lazy Sweep
Multiple free-list
チャンクのサイズごとにフリーリストを用意する
2ワード用、3ワード用、...、100ワード用、..、101ワード以上用の100個用意したり
フリーリストを全部探索する必要がなくなる
Big Bag Of Pages(BiBOP法)
フラグメンテーションの対策
ヒープを固定サイズに分割して、似たサイズのオブジェクトをまとめて配置して管理する
サイズ以外にも型でわけたりもすることもある
Bitmap Marking
CoWの相性の悪さへの対策
マーキングの有無をオブジェクトのヘッダではなく、別の場所の2次元テーブルで管理する
Lazy Sweep
ミューテータの最大停止時間を減少させる
Sweep Phaseのスイープ処理を遅延して行う
アロケート時に必要なチャンクが見つかるまでスイープ操作を行う
用いられている言語の例
Ruby(MRI)
JavaScript
Go v1.10
C#
C, C++
Boehm GCが使える
Java
Objective-C
etc.(調べきれてない)
おわり
僕の部屋と机の上もGCしてほしい