JHCのGC解説

Haskell GC

GC Advent Calendarでは時間的に書けなかった、JHCのGCの解説をまとめる。

JHCのGC概要


JHCには下記3つのGCオプションがある。

  • GCなし
  • BOEHM GC
  • JGC

このうち、上の二つはgc_noneによる実装であり、JGCはgc_jgcによる実装である。
この様な構成になったのは、JGCが後から追加されたためだと思われる。

gc_none の挙動


GCなし


アロケーションのために必要となるメモリ空間の確保は基本的にmallocで行われる。
mutatorへの割り当ては jhc_malloc と jhc_malloc_atomicの二種類の関数がある。

Boehm GC


BOEHM GCを使用するための実装(初期化等)も一部はここにあるようだ。

gc_jgc の挙動


JHCオブジェクトの基本構造


JHCの世界ではすべての値がポインタを介してアクセスされる。ポインタは次の4種類に分類される。なお、JHCの実行系内のポインタは下位2ビットがオブジェクト種別を識別するために使用されている。

下位2ビット GC対象のポインタを含むか？
P_WHNF 0x00 Yes 直値、関数値以外の値。
P_LAZY 0x01 Yes 遅延評価オブジェクト。値を含む。
P_VALUE 0x02 No 直値。16ビット、または30ビットの値でポインタではない。
P_FUNC 0x03 No 関数

JHCのメモリ領域はページ単位で管理されており、その先頭にあるのがS_BLOCK構造体。S_BLOCK構造体はオブジェクトのサイズによって微妙に内容が異なるが、ほぼ同じである。
なお、大きなオブジェクトを格納するページはMONOLITHIC BLOCKと呼ばれる。

struct s_block {
        SLIST_ENTRY(s_block) link;
        unsigned char flags;  // defined in rts/constants.h
        unsigned char color;  // offset in words to first entry.
        union {
                // A normal block.
                struct {
                        unsigned char num_ptrs;
                        unsigned char size;
                        unsigned short num_free;
                        unsigned short next_free;
                } pi;
                // A monolithic block.
                struct {
                        unsigned num_ptrs;
                } m;
        } u;
        bitarray_t used[];
};

s_block構造体のメンバーにusedというのがいるが、これがGC時のマークに使用されるビットである。MONOLITHICなブロックはusedのメンバーは常に一つである。

JHCのアロケーションシステムは独特の仕組みを持っている。

サイズによって

  • MONOLITHIC BLOCKから割り当てられたオブジェクト(150Byte～(4K-SBLOCKサイズ)まで)
  • キャッシュされた領域から割り当てられたオブジェクト(1～149Byteまで)

に大きく分けられる。

キャッシュは、サイズとポインタ数の組別に作られている。
割り当てを行う際はサイズとポインタ数の組から検索されるキャッシュを探す。
それぞれのキャッシュは双連結リストで管理されており、ある程度ヒューリスティックにソートされている。
実際の割り当ては、空きのあるブロックからUSEDビットの空きを探す形で実施される。

なお、キャッシュが使用するBLOCKはMEGA BLOCKSから割り当てて使用される。MEGABLOCK自体はmallocで確保される。(あえてmalloc?)

MONOLITHIC BLOCKは、MEGABLOCKとは別に、動的に確保／開放が行われる。(posix_memalignを使用)
実際のサイズにかかわらず、ページサイズが割り当てられるようである。(このため、巨大なオブジェクトは割り当てられなそう。)

GCの挙動


実際にGCが呼ばれた後の挙動を説明する。
1. すべてのオブジェクトのマークビットがOFFにされる。
2. ルート、および、StablePTRがマークされる。
3. ポインタをたどって、マークを付けていく。
4. 不要なMONOLITHをsweep/freeし、空のBLOCKをキャッシュ内のfree blocksにつなぐ。(MEGA BLOCKSの解放はしない)
5. 割り当てが速くなるよう、キャッシュ内のBLOCKの順序を整えて終了。

上記で特徴的なのは、MONOLITHIC BLOCKのオブジェクトには明示的なSweepフェーズがあり、ファイナライザを呼べるのに対し、キャッシュされたオブジェクトについてはSweepフェーズがない上にファイナライザもコールできないことである。また、usedビットは立てっぱなしにして、再割当て時の判定に使用する。(逆に言うと、再割当て時にはusedビットを再検索する必要がある。)

GCが呼ばれるタイミング


明示的に呼ばれる以外は使用中のブロック数が閾値以上になった時点で呼び出されるようだ。
ただし、GC実行後も閾値の90%以上のサイズを使用しているままの場合、閾値が2倍に増やされる。