Kashiwa Schemeに世代別GCが付きました
Rubyとか、Dalvik(Android用の仮想マシン)には、
(少なくても正式には)世代別GCが付いていないらしいですね。
そういった意味ではKashiwa SchemeはRubyやDalvikを、
超えた…そういっても過言ではないかもしれません。
いえ、ずばり過言でしょう。ごめんなさい。
Kashiwa Schemeでは、オブジェクトは1回のごみ集めを生き残るだけで、
tenuring(殿堂入り)します。たったの1回です。
「1回」というパラメータを意図的に設定しているのではなく、
仕組み上、そうすることしかできません。安っぽい殿堂入りですね。
—
世代別GCを付けたといっても、ごく普通のヒープに対するGCを書いただけです。
ヒープを半分に分けて片方だけ使うという、ごく普通のcopying GCを書きました。
＃ここでいう「ヒープ」はScheme用に管理している領域のことであり、
＃プロセス自体のヒープのことではありません。
スタックに対するGCは、
『スタックをfrom-space、ヒープをto-spaceとしたcopying GC』
であったのに対して、ヒープに対するGCは
『ヒープの半分をfrom-space、ヒープのもう半分をto-spaceとしたcopying GC』
であり、本質的には同じものです。
書き加えたのはわずかに100行ほどです。なんと楽なことでしょう。
—
ヒープに対するごみ集めでも、スタックへの参照を見つけたら、
それをヒープにコピーするようにしています。
こうすることで、ヒープに対するごみ集めが完了すれば、
スタックに対するごみ集めも同時に完了するようになります。
少し面倒なのは、ヒープに対するGCは、
スタックに対するGCの途中で発生する(可能性がある)ということです。
スタック上のものをヒープにコピーしている途中でヒープが足らなくなると、
ヒープに対するごみ集めが動き出します。
このとき、スタック上にはヒープを指すforwarding pointerがある可能性があります。
そのため、ヒープに対するごみ集めの最中にforwarding pointerを見つけても、
そのまま鵜呑みにするのではなく、どこを指しているのか確認する必要があります。
—
また、ヒープに対するごみ集めの途中で、ヒープが足りなくなることがあります。
オブジェクトのコピーがヒープの中で完結していれば大丈夫なのですが、
スタックからもオブジェクトをコピーするため、ヒープが不足することがあります。
ヒープが不足した場合、mallocを使って現在のヒープの「2倍」の領域を確保します。
そして、以前のヒープ全体(from-spaceとto-spaceの両方)を改めてfrom-spaceとして、
新しく確保した領域(の半分)をto-spaceとして再度GCを行います。
こうすることにより、オブジェクトが新しい領域にうまく移動してくれます。
ヒープの拡張にはreallocを使ってもよさそうなのですが、
reallocは(古い領域を拡張するのではなく)別の場所に領域を新たに確保した場合、
古い領域をその場で開放してしまうのが問題になります。
スタックからヒープへの参照が残っている可能性を考えると、
古い領域をその場で解放されてしまっては困ります。
理想は、ヒープが移動しない場合はreallocを用いて、
そうでない場合はmallocを使うということなのですが、
そんなことってできるのでしょうか。
sbrkを使って自分で書くしかないんですかね。
—
また、上記の「2倍」という数字には根拠がありません。
新たに設定するfrom-spaceと同サイズのto-spaceを設定するためには、
2倍にするのが都合がいいのですが、
スタックからのオブジェクトのコピーが非常に多い場合には、
ヒープ拡張後に、再度ヒープが足らなくなる可能性があります。
今のところ、ヒープが再度不足した場合には、
その場で終了するようにしています。
本当は、from-spaceをうまく設定して再度GCをやり直すか、
そもそも不足が置きないだけの十分な領域を確保するのが良いでしょう。
整合性を保ったままfrom-spaceを設定するのはかなり面倒です。
そのため、十分な領域を確保するというのがいいのですが、
これはこれで意外と厄介です。
スタックの長さが閾値を超えたら、GCが始まるわけですが、
閾値を「どれだけ超える可能性があるか」は分からないのです。
とはいえ、どれだけ超えたかは知ることが可能なので、
現在のスタック全体をヒープにコピーしても大丈夫なくらい、
ヒープを拡張すればいいということに今気づきました。
なんでエントリを書き始めてから気づくんでしょう。