Schemeをつくろう(21) フリーリスト作り
GCの本格運用のためには、フリーリストが不可欠。ということでフリーリスト作り。
その前に復習。
データ構造
オブジェクトの表現は、2個の構造体で表現することにした。
+--------------+ +--------+
| オブジェクト | -> | データ |
+--------------+ +--------+
V
オブジェクト
Vオブジェクト全体は線形リストで繋がってます。
GCの実装
マーク・アンド・スイープ方式を取る。
- 線形リストでオブジェクトを繋ぐ。
- レジスタ内を走査してマークする。
- 繋いだ線形リストからマークの無い未使用のオブジェクトを開放する。
前回はここまで。
では、いつGCをするのか考える。
GCのタイミング
コードリーディングから、オブジェクト確保時GCするのがセオリーっぽい事がわかったので、オブジェクト確保時にGCすることにします。
しかし、今のまま実装してしまうと毎回GCしてしまう事になるので、フリーリストを導入し、フリーリストが空になったらGCして、それでもフリーリストが空ならばmallocすることに。
というわけで、フリーリスト作り
オブジェクト開放時に、オブジェクトとデータという構造体を2個管理しなければならないのは大変なので、
完全に分離しないで、(オブジェクト+データ)という単位ごとにフリーリストを作っておくことにした。
(オブジェクト+データ)という単位で扱えば、フリーリストは配列で作れる。
object gc_free_objects[TYPE_LENGTH];
かなりらくちん管理だ。
フリーリストの枯渇
作っていくと問題がいろいろ。
フリーリストの枯渇状態が続くと、
> (+ 1 2 3 4 5 6 7 8 9 10) gc... gc... gc... gc... ...
いっぱいGCしてしまう。
問題は、フリーリストが無くなったら、オブジェクトを１個しか確保しないことにある。
1個使ってしまうので、またGCが必要になる。という連鎖が起こってしまう。
そこで、メモリの確保要求が来たら、少し余分にフリーリストに貯めておくことにする。
改善後は、リストの枯渇、シンボルの枯渇、数値の枯渇で、GCは3回に抑えられた。
レジスタに繋がっていない状態のオブジェクト
もうひとつの問題。
レジスタに繋がっていないオブジェクトが存在した状態でGCが走ると、繋がっていないオブジェクトは全て破棄されてしまう。
例えば、consするとき
value = cons(1, cons(2, cons(3, value)));
(valueはSchemeレジスタ、数は数オブジェクトとする)
と、チェーンでconsしてしまうと。
value = cons(1, cons(2, cons(3, value))); // ↑GCが走ると ↑破棄される
途中のconsはレジスタに繋がっていないので、破棄されてしまうオブジェクトが発生する。かなり大問題。
GCを正しく行うには、
args = 3; value = cons(args, value); args = 2; value = cons(args, value); // GCしてもレジスタに繋がってるから安心 args = 1; value = cons(args, value);
と、Schemeレジスタに必ず繋がった状態を保ちながらconsする必要がある。
書き換えが面倒なので、GC禁止フラグを立てて対処してみた。
