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

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ノードをマークしていきます。

  1. Hpri<-S0
  2. Hpriが空なら終了
  3. Hpriからひとつ取り出して、参照するHsecの位置に移動
    1. reachableが1ならば何もしない
    2. reachableが0ならば1にして、参照しているアドレスをHpriにpush
  4. 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はアセンブリに毛の生えたような言語なので、手書きするとかなりバグが出ます。
よく考えずに抽象化してしまうと、重要な最適化の機会を逃してしまったり、後で機能追加しようと思ったときにその枠組みで扱えない、ということになるので
なかなか難しいところです。