copying_gcという車輪の再発明
なんか、最近、「車輪の再発明をしよう」みたいな話がちょくちょくあるので、GCを再発明してみた。
「車輪の再発明をしよう」の例：
https://twitter.com/viscuit/status/288181884658257922
…まぁ、再発明っていうか、スクラッチで書いただけなんですけど。
コード
ここに置きました。
https://github.com/dec9ue/copy_gc/blob/master/copy_gc.c
簡単に解説
基本的にGHCのGCコードとほぼ同じアイディアで作っています。
つまり、
- Cheneyのアルゴリズムがベース
- 比較的サイズの大きなオブジェクトはコピーすると不利なので、pin留めされるように作っている
ただし、下記のような点は違います。
- 世代別GCはない
- Parallel GCもない
- InfoPointerのかわりに先頭1wordでオブジェクトの性質をメモっている
Cheneyのアルゴリズムについては以前に書いたスライドのp.12とかGCの神の記事とか見てください。
時間的な問題もありますが、世代別GCは実行コード側に手が入るのでやってません。
ParallelGCは。。。知らんがな。
「大きなサイズ」の話
GHCもそうなんですが、純粋なコピーGCではなく、マークスイープの考え方を混ぜています。
これによって、コピーGCの弱点であるコピーのコストを回避するとともに、FFIなどで使用するための「動かないオブジェクト」を作ることができます。
InfoPointerがらみの話
コピーGCでは、オブジェクトのサイズと含まれているポインタを正確に把握しなくては行けません。
GHCではInfoPointerというのがこの仕事をしています。このInfoPointerの先はTEXT領域にあって、リンク先をたどるとオブジェクトのサイズなどがわかります。
今回はこれは使用せず、(実行側に依存しちゃうもんね)オブジェクトの直上に1ワードとってその中にサイズやポインタ数を記録しました。
GHCのヒープ構造はここをみると解説があります。
良いコードなのか？
実戦で評価してないのでわからないです。何で評価したらいいんだろう。。。
感想
- ムシャクシャしてやった。でもまだ反省してない。
- gcのコードサイズはJHCのGCコードとさほど変わらない。(けど、統計機能が入ってないので、同じ機能に対してはこちらのほうが大きいとも言える。。。)
- gcって意外に書ける気がする。でも時間かかりすぎたか。
- パフォーマンスまだ測ってない。測り方募集中。
- 「ここがヘンだよ」みたいなのあったら教えてくださいこわい人。
参考：
JHCのGCコード：
http://repetae.net/dw/darcsweb.cgi?r=jhc;a=headblob;f=/rts/rts/gc_jgc.c