Mark-sweepのunmarkをサボる
ガベージコレクション 自動的メモリ管理を構成する理論と実装を読んでたら、ごみ集めのたびにマークビットの意味を反転させればunmarkのコストを避けれる、という話があったので試してみた。
恐らく、これが効果があるのはヒープが巨大な時と、unmarkのコストが大きい時だろう。巨大なヒープを使うのはいやなので、unmarkのコストが大きい（要するに遅い）NScLisperでこれを実装してみた。
Benchmark program: (define (muda n . r) (if (<= n 0) r (muda (- n 1) (cons 0 0)))) (time (muda 3000)) Before: 47143 ms After: 46688 ms
どちらも評価時にごみ集めは8回走った。
まあ、速くなったといえば速くなったけど、それほど大きな違いはなかった。
恐らくNScLisperのヒープが小さすぎるのが一番の原因だろう。NScLisperのヒープは2900セルしかない。
それから、consingの際に、これまではマークビットが0であることが保証されていた (初期値は0だし、再利用の際もsweep時に0になる) ので何もする必要はなかったが、この変更により「マークされてないことを表す値」をマークビットに設定する必要が出てくる。このコストはunmarkと変わらない。つまり、unmark処理省略の恩恵を受けれるのは基本的に生きているオブジェクトだけだ。
(正確にはプログラム終了時に使われてないセルについてもunmarkのコストを避けたことになるが、逆に最初のごみ集めが起こるまでのconsingでは余計なコストが増えている)
このプログラムでは常に約700セルが使われているので、8回のごみ集めで合計5600回分のunmarkのコストを避けたことになる。これだけで455ms速くなったのだからお得といえばお得な気もする。
ただし、変数が合計で4096個しか作れない（ヒープやスタックも含む）環境下で変数を1つ消費する価値が有るかというと、やはり微妙なところだ。
(自分用メモ)
マーク済みを表す値ではなくマークされてないことを表す値を変数に入れたほうが減算の回数が減るのではないかと気付き試したが、結果に変化は見られなかったのでrevertした。