読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

ForthでMark&Sweep GC書いた

forth

前にも1度C言語挑戦したんだけど、何かこう自分で何やってるのかよくわからん感があったので、メモリを直に触れるForthでMark&Sweep GCに挑戦し直した。

コード

設計

Forthの辞書構造を活かしたままGCをやるのは多少難しいというか、辞書全部を保守的にやるのは大変難しそうだ。おそらく1セルごとにフラグを追加、アライメント整備など根本的に変える必要がある。何ヶ月かかるかわからない。

なので、今回はConsセルに限定して、

  • スタックとセル内リンクは保守的GC
  • 別にセルを保持する専用変数の宣言cvar:を作り、それはExactGC

でやることにした。

処理系は最近作ったSTCのRFR64で書いたけど、マシンコード依存なことはせずForthのみで書いたので、ITCやDTCにも簡単に移植できると思う。

セルの構造は1バイトのフラグと8バイトのcar部、cdr部にして、1セル17バイトになった。nilの存在すっかり忘れてて、気づいたのがmap書き始めてからだったので、面倒になってセル領域かどうかで判定するようにした。次やるときはnilフラグが立ったセルを1つ作ればいい、のかな……?

ほか、特に変わったことはしてないし、わざわざ落としてmakeして試すのも面倒だろうし、ということで実行結果など貼って終わりとする。

次はCopy GCなんかもやってみたいけど、更に難しそうだ。。

gc-test

: gc-test  ( -- )
   1 2 cons 3 cons 4 cons ( 3セル確保 )
   ." BEFORE GC" cr dump-cells
   MAX-CELLS  dotimes  drop new drop  end  drop  dump-cells
   MAX-CELLS  dotimes  drop new drop  end  drop  dump-cells
   drop gc dump-cells ;

3セル確保してスタックに置き、1領域確保しては捨てる、を繰り返してGCの発動を見る。最後に最初に確保した3セルもスタックから捨てて強制GC、その分が回収されたかも見る。

長いから全部貼らないけど、最初はこんなカンジで

gc-test
BEFORE GC
25685621   FLAG:1 CAR:2 CDR:1 
25685638   FLAG:1 CAR:3 CDR:25685622 
25685655   FLAG:1 CAR:4 CDR:25685639 
25685672   FLAG:0 CAR:0 CDR:0 
25685689   FLAG:0 CAR:0 CDR:0 
25685706   FLAG:0 CAR:0 CDR:0 
25685723   FLAG:0 CAR:0 CDR:0 
25685740   FLAG:0 CAR:0 CDR:0 
25685757   FLAG:0 CAR:0 CDR:0 
25685774   FLAG:0 CAR:0 CDR:0 
25685791   FLAG:0 CAR:0 CDR:0 
25685808   FLAG:0 CAR:0 CDR:0 
25685825   FLAG:0 CAR:0 CDR:0 
25685842   FLAG:0 CAR:0 CDR:0 
25685859   FLAG:0 CAR:0 CDR:0 
25685876   FLAG:0 CAR:0 CDR:0 

GC START
unmark-all success
Vars  marked. empty:16 
    marked: 25685655 
    marked: 25685638 
    marked: 25685621 
Stack marked. empty:13 
mark-refed success
GC COMPLETE

25685621   FLAG:1 CAR:2 CDR:1 
25685638   FLAG:1 CAR:3 CDR:25685622 
25685655   FLAG:1 CAR:4 CDR:25685639 
25685672   FLAG:1 CAR:0 CDR:0 
25685689   FLAG:0 CAR:0 CDR:0 
25685706   FLAG:0 CAR:0 CDR:0 
25685723   FLAG:0 CAR:0 CDR:0 
25685740   FLAG:0 CAR:0 CDR:0 
25685757   FLAG:0 CAR:0 CDR:0 
25685774   FLAG:0 CAR:0 CDR:0 
25685791   FLAG:0 CAR:0 CDR:0 
25685808   FLAG:0 CAR:0 CDR:0 
25685825   FLAG:0 CAR:0 CDR:0 
25685842   FLAG:0 CAR:0 CDR:0 
25685859   FLAG:0 CAR:0 CDR:0 
25685876   FLAG:0 CAR:0 CDR:0 

最後、全部解放後はちゃんとFLAGが0、利用可能になっている。

GC START
unmark-all success
Vars  marked. empty:16 
Stack marked. empty:16 
mark-refed success
GC COMPLETE

25685621   FLAG:0 CAR:2 CDR:1 
25685638   FLAG:0 CAR:3 CDR:25685622 
25685655   FLAG:0 CAR:4 CDR:25685639 
25685672   FLAG:0 CAR:0 CDR:0 
25685689   FLAG:0 CAR:0 CDR:0 
25685706   FLAG:0 CAR:0 CDR:0 
25685723   FLAG:0 CAR:0 CDR:0 
25685740   FLAG:0 CAR:0 CDR:0 
25685757   FLAG:0 CAR:0 CDR:0 
25685774   FLAG:0 CAR:0 CDR:0 
25685791   FLAG:0 CAR:0 CDR:0 
25685808   FLAG:0 CAR:0 CDR:0 
25685825   FLAG:0 CAR:0 CDR:0 
25685842   FLAG:0 CAR:0 CDR:0 
25685859   FLAG:0 CAR:0 CDR:0 
25685876   FLAG:0 CAR:0 CDR:0 

