Kashiwa Schemeにライトバリアが付きました
前回のエントリの最後に
面白いのが、スタックからヒープへのコピーという処理は、
スタックをyoung領域、ヒープをold領域とした世代別GCとも見なせる点です。
……と、ここまで書いた時点で、ヒープからスタックへの参照を、
remember setに入れて覚えておく必要がありそうな気がしてきたけど、
そんな処理は書いてないぞ。なんてこった。ライトバリアとか書きたくないぞ。
などと言いましたが、結局ライトバリアを書きました。
—
そもそも何が問題だったかを簡単に書きます。
(define (g x)
(lambda (z)
(set! x (cons z x))
x))
(define ls (g 1))
(ls 2)
(ls 3)
...
Kashiwa Schemeは基本的にすべてのオブジェクトをスタックに割り当てます。
(ただしシンボルは最初からヒープに割り当てます。)
そのため、上記プログラムでは、(g 1)によって作られるクロージャは、
スタックに割り当てられ、そのアドレスがグローバル変数lsに代入されます。
しばらくしてスタックに対するごみ集めが起こると、先ほどのクロージャはヒープに移されます。
その後に(ls 3)などの評価を行うと、上記のクロージャが呼び出され、
クロージャの保持する変数xに『新しいコンス』が代入されます。
新しいコンスはもちろんスタックに割り当てられるわけです。
このようにして、ヒープからスタックへの参照が生まれます。
この状態でスタックに対するごみ集めが起こると、
上記のクロージャはルートセットに含まれないため、
コンスがごみとして回収されてしまいます。
これはどう考えてもまずいわけです。
—
で、解決策はいくつかありまして、一番簡単なのは、
スタックに対するごみ集めのたびにヒープ全体を舐めることです。
これは確実な上、簡単に書くことができますが、
ごみ集めにかかる時間が明らかに増大します。
別の解決策として、ヒープからスタックへの参照を記憶する方法があります。
ヒープからスタックへの参照を覚えておき、それをルートセットに加えることで、
回収漏れを防ぐというやり方です。これだとごみ集めの時間はあまり増えません。
ヒープからスタックへの参照の集合をremember setと呼ぶことにします。
ごみ集めを正しく行うためにはremember setを正しく作る必要があります。
ヒープからスタックへの参照がいつ生まれるかというと、set!やset-car!などの、
破壊的代入が行われる時のみです。
それらの場所で、必要があればremember setに参照を加えればいいわけです。
書き込みを行う場所で見張るため、この処理をライトバリアと呼びます。
remember setにも作り方が色々あります。
一つは単純にアドレスを1つずつ覚える方法。
この方法だと、ヒープからスタックへの参照の数だけメモリが必要です。
例えば、対象となる参照が1M個ある場合、remember setは4MB必要です。
(アドレスは32bitとして計算してます)
もう一つの方法は「おおよその場所」を覚える方法です。
ヒープを例えば512bytesごとのブロックに区切り、
ブロックの中にヒープからスタックへの参照が(1個以上)あるかを記憶します。
remember setのサイズは参照の数ではなくヒープサイズに比例します。
参照の有無は1bitあれば表せるので、ヒープが1GBあっても、
remember setはたったの256KBで十分なわけです。
(K=1024, M=1024K, G=1024Mで計算しています)
さてさて、どちらの方針が有利でしょうか。
対象となる参照の数が非常に多い場合は、おおよその場所を覚える方がいいでしょう。
しかし、おおよその場所しか覚えない場合は、
スタックに対するごみ集めの時に「実際の場所」を探すために
余計なスキャンを行う必要があります。
対象となる参照の数が少ない場合はアドレスを1つずつ覚える方がいいでしょう。
さて、Schemeといえば、破壊的代入を嫌う文化があります。
そのため、対象となる参照の数は十分に少ないと仮定していいでしょう。多分。
そんなわけでアドレスを1つずつ覚える方針を取ることにしました。
これを書きたかっただけなのに説明がえらく長くなってしまった。