write barrier

9 Generational GC

(中略)

さて、Schemeにおいて、ユーザプログラムがconsやvectorのみを用いる限り、旧→新のポインタは決して生まれない。 Set-car!などの破壊的代入を行なって初めて生じるものである。コンパイラが、破壊的代入の際に必ずGCに知らせる(書き換えられるオブジェクトを GCに教える)ようにすれば、GCが旧→新のポインタ全てを手早く見つけることができる。このように、メモリオブジェクトへの書き込みの際に特別な処理を行なう機構をwrite barrierという(注)。

(中略)

10 Incremental GC

(中略)

Generational GCと同様に、write barrierが必要になる (ここではmark and sweepを仮定する)。 Write barrierがないと破綻する例を図8に示す。マークフェイズの途中でaが黒になった時点(b, cはまだ白)で、ユーザプログラムが動き出すとする。ユーザプログラムがaからcへのポインタを作り、bからcへのポインタを消す(NULLなどで上書き)とする。この状況でGCが再開するとbまではマークを行なうが、cのマークは一切されないためcは誤って解放されてしまう。

(中略)

Copying GCを素直にincrementalにしようとすると、read barrierが必要になる(のでとても遅い)。詳しくは [2]の8章、[4]の3章などを参照のこと。

(中略)

...行なう機構をwrite barrierという
コンパイラの協力が得られない場合でもwrite barrierを実現することは可能である。大抵のOSではメモリ領域のアクセス権限を変えることができる(SunOSのmprotect()など)ので、旧世代ヒープを write不可にしておくことによって、writeをつかまえることができる

MS CLR も旧世代オブジェクトから新世代オブジェクトへの参照は write barrier で引っ掛けているので,そもそもそういう参照を作らないようにコーディングすることにはそれなりに意味があります.
そういえば「ワンダと巨像」のインタビューでもインクリメンタルにコンパクションを行っているっぽい話が出てました.

新しいエリアに入れば新しいエリアの地形データやテクスチャなどを読み込み、変わりに不要になったデータはどんどん破棄される。これを繰り返していくとメモリの中は使用領域と未使用領域の虫食い状態になってしまう。メモリの使用効率が悪くなってしまう。

ワンダと巨像」では、垂直帰線期間を見て余裕があるときに、バックグラウンドでこうしたメモリ領域の再配置処理を行なっているのだという。プログラムのアドレス等も再配置に対応する仕組みを導入しているそうで、まさに、オリジナルOSを実装しているようなイメージだ。グラフィックスのように目に見える技術ではないが、そういった部分にも高度な技術が活用されているからこそ、作品からトータルな品位の高さが醸し出されているのかも知れない。

まあ任意のデータじゃなくって特定リソースのみなら実装上の制限は緩くなりそうですね.さて「オリジナルOSを実装」とありますが,Copy-On-Write にしてもハードウェアのサポートは重要です.そういう意味では Azul Sysmtes の Vega で最適化を極めてみる,なんてのも楽しそうですね.いい加減 IA32 の VM に皆さん飽きてきてたりしませんか?

ここから本題。 Azul Sytems の NAP は Pauseless GC という一風変わった GC アルゴリズムを採用している。 Pauseless GC は理論上 STW がない。にも関わらず性能もあまり悪くないというキ印もの。


中略


もう一点すごいのはmarking が完全に concurrentな点だ。 Mostly concurrent ではない。この実現方法が凄いと言うか、インチキというか... 鍵になっているのはハードウェア・サポートだ。