SGC

色々あって GC に興味がちょっと出たので色々見てました。とりあえずまとまった日本語資料としては以下の PDF が一番良いように思いました。 kinaba さんがちょっと前に言及しておられたえんどう豆的でない方の遠藤さんが書いた文章らしい。

http://matsu-www.is.titech.ac.jp/~endo/gc/gc.pdf

これをざーと読んでいくと、すごくためになって、色々わかるのですが、最後の方の 7.2 に、

筆者は、 parallel かつ concurrent な GC を、 Boehm GC を基にして実装している。

とか書いてあって、そのちょっと前に concurrent GC ってのは要は別スレッドでちょいちょい GC 動かす実装で、 incremental GC の一種と考えられて、要 write barrier 。とか書いてあるわけです。でこれってちょっと考えるとどうやってやるのか不明気味な感が強いんです。なんでかっていうと、 Boehm GC ってターゲットの言語について知らない、 conservative GC って種類の GC で、ポインタっぽいものが見えたら全部ポインタだと考えて mark していくような実装。で mark されなかったものは sweep のフェーズで消しちゃう、と。で、 write barrier ってのは GC が mark してる最中にポインタがつけ変わっちゃったりするとあら大変なので、ポインタの書き換えが起きた時にこれ危ないから mark やりなおしねーというようなフラグを立てとくみたいな手法。でもまぁ普通に考えると C 言語とかで変数代入が起きるたびになんか mark する、とかいうのはできない。つまり言語処理系は協力してくれないのね。

んでまさかメモリ保護とかちゃうよなーとか話しつつ調べてもらったところによると、

http://matsu-www.is.titech.ac.jp/~endo/papers/endo-ismm2002-gc.ppt

本当にメモリ保護らしい。つまり、

  • 別スレッドでこっそり mark をしょぼしょぼ
  • mark しはじめる page は書き込み保護かける
  • もし write fault 起きて SIGSEGV 飛んだらその page に dirty flag を立ててメモリ保護外しとく。ここで外しとくからそんなに SEGV 地獄にはならんと。
  • mark が終わったら final mark とかいうフェーズに突入
  • このフェーズで dirty flag が立ってる page を mark しなおし。ちなみに final mark は全スレッドを止めて行うのでオーバヘッドになっちゃう
  • あとは sweep 。これも裏でしょぼしょぼ。

って感じみたい。あとは dirty page が増えてきたら protect しなおしてそこの mark をして final mark が遅くなりすぎないようにするとか、 final mark が timeout したら incremental mark をやりなおすとかそいう工夫があるらしい。

いやーすごい人がいるもんだなぁと久しぶりに感動しました。なんていうかアイデアも実装もどっちもすごいですよね。なんかベンチ結果とかも異様にいいしなー。

コードとかも公開されているのでちょっと遊んでみたいなぁと思っています。

http://www.yl.is.s.u-tokyo.ac.jp/gc/sgc-j.shtml

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h