コピーイングGCに挑戦

#久々Lisp
自作Lisp処理系のEasy-ISLisp（以下　EISL)についてコピーGCを追加しました。前からGCのことをもっとよく理解したいと思っていました。従来のマーク＆スイープに追加でコピーイングGCを入れました。後日のために書き記します。

#セル構成
セルはCの構造体配列で確保しています。20,000,000個を確保しています。（このサイズですとラズパイでもコンパイル、動作可能です）

ここでは便宜上、この配列の添え字のことをアドレス（番地）と表現することとします。

マーク＆スイープのときにはこれを全部ヒープ領域として使用しています。コピーイングGCのときには次のように分割して使用します。

アドレス　０～5,999,999　ヒープ領域
アドレス　6,000,000～12,999,999　ワーキング領域１
アドレス　13,000,000 - 19,999,999 ワーキング領域２

コピーイングGCでは２つの領域で交互にコピーをして利用します。ワーキング領域1,2はこのためのものです。ヒープ領域はシンボル、SUBR、FSUBR、入出力ストリームなどコピーを要しないものを保存します。ユーザー定義の関数、総称関数もここに保存します。コピーの対象とはしません。


#コピーする

○タイミング
上記の領域はwp（ワーキングポインタ）で管理しています。大域変数areaでワーキング１，２のいずれかがカレントなのかを記憶しています。wpの値から残りのセルが一定数以下となったときにGCを起動します。

○コピーするもの
コピーするものは局所環境、動的変数環境、などです。シンボルはヒープ領域にありコピーの対象ではありません。しかし、そのcar部とcdr部には関数定義と大域変数の値が束縛されています。これは新たにコピーされたものの番地に置換します。もっともcar部に接続されている関数定義はコピーをしなくてもいいようにヒープ領域に保存してあります。

○留意点
注意すべてはevalが実行中にGCを起動する場合です。evlis（引数を評価する部分）の実行中にGCがかかると値がコピーされたものに置き換えられてしまいます。これはargstackというスタックで管理しています。従来、マーク＆スイープの時にはこの値をマークすることによりスイープさせずに値を保持していました。コピーイングGCではこの値はコピーされた新たな値に置換されます。argstackからpopすることにより途中、GCが起きた場合に対処しています。

○縦型探索
コピーすべきオブジェクトは縦型探索でみつけてコピーしています。


#使用法
起動直後はマーク＆スイープになっています。gbc関数に与える引数によりこれを切り替えることができます。

```
gbc('copy)   コピーイングGCに切り替える

gbc('m&s) 　マーク＆スイープに切り替える。

```


#ベンチマーク
竹内関数、たらいまわし関数でテストしました。インタプリタは小整数につき即値とはしていません。このため大量の小整数セルが生じますのでGCのテストにうってつけです。

```
Easy-ISLisp Ver1.4
> (load "tarai.lsp")
T
> (time (tarai 12 6 0))
enter M&S-GC free=43
exit  M&S-GC free=19997344
enter M&S-GC free=48
exit  M&S-GC free=19997358
enter M&S-GC free=48
exit  M&S-GC free=19997302
enter M&S-GC free=47
exit  M&S-GC free=19997237
enter M&S-GC free=41
exit  M&S-GC free=19997259
enter M&S-GC free=41
exit  M&S-GC free=19997247
enter M&S-GC free=49
exit  M&S-GC free=19997315
enter M&S-GC free=41
exit  M&S-GC free=19997327
Elapsed Time(second)=13.120511
<undef>
> (gbc 'copy)
T
> (time (tarai 12 6 0))
enter COPY-GC free=47
exit  COPY-GC free=6999708
enter COPY-GC free=48
exit  COPY-GC free=6999680
enter COPY-GC free=45
exit  COPY-GC free=6999720
enter COPY-GC free=41
exit  COPY-GC free=6999774
enter COPY-GC free=49
exit  COPY-GC free=6999624
enter COPY-GC free=48
exit  COPY-GC free=6999585
enter COPY-GC free=48
exit  COPY-GC free=6999609
enter COPY-GC free=48
exit  COPY-GC free=6999666
enter COPY-GC free=44
exit  COPY-GC free=6999648
enter COPY-GC free=47
exit  COPY-GC free=6999659
enter COPY-GC free=41
exit  COPY-GC free=6999652
enter COPY-GC free=42
exit  COPY-GC free=6999587
enter COPY-GC free=48
exit  COPY-GC free=6999597
enter COPY-GC free=43
exit  COPY-GC free=6999654
enter COPY-GC free=42
exit  COPY-GC free=6999712
enter COPY-GC free=41
exit  COPY-GC free=6999727
enter COPY-GC free=42
exit  COPY-GC free=6999708
enter COPY-GC free=49
exit  COPY-GC free=6999771
enter COPY-GC free=47
exit  COPY-GC free=6999704
enter COPY-GC free=46
exit  COPY-GC free=6999697
enter COPY-GC free=41
exit  COPY-GC free=6999805
enter COPY-GC free=44
exit  COPY-GC free=6999691
enter COPY-GC free=48
exit  COPY-GC free=6999708
Elapsed Time(second)=12.103059
<undef>
> 

```


若干ですがコピーイングGCの方が速くなっています。これはコンパクションが行われ関連するセルの番地が近くなっていること、また、スイープを一気にやらなくてもよいので有利になってると思われます。


#LispとGC
昨今は言語処理系そのものにGCの機能があったり、Cに保守的GCのライブラリを付加することで自分でGCを書かなくてもよくなっています。しかし、LispとGCとは切っても切れない関係にあります。最初にGCが考案されたのはLispにおいてでした。実用的なGCを書くのは難しいですが、自分で作ってみることによりより深くLispを理解できるものと思います。お勧めです。

コードはgithubにおいてあります。

https://github.com/sasagawa888/eisl