ExactGCとmap

こんなカンジで、生成したセルを変数takoに保存する

1 2 cons 3 cons 4 cons 5 cons  cvar: tako

tako first . cr
( => 5 ) 

tako third . cr
( => 3 ) 

次に、map用のワードを作っておいて

: a  ( x -- x ) . 999 ;
: b  ( x -- x ) . 111 ;

これらをセルにmapすると、新たに全ての値が999や111になったセルが生成される。

aをmapしてみる。

tako ' a map cr
( => 1 2 3 4 5 )
.s
( => 25685741  新しく生成されたセルの先頭アドレス。フラグ1バイトの次。 )

で、dump-cellsで中身を見ると、新しいセルが生成されてるのがわかる。

25685621   FLAG:1 CAR:2 CDR:1 
25685638   FLAG:1 CAR:3 CDR:25685622 
25685655   FLAG:1 CAR:4 CDR:25685639 
25685672   FLAG:1 CAR:5 CDR:25685656 
25685689   FLAG:1 CAR:999 CDR:999 
25685706   FLAG:1 CAR:999 CDR:25685690 
25685723   FLAG:1 CAR:999 CDR:25685707 
25685740   FLAG:1 CAR:999 CDR:25685724 
25685757   FLAG:0 CAR:0 CDR:0 
25685774   FLAG:0 CAR:0 CDR:0 
25685791   FLAG:0 CAR:0 CDR:0 
25685808   FLAG:0 CAR:0 CDR:0 
25685825   FLAG:0 CAR:0 CDR:0 
25685842   FLAG:0 CAR:0 CDR:0 
25685859   FLAG:0 CAR:0 CDR:0 
25685876   FLAG:0 CAR:0 CDR:0 

何回かデタラメにaとbをmapし、GCを発動させる。その後、最後に生成されスタックに残ったセルと、最初にcvar:で保存したセルのフラグが1のまま生き残っていることを確かめる。

' a map ' b map ' a map ' b map
( => 999 999 999 999 999 ... 途中でGCが発動する )

最後に強制gcをかけて、dump-cellsで残ったセルを確認する。

gc dump-cells
GC START
unmark-all success
    marked: 25685672 
    marked: 25685655 
    marked: 25685638 
    marked: 25685621 
Vars  marked. empty:12 
    marked: 25685808 
    marked: 25685791 
    marked: 25685774 
    marked: 25685757 
Stack marked. empty:8 
mark-refed success
GC COMPLETE

25685621   FLAG:1 CAR:2 CDR:1 
25685638   FLAG:1 CAR:3 CDR:25685622 
25685655   FLAG:1 CAR:4 CDR:25685639 
25685672   FLAG:1 CAR:5 CDR:25685656 
25685689   FLAG:0 CAR:999 CDR:999 
25685706   FLAG:0 CAR:999 CDR:25685690 
25685723   FLAG:0 CAR:999 CDR:25685707 
25685740   FLAG:0 CAR:999 CDR:25685724 
25685757   FLAG:1 CAR:111 CDR:111 
25685774   FLAG:1 CAR:111 CDR:25685758 
25685791   FLAG:1 CAR:111 CDR:25685775 
25685808   FLAG:1 CAR:111 CDR:25685792 
25685825   FLAG:0 CAR:111 CDR:111 
25685842   FLAG:0 CAR:111 CDR:25685826 
25685859   FLAG:0 CAR:111 CDR:25685843 
25685876   FLAG:0 CAR:111 CDR:25685860 

スタックと変数にそれぞれ4セルずつ生き残っていることが確認できる。

おわりに

今回は書く時に、トップダウンボトムアップの組み合わせを意識してみた。

ワードgcではとりあえずmark&sweepってワードを実行だな、mark&sweepではunmark-allしたあとmark-refedして……とスタブワードをどんどん作っていった。

途中で「これ一気に書き上げたあとバグ見つけるの地獄なんじゃ……」と段々ハラハラして、まあ正直なかなか自分にとっては難しいバグが出たんだけど、Forthのワードの定義しやすさと、パーツごとの試しやすさのおかげでドーパミンに駆動されてガンガン書けていけた。

意外に早くできたし、楽しかったんだけど、多少体力を必要とする書き方ではある気がする。最初の一歩、ノリ始めるまではやっぱりボトムアップが良さそうだ。

それから、これを作るために、いろいろと必要なライブラリを整備せざるを得なかったのも良かった。必要は発明のナントカだなあ。

あとインタラクティブ開発とフィードバックを重視した方がいい。イイネ。GCのログとかセルのダンプ綺麗に表示して上手くいってるの見るとかなり興奮した。Forth内でいろいろメモリ操作してバグの原因突き止めたときは脳内で何かがドバドバ出て大変良かった。またいろいろやりましょう。

広告を非表示にする