GHC 6.10の新GC

 2008年6月17日にGHCの開発版に並列GC(Parallel GC)が実装されたので,早速手元でビルドして第11回のquicksort''関数を使って試してみました(参考リンク)。

import Control.Parallel
import Control.Parallel.Strategies

main = print $ quicksort'' ([0..10000]::[Int])

quicksort'' :: (Ord a, NFData a) => [a] -> [a]
quicksort'' []      = []
quicksort'' [x]     = [x]
quicksort'' (x:xs) = losort ++ (x:hisort) `using` strategy
      where
        losort = quicksort'' [ y | y <- xs, y < x]
        hisort = quicksort'' [ y | y <- xs, y >= x]
        strategy result = rnf losort `par`
                          rnf hisort `par`
                          rnf result

$ ghc ParallelTest.hs --make -threaded
[1 of 1] Compiling Main             ( ParallelTest.hs, ParallelTest.o )
Linking ParallelTest.exe ...

$ ./ParallelTest +RTS -N4 -sstderr
ParallelTest +RTS -N4 -sstderr
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29
~ 略 ~
,9998,9999,10000]
   2,284,305,164 bytes allocated in the heap
     222,969,748 bytes copied during GC
       1,461,776 bytes maximum residency (24 sample(s))
         257,252 bytes maximum slop
               6 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:  4155 collections,     0 parallel,  0.70s,  0.70s elapsed
  Generation 1:    24 collections,     3 parallel,  0.02s,  0.02s elapsed

  Parallel GC work balance: 1.12 (454149 / 404194, ideal 4)

  Task  0 (worker) :  MUT time:   0.73s  (  4.30s elapsed)
                      GC  time:   0.14s  (  0.14s elapsed)

  Task  1 (worker) :  MUT time:   0.38s  (  4.30s elapsed)
                      GC  time:   0.08s  (  0.08s elapsed)

  Task  2 (worker) :  MUT time:   0.03s  (  4.31s elapsed)
                      GC  time:   0.00s  (  0.00s elapsed)

  Task  3 (worker) :  MUT time:   0.00s  (  4.31s elapsed)
                      GC  time:   0.00s  (  0.00s elapsed)

  Task  4 (worker) :  MUT time:   1.95s  (  4.31s elapsed)
                      GC  time:   0.34s  (  0.34s elapsed)

  Task  5 (worker) :  MUT time:   1.22s  (  4.31s elapsed)
                      GC  time:   0.16s  (  0.16s elapsed)

  INIT  time    0.02s  (  0.00s elapsed)
  MUT   time    4.31s  (  4.31s elapsed)
  GC    time    0.72s  (  0.72s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    5.05s  (  5.03s elapsed)

  %GC time      14.2%  (14.3% elapsed)

  Alloc rate    527,781,698 bytes per MUT second

  Productivity  85.4% of total user, 85.7% of total elapsed

recordMutableGen_sync: 0
gc_alloc_block_sync: 1
whitehole_spin: 0
gen[0].steps[0].sync_todo: 0
gen[0].steps[0].sync_large_objects: 0
gen[0].steps[1].sync_todo: 3
gen[0].steps[1].sync_large_objects: 0
gen[1].steps[0].sync_todo: 52
gen[1].steps[0].sync_large_objects: 0

 第10回の出力結果と比べると,Generation *:のparallelやParallel GC work balance:などGCの並列性を表す項目が増えているのがわかりますね。最後に少しごみのような出力が付いていますが,おそらくデバッグ用の情報でしょう。開発版が実際にGHC 6.10としてリリースされる頃には取り除かれるはずです。

 Parallel GC work balance:のidealが,GCのスレッド数です。実行時システムの-N<n>オプションに渡したのと同じ4という値になっています。

 ここでは並列プログラムを実行しているため-N<n>オプションを与えていますが,並列に動くGCの数だけ別に渡すための-g<n>オプションも用意されています。このオプションを使うことで,全く並列化されていないプログラムでもGCの並列化によるマルチコアの恩恵を受けられるようになります。

 並列GCとは別に,古い世代のGCのために通常のコピーではなくマーク・リージョン(mark-region)方式を使用するための実験的な変更も取り入れられたようです。この機能は実行時システムの-wオプションで有効にできます。ただし,このGCはまだ並列化されていないようです(参考リンク1参考リンク2)。

 GHCに並列GCが取り入れられたといっても,それでGC改善の試みが終わるわけではなく,今後もいくつかの改良が行われていく見込みです。Haskellの進化をGCの改良という視点からながめるのも面白いかもしれませんね。

 GHCのGCについての情報は,GHCのマニュアルの中で,GCを制御するためのオプションについて書いている個所(参考リンク),およびThe GHC CommentaryGarbageCollectorNotesなどから得ることができます。興味のある方はGCアルゴリズム詳細解説Wikiを参考に,これらを眺めてみると良いでしょう。

 より詳細な部分について知りたい場合には,実際のGCの動作について書いてある論文を読むのが一番だと思います。GHCの開発版に実装された並列GCについては「Parallel Generational-Copying Garbage Collection with a Block-Structured Heap」(参考リンク)という論文に書かれています。マーク・リージョンGCについては「Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance」(参考リンク)という論文に書かれています。また,現在未実装のインクリメンタルGC(incremental GC)についても「Non-stop Haskell」(参考リンク)やそれに続く論文で書かれています。


著者紹介 shelarcy

 第18回の著者紹介で言及したwxHaskell 0.10.3のリリース以後も,wxHaskellの開発を続けています。しかし,2008年9月に発売予定の「Real World Haskell」の草稿では,どうやらGUIのプログラミングの説明にwxHaskellではなくGtk2Hsのみを扱っているようです。

 wxHaskellの開発者の1人として個人的にはこの状況を改善したいのですが,そのためにはGUIプログラミングの章の草稿(参考リンク)の内容に沿った機能の追加が必要になるようです。wxHaskellではこの機能は別の機能である程度代替可能なものであるため,仕事の優先順位の兼ね合いで,Real World Haskellの内容確定までにこの機能追加を間に合わせることはできないかもしれません。

 その場合,欠けたwxHaskellの記述に対して何らかのフォローを入れればと思います。