Schemeをつくろう(19) GCの速度改善

Scheme

GCの速度を改善してみる。改善したのは2箇所。

一度巡ったオブジェクトは巡らない

ルートは違うけど、参照を共有してる

ペア-+--+->数字
U    |  |  U
ペア-+  +->ペア-+->数字
N          U    |  U
                +->NULL

2個目のペアを巡る場合、参照先ににフラグが立っていれば、以降はフラグが立っている事が保障されるので、最初の1個と参照先だけ巡ればいい。


一度巡ったオブジェクトは巡らなくていい。


循環参照してる場合も、

ルート -> オブジェクト -> オブジェクト
              A               |
              |               V
          オブジェクト <- オブジェクト

フラグが立っていれば、以降を見る必要が無いので、途中で処理を中断できる。循環参照してても安心です。

スイープ&フラグ

前回は、スイープするときに、

元の状態

ペア->ペア->数字->数字->ペア->NULL
U     U     U     U     N

スイープ

ペア->ペア->数字->数字->NULL
U     U     U     U

と、Nのフラグのあるオブジェクトの破棄をするだけだった。


空で回すのはもったいないので、スイープ時にNのフラグを立てちゃえという作戦。

ペア->ペア->数字->数字->NULL
N     N     N     N

Nフラグを立てるフェーズは要らなくなるよね！！

あ、新規にオブジェクトを追加するときもNフラグを立てておく。繰り返し回数が減って速度アップ！

まとめ

2つの改善で大幅な速度改善ができました。単体のマーク・アンド・スイープではデータ量が増えると速度が落ちるという根本的な問題があるので、どう克服していくかが鍵となりそうです。


マークフェーズではは参照を全て見る。みたいなイメージがあったけど、データ個分だけ見ればいいんですね。勉強になりました。