#関数型なんたら でGCの話を聴いて、SML#のGCの論文を読んで色々感じたのでエントリー。

Snapshot GC

まず、湯浅先生のSnapshot GC (解説)。並列、並行、インクリメンタルにGCが出来る。恐らく一番性能が出るとのこと。解説ではmark & sweepだけど私が聴いたのはCopyingだった。

勿論並行にするにはライトバリアが必要なんだけどその辺にまつわる話。並行じゃなくても世代別GCでもライトバリアが必要になるからその辺も頭に入れて聴いてほしい。Copyingはアロケーションが鬼のように速いのが特徴。mallocの感覚でメモリ確保が重いとか思ってると感覚が狂う。なので新たなオブジェクトを作るコストは非常に低い。そこにオブジェクトの変更にはライトバリアが付くとなると、大きくないオブジェクトの場合 オブジェクトを変更するより新たに作った方がコストが低くなる 。一応言っておくと、Copying GCの負荷は 生きている オブジェクトの数に比例するのでゴミオブジェクトを大量に作ったところでそんなにGCの負荷は高くならない。勿論、GCの頻度は上がってしまうが。それも世代別GCなら軽いGCが走るだけなので回数が増えてもそんなに負荷にはならない。

つまるところ 関数型スタイルでプログラムを書いた方がパフォーマンスが上がる ことがある。素晴しい。逆にこのような理由から関数型言語ではCopying GCを使うことが多い。

ただ、全ての場合で速くなる訳ではない。Copying GCはオブジェクトを移動するため、オブジェクトのアドレスが変わる。普通の参照ならGCのアルゴリズムが書き換えてくれるのだがそうはいかないのがハッシュ。ハッシュは多くの場合オブジェクトのアドレスをハッシュ値に使うため、GCが走ったらハッシュ値の再計算が必要になる。しかもハッシュの操作には破壊的なものが多いため、ライトバリアの影響も受ける。その場合、 ハッシュマップよりもツリーマップの方がパフォーマンスが出る ことがある。勿論、アルゴリズムのオーダが違うので要素数がケタ違いに大きくなるとハッシュに軍配が上がるが、通常そこまで要素を入れない。ようやく関数型言語でツリーマップが使われる理由が分かった。

Bitmap GC

関数型言語と相性の良いCopying GCだけど問題もある。Stop the Worldの話は世代別化やらそれこそSnopsht GCでどうにでもなるからそれはいい。Copying GCに本質的な問題。オブジェクトのアドレスの問題。GCが走ると現在のポインタが無効になる。処理系内部だけならまだ開発者が頑張れば良いんだけどC拡張を許すとそうもいかない。普通のポインタの問題だけじゃなくて構造体にポインタがあったら、とかそもそも外部ライブラリの内部のポインタをとか考えてるとどこかで割り切る必要がある。

そのためユーザにC拡張を気持ち良く使わせようと思うとCopying GCではつらい。Mark & Sweepが現実的な選択肢になる。が、そうすると今度はパフォーマンスに問題が出る。特にフラグメント化の問題は関数型スタイルが天敵である。じゃあ、Mark & Sweepの性能を改善しようというのがBitmap GC。

概要はMark & Sweepがオブジェクトにマークを付けるのに対してオブジェクトとマークを別にしてマークだけbit列で管理すると局所性が上がって良いよねというもの。詳しくは最初に上げた論文を参照して欲しいが一応解説。

局所性が上がるとはいっても単にキャッシュが効くとかではない。ビット列になることでCPU命令で操作出来るようになって$O(n)$が$O(n/32)$になったりする。そして何より、Mark & SweepじゃなくてSweep & Markになる。Sweepはビット列を0で埋める論理削除。ほぼ一瞬。なので実質Markのコストしかかからない。

構成

勿論、ただのbit列でオブジェクトの生死を管理するにはヒープをサイズ毎に用意する必要がある。8bitのオブジェクト用のサブヒープ、16bitのオブジェクト用のサブヒープ…という風に。そしてそれぞれのヒープ毎にビットマップをつける。ただそれだと無限に大きいサイズのヒープが必要になるのでどこかで切ってそれ以降は普通のMark & Sweepで管理するらしい。因みにSML#では4096bitが上限。32bit専用アーキテクチャなので64bitだと少し違うのかもしれない。以下、32bitアーキテクチャを仮定する。64bitでも適切に読み替えれば問題ない。

