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

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

私に教えられることなら

ForthでMarkCompactGC

forth gforth

VMに手を入れず、ForthのみでMarkCompactGCをやろうと思い立った。多分できました。

github.com

まだ全然使うことを想定して作っていません。あくまでも「できるものなんだな」程度に見て下さい。ここからバグ潰して整備するのはとても苦労しそう。

gforth-0.7.0、64bit版のみで動くと思います。まあcellが8byteならokなはず。標準的なワードしか使ってないのでそこそこいろんな処理系にも移植しやすい……はず

いつもどおり、以下は自分の振り返り用のメモ。

使い方

include ./markcompact.fsなどで使える。とりあえずgforthに渡せば使える。

  • 中身がGC対象になるArray
  • ならないByteArray

の2種類のオブジェクトを作れる。Arrayはセル数を、ByteArrayはバイト数を指定して作る。

スタックに乗っている、もしくは:ovar fooで宣言したfooにobj foo !と保存するとGCから逃れられる。

例えば以下のコードだと

    :ovar test-ovar
    16 create-array drop
    15 create-array drop
    14 create-array ( keep #1 )
    12 create-byte-array drop
    10 create-array test-ovar ! ( keep #2 )
    garbage-collect

スタックに乗ったままの#1、オブジェクト変数(ovar)のtest-ovarに保存された#2はgarbage-collectを生き残る。

Arrayを使用したCons Cell(Linked List)の定義は以下のようにできる

: cons  ( b a -- [a|b] )
    2 create-array  swap over  ( b xs a xs )
    0 at!                      ( b xs )
    dup -rot                   ( xs b xs )
    1 at! ;

: car   ( xs -- x )  0 at@ ;
: cdr   ( xs -- x )  1 at@ ;
: car!  ( x xs -- )  0 at! ;
: cdr!  ( x xs -- )  1 at! ;

その他mapなどのワードを作って、以下のようなコードが動く。

: inc-print 1 + dup . ;  \ for test2

    null 1 cons 2 cons 3 cons 4 cons 5 cons
    ' inc-print map cr
    ' inc-print map cr
    ' inc-print map cr
    ' inc-print map cr
    ' inc-print map cr
    drop cr

実行結果

2 3 4 5 6 
3 4 5 6 7 
4 5 6 7 8 
5 6 7 8 9 
6 7 8 9 10 

またByteArrayを用いた文字列も作った。この「GCされる断片化しない可変サイズオブジェクト」が一番やりたかった。

いい名前が浮かばないので$tringと呼ぶ。実装はメモリ操作だらけなので省略。

s" foo" >$  \ 文字列オブジェクト "foo"
s" bar" >$  \ 文字列オブジェクト "bar"
$+          \ 2つを結合して新たな文字列オブジェクト "foobar" を作成
dup $type   \ => foobar
$len .      \ 6

辞書にデータ残らないのでREPLでも気楽に使える。

実装

VMに手をいれないということで、タグ付きポインタなど使ってExactGCをやることはできない。なのでMark&Sweepを書いたときみたいに、スタックと専用変数でのConservativeGCでやった。

ConservativeGCなのでコンパクションの際にそのままForwardingはできない。なのでオブジェクトテーブルを使った。create-objectの時に返されるのはテーブルのエントリアドレスで、そのメモリから間接的にオブジェクトの真アドレスを取得する。Arrayからの参照もテーブルを介してなので、全ての参照についてForwardingする必要は無い。テーブルエントリを書き換えるだけでいい。

マークはオブジェクトのヘッダに行う。オブジェクトのヘッダは

  • サイズ
  • 自分を指すエントリ(のオフセット)
  • マーク
  • Array/ByteArrayフラグ

を持つ。

専用変数は単純にリンクリスト。宣言時に2セル確保し、片方をリンク用に使う。

感想

オブジェクトテーブルは楽だなあ。

AmeLispGC実装どうしようかとガベージコレクションのアルゴリズムと実装を読んでて、とにかくForthでやりたくてたまらなくなったのでやった。わかりやすくていい本だ。

書いてる最中は辛い辛い言ってたけど、GCの練習にはメモリを直接いじれるForthは楽かもしれない。まあ、他のとこが辛いんだけど……

それからツイッターで書いてたように、今回は紙での設計、それも落書きから始まって、ラフスケッチを繰り返してから取り掛かった。物凄く楽だったので今後ともこのやり方でやりたい。これについてはまた今度書こう。

広告を非表示にする