Haskell の GC を比較してみる

Haskell GC

GC Advent Calendar 22日目の記事です。

同じ言語に対する異なる処理系があれば、GCを比べてみたくなるのは人間のサガですよね。
今回はHaskellの2つの処理系のGCを比べて見ることにします。


■ GHC(the Glasgow Haskell Compiler)

Haskellの実行系といえばこれ。というような処理系です。Javaで言えばOracle JRE、Rubyで言えばCRubyというところでしょうか。実用世界の処理系なので様々なオプションや最適化の実装が施されています。

■ JHC

コード効率を優先した処理系です。様々なコンパイラテクニックをフルスケールのコンパイラに実装するための場である、というようなコンセプト説明がされています。頭文字のJはJohn Meachamの頭文字なんでしょうか。

それぞれのGCの特徴

■ GHC

ではまず、GHCから。
GHCのGCは下記のような特徴を持っています。

  • コピーGC
  • 世代別GC
  • Parallel GC(ConcurrentとかIncrementalではなく、SMPで並列処理するGC)
  • マークスイープのオプションがある

GHCの動きを視覚的に見るには、ThreadScopeというプロファイル表示ツールが便利です。

f:id:dec9ue:20121223085348p:plain

適当にやっててもそれなりに表示されてなにかできた気分になる！

■ JHC

JHCのGCは下記のようなオプションがあります。

  • Boehm GC
  • JGC
  • GCなし

Boehm GCは有名な保守的GCの処理系ですね。
また、GCなしというのがあるのが面白いですが。。。

メインのGCはJHCの固有実装である、JGCとなります。

JGCの特徴は下記です。

  • マークスイープGC
  • World Stopping
  • その他、凝った仕組みは特に無し

JGCにもプロファイリング機能はありますが、グラフィカルなツールは見つかりませんでした。ごめんなさい。

同じコードを動かしてみる

下記は悪名高きHaskellの5行クイックソートです。
比較的ゴミが出やすいこのコードを使って、これらの実行系の動作を比較してみたいと思います。

sort_len :: Int
sort_len = 20000
main = do
        print $ show $ drop (sort_len - 1) $ quicksort [1..sort_len]

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

それぞれ、コンパイルします。

./sorttest: $(SRC)
        ghc -O2 $(SRC) -o $@

./sorttest_jhc: $(SRC)
        jhc $(SRC) -o $@

実行結果は、流石にGHCが速いですが、JHCもなかなかのものです。
JHCのシステム時間が短いのが印象的です。(理由はよくわからないですが、、、)

seg@ubuntu:~/haskell-training$ time ./sorttest
"[20000]"
real	0m54.974s
user	0m46.387s
sys	0m7.544s

seg@ubuntu:~/haskell-training$ time ./sorttest_jhc
"[20000]"
real	0m57.992s
user	0m56.904s
sys	0m0.396s

以下はプロファイラを使用して簡単に挙動を見た結果です。

■ GHC
デフォルトではGCの呼び出し回数が10000回程度に達していました。
別途ヒープ使用量を見てみたのですが、1MB程度で安定して動作していました。

プロファイラの表示画像を見るとわかりやすいですが、GCの動作時間がかなり長いことがわかります。

f:id:dec9ue:20121223102629p:plain

もう少しメモリ使用量が増えることを許容してもGCの実行頻度を落としたほうがよさそうだなぁ。。。

■ JHC

デフォルトではGCの呼び出し回数が1300回程度でした。
一方で、メモリ使用量が時間とともに増加し、最終的に2MB程度まで達しました。

コードに少し手を入れてGCの動作時間を見てみましたが、全体の比率から言うと1割に達しない程度かなと思われました。

まとめ

Haskellのような遅延評価型の言語ではヒープに配置されるデータが多く、それらが評価が進むだけでゴミになるので、コピーGCの方が圧倒的に有利だと私は思っているのですが、、、
今回、デフォルト状態で動かした様子だけでは機構による差異よりも動かしたいプログラムの挙動とGCの呼び出し頻度のミスマッチの方が簡単に深刻な問題を呼んでしまうのかな、という印象を受けました。

ということで、実際の現場ではGCの実装を云々議論するより、パラメーターを調整してみるというトライが非常に重要だということかなと。出来ればこういうのをある程度簡単に調整してくれるしくみがあると嬉しいなぁ。

追記

サンプルコードの中でlastを使うとJHCでうまく動かなかったですね。。。なんでだろう。。。dropとか使ってしまいました。