サブヒープはセグメント列とアロケーションポインタからなる。アロケーションポインタは次にアロケートすべき場所を差す(セグメント、ブロック、bitmap tree(後述)の情報)。

セグメントはオブジェクト数、ブロック列、ビットマップ、作業領域を持つ。ブロックというのが実際のオブジェクトが入る場所。8bitのサブヒープなら8bitのオブジェクトが入る。1セグメントに含まれるブロックの数は事前に決められている。要はコンパイル時なり起動時なりのパラメータになる。勿論、サブヒープ毎にブロック数をいじることになる。

ビットマップはただのビット列ではない。ただのintの列にするといくらCPU命令を使っても次の空いている場所を捜すのに$O(n/32)$かかってしまう。そこでbitmap treeで管理する。bitmap treeは親ビット列のi番目のビットが1のとき、i番目の子ビット列がfullである。ここでfullとは末端なら対応するブロックが使われている、それ以外なら子ビット列が全て1であるということである。これで次の空いているブロックを$Ω(log_{32} n)$で見付けることが出来る。同じワード内にあって適切なCPU命令があれば$O(1)$で済む。

アロケーションは先に出てきたアロケーションポインタの先が使われているか判断して、空いてれば先にデータを書き込んでアロケーションポインタをインクリメントするこのとき、特にbitmap treeは変更しない。空いてなければ空きブロックを捜す。空いてなければ次のセグメントに移って繰り返す同じ操作を行なう。最後のセグメントならセグメントプールに新しいセグメントを要求する。それももらえなければGCが走る。この辺はホットスポットらしいので色々テクニックが詰まっている。詳しくは論文を参照して欲しい。

GCは先に述べたように全てのサブヒープの全てのセグメントのbitmap treeを0で埋めることから始まる。そしてこれでSweep完了。

Markはまずrootノードについて、対応するbitmap treeを1にして、セグメントのオブジェクト数をインクリメントし、作業領域のトレーススタックに積む。あとはトレーススタックの中身の参照先をを順に同様に処理していけば良い。既にMarkされているオブジェクトは単に無視する。空になったセグメントはセグメントプールに返して、fullなセグメント(オブジェクト数=1セグメント毎のブロック数 なセグメント)はセグメント列の先頭に持ってくればアロケート時に無駄に探索されることはない。そしてアロケーションポインタを最初の空きブロックを差すようにすれば良い。

オブジェクトをサイズ毎に管理することでSweepを論理削除で済ませているところが良い。

世代別化

論文には世代別化の話もある。ライトバリアが必要なのは一緒だけど世代の管理が面白かった。安直には世代毎にサブヒープを分ける方法が思い付くが、それだとオブジェクトの移動が発生する。論文では世代毎にbitmap treeを持っている。ある世代のbitmap treeはその世代とそれより古い世代全ての生きているオブジェクトのbitmapになっている。

ある世代をsweepしたければ一つ古い世代のbitmap treeで上書きすれば良い。

ある世代のMarkは生存回数をインクリメントし、その世代のbitmap treeにMarkする。生存回数が閾値を越えたら上の世代にもMarkする。

全て完了したら若い世代達にも反映する(どう反映するかは論文には載ってない。差分をとって…とかかな？)。面白いのはある世代狙い撃ちでGC走らせられる点。あるいはいくつかの世代でも可能だろう。多くのアルゴリズムはある世代"以下"な気がする。これによって、マイナーGCでダメならミドルGCして、それでもダメならメジャーGCしてってなってたのが若年、中年、高年で別々に可能になる。まあ、ライトバリアの数がものすごいことになるからやらないだろうけど。なんでかっていうと若い世代から古い世代への参照もトレースする必要が出てくるから。論文に詳しく載ってないのはそんなに多くの世代を作っても現実的でないからだろう。勿論、ある世代以下を全てsweepも出来るので普通はそうする筈。

リメンバーセットとライトバリア

さて、さっきからライトバリアの話は出てたのに具体的になんなのかが出てこなかった。

世代別GCでは、マイナーGCが動くときに旧世代から新世代への参照があればその新世代のオブジェクトは生きているのでマークしなければならない。その「参照されている」ことを覚えておくのがリメンバーセット。GCされた後どうなるかは資料が見付からなかったけど旧世代に移ったものやGCされたものを取り除くんじゃないかな。

