hs2bf - GC - ⊥=⊥

ようやくGC(とλ-liftingとletrec)を実装しました。今回はその説明です。

λ-lifting

適当に名前を付けてグローバルにして、自由変数を与えるだけです。(Haskellは自動カリー化、というより全ての関数が1引数をとるので)

letrec

letrec
 x=f x y
 y=g x y
in h x y

のような式は、まずx,y用にダミーのノードを確保して(アドレスを作って)、f,gが呼び出してから書き換える必要があります。

普通は間接参照用のノードを追加するところですが、今回は本当に全てのアドレスを書き換える実装にしてあります。

GCの動作

今のところ、ヒープの構成はは次の(可変長)のレコードが先頭から密に並んでいます。

1B: ノードサイズ
1B: reachableフラグ(0:unreachable 1:reachable)
1B: 種類(関数適用,コード片id,構造体,定数)
*: ペイロード
1B: ノードid
1B: ノードサイズ

これを踏まえて動作を説明します。

transfer

HpriからHsecにそのまま移動します。このフェーズはGC終了後のヒープの裏表を元と一致させるために入れています。

終了後は:

Hpri: 0
Hsec: ヒープ
S0: スタック

mark

Hpriをスタックとして、Hsec内のreachableノードをマークしていきます。

Hpri<-S0
Hpriが空なら終了
Hpriからひとつ取り出して、参照するHsecの位置に移動
1. reachableが1ならば何もしない
2. reachableが0ならば1にして、参照しているアドレスをHpriにpush
2に戻る

終了後は:

Hpri: 0
Hsec: ヒープ(マーク済み)
S0: スタック

copy

Hsecの先頭から順番にreachableが1ならばHpriの末尾に追加する。
このときノードidを古いままコピーするのが重要。

Hpri: ヒープ(new)
Hsec: dirty
S0: スタック

index

Hpriの先頭から数えつつ(これが新しいidになる)、古いidを得る。Hsecのold_id番目にnew_idを書き込む。

Hpri: ヒープ(new)
Hsec: table(未使用部はdirty)
S0: スタック

rewrite

Hsecを使ってHpriとS0内のアドレスを書き換える。

ステップ数比較

今使っている以下のテスト用コードについて、実行に要するステップ数を比較してみました。

-- Halt.hs
main=Halt

-- Const.hs
main=Output '~' Halt

-- ExplicitCase.hs
data Test
    =Foo Char
    |Bar
    |Baz

main=case Bar of
    Baz -> Output 'x' Halt
    Bar -> Output 'o' Halt
    Foo x -> Output '*' Halt

-- Hello.hs
main=outputStr Halt "Hello World!"

outputStr k []=k
outputStr k (x:xs)=Output x (outputStr k xs)

-- LocalFun.hs
main=f '~'
    where f x=Output x Halt

-- Lambda.hs
main=(\x y->Output ch x) Halt main
    where ch='A'

	Halt.hs	Const.hs	ExplicitCase.hs	Hello.hs	LocalFun.hs	Lambda.hs
GC無し	34103	343260	655398	1051859235	2632572	4748450
GC有り	72080	753975	1134942	2696838584	4187121	6932535
増加率	+111%	+120%	+73%	+156%	+59%	+46%

今のところ関数呼び出し1回ごとにGCを1回動かしているので、妥当な値だと思います。最適化の余地もかなりありそうです。
(ちなみにこのGCはノード数の2乗に比例した時間を使っています)

今のところの感想

G-machineコードの変換先で、GCの書かれているSAMはアセンブリに毛の生えたような言語なので、手書きするとかなりバグが出ます。
よく考えずに抽象化してしまうと、重要な最適化の機会を逃してしまったり、後で機能追加しようと思ったときにその枠組みで扱えない、ということになるので
なかなか難しいところです。