ライトバリアは調べたところ、多義的である。オブジェクトの参照を変更するときにごにょごにょするもの全般をライトバリアと呼んでいるようだ。Snapshot GC(並行GC)の場合はマーク中に変更された参照の先のオブジェクトもマークしていくことのようだし、RGenGC(インクリメンタル GC)はマーク中に変更された参照の元オブジェクトをグレーにすることのようだし、世代別GCではさらに色々意味がある。

世代別GCでのライトバリアは、全ての参照を変更する操作にフックして動く。そしてリメンバーセットを更新する。そこまでは皆共通している。そこからは、

• 旧世代オブジェクトから新たに参照された新世代オブジェクトをリメンバーセットに加える
• 変更されたオブジェクトをリメンバーセットに加える
• 変更されたオブジェクトを、旧世代オブジェクトならリメンバーセットに加える

などのバリエーションがある。それ以外にもありそう。尚、どれも正確ではない。つまり本来なら死んでいるオブジェクトも生き残る可能性がある。

正確にやろうと思えばリメンバー"マップ"を用意し、[新世代オブジェクト]->[旧世代からの参照数]を保持し、参照カウントを行なえばいけると思う。

そこまでやらないのは性能に問題があるからかな。あとそもそも世代別GC自体正確にはオブジェクトを回収しないから正確にやってもあまり意味がないのもある。

Sticky Mark世代別化

Sticky Mark世代別GCというのは世代別GCを世代2つ、生存回数の閾値1とするときの簡単な実装方法。本当に簡単で、前回のMarkを残しておけば良い。それが旧世代の目印になる。あとはライトバリアとリメンバーセットを用意するだけ。元々Markのときに既にMarkされているオブジェクトはスルーされるのでアルゴリズムはほぼ変更が要らない。普通のMark & Sweepでも出来るし、Bitmap GCでもアロケーションのときにbitmap treeをいじってないのでbitmap treeを0にする処理をしなければ良い。

さらに、リメンバーセットに関しても簡単になる。全てのオブジェクトが旧世代になるのだからリメンバーセットはクリアするだけで良い。あるいはGC毎に消えてしまうデータに格納してしまっても良い。SML#ではトレーススタックに積むことでリメンバーセットとしているようだった。何も考えなくてもGCのときにルートノードとして扱われる。重複判定に関しては読み解けなかった。

以下、書いてあるところの引用。最初の this factというのはリメンバーセットについて簡単になるということ。Tworkというのが作業領域。

Taking advantage of this fact, we allocate a re- membered set in the collector’s trace stack. As mentioned before, our trace stack is implemented as a linked list using Twork work areas. This is done by assigning a unique pointer slot in Twork to each object. This implementation allows us to determine whether a given object is already in the list or not by checking whether the pointer is non-null. This automatically eliminates duplication in the remembered set. A write barrier can then be incorporated in the generational collector as follows. A write barrier code takes a young object that is to be referred from the old generation due to mutation, and marks it and pushes it to the trace stack. Minor collector simply traces objects using the trace stack whose initial contents is the remembered set

誰か分かる人教えて下さい。

複数mutater対応

要はアプリケーションでスレッドを使ったときの話。1スレッドにつき1セグメント割り当てて新たなセグメントを確保するときだけロックとればアロケーション速いよねって言ってる。GCはStop the Worldしないようにするとか言ってるけど出来るのかな。

パフォーマンス

Bitmap GC、sticky bit世代別Bitmap GC、シンプルなCopying GC、2世代、5世代の世代別Copying GCでの比較が載ってる。Copying GCは2世代が最もパフォーマンスが良く、世代別Bitmap GCもそんなに負けてない。少くともシンプルなCopying GCには勝ってる。アロケーションは及びもつかないものの、世代別Bitmap GCはGCのStop the Worldは圧倒的に短いみたい。

picrinの話

picrinのGCは超シンプルなMark & Sweep。んで、picrinのボトルネック。どうにかしたい。先述の理由からMark & Sweepなのは維持なんだけどどう拡張しようねという話。

ライトバリアさえ実装してしまえばSticky Markで簡単に世代別化出来る。もうちょっと言うとライトバリアだけのデバッグが出来る。そしてまともな世代別化につながる。でもライトバリア->Bitmap化だとライトバリアも書き換える必要が出てきてあまり宜しくない。

Bitmap化すれば速くなるっぽい。が、メモリ管理を大幅に書き換える必要がある。特にサイズ別に管理するところ。でもそこからさらにSticky Markとかでさらに拡張可能。

うーん。個人的にはBitmap化してみたいんだけど完全に独自メモリ管理になっちゃうからなー。