Haskell の処理系、GHC でのごみ集め

Haskell処理系のひとつ、GHCの実行時オプションを勉強していたところ、 一つドキュメント化されていないオプションを発見しました。 以下のオプションです:

  -w       Use mark-region for the oldest generation (experimental)

調べた結果、GCのアルゴリズムを変更するオプションと分かりました。

GHCのランタイムは、メモリ上のごみ集め (garbage collection, 以下GC)に、 世代別 GC を採用しています。世代別 GC とは、 「一時オブジェクトは、すぐに破棄されることが多く、 ある程度長く生存したオブジェクトは、以降も長く生存することが多い」 という経験則に基づいた GC 手法です。

このようにすることで、世代別 GC ではメモリの効率的な回収を行うことができます。

次に、各世代への回収手法です。GHC のデフォルトでは、 全ての世代に対してCopying による回収を行います。 Copying とは、ヒープ(動的に確保されたメモリ領域)を分割し、 生きているオブジェクトを隙間を詰めながら移動することで 使われていないオブジェクトを回収する手法です。 ヒープを分割することによる領域の無駄はありますが、高速な回収が可能です。 さらに、GHCの実装では並列化もされています。

最も古い世代へのGCについては、より正確で領域の無駄の少ない回収手法を選ぶことが出来ます。 実行時オプションの '-c' を指定するか、 最大ヒープの 30% (デフォルト値) を越えてヒープを使用するかすると、 Mark-Sweep と compaction を行うアルゴリズムに変更されます。 Mark-Sweep は、全てのオブジェクトについて使用されているかチェックし、 使用されていないと確認されたオブジェクトを解放する手法です。 これに加えて、 Mark-Sweep で生じたヒープ上の隙間を積める処理 (compaction) を行い、 ヒープの断片化を防ぎます。

この '-c' オプションは、 「Copying より遅いが、メモリ使用量を顕著に減らす効果がある」 と user guide にあります。 実際、大量にメモリを使用するプログラムにおいて、 メモリ使用量を 2/3 程にまで抑えることができ、 結果的に無駄なGC時間を減少させて速度を稼ぐことが出来ました。

さて、 Mark-Region ですが、 'Mark-Sweep'の改良版といえるアルゴリズムです。 Mark-Region の基本形は、以下のようになります:

メモリを region 単位で扱うことにより、局所性が向上します。 それにより、マシン上でのキャッシュヒット率の向上などが見込め、 性能の向上が期待できます。

一方で、解放処理が region 単位になることで、 速度の向上と引き換えに領域の無駄遣いが起こってしまいます。 詰め込みきれなかった region の余った領域が無駄になったり、 中途半端に詰められた region が解放できなかったりという点です。

現在、この Mark-Region の欠点を解消し、さらなる最適化を組みこんだ Immix という GC が実装されているそうです。概要は以下のようになっていま す:

これらにより、 Mark-Region での region の大きさをどうするかという問題や、 region 内部の断片化の問題を回避しています。

GHC に搭載されている '-w' オプションは、 GHC 6.10 頃から'experimental' なものとして組み込まれており、 最も古い世代へのGCに Mark-Region を行うようになります。 実際に大量にメモリを使用するプログラムに使用してみたところ、 '-c' を使用したときと同じくらいにメモリ使用量が減少し、 さらにGC時間は '-c' の時よりも短くなっているのが確認できました。

この Mark-Region の性能から、将来的にこれの改良版の Immix が GHC に組み 込まれ、この仕組みが安心して使えるようになることに期待しています。

参考 : GHC の GC について:

参考 : Immix について:

Author: YOKOTA Yuki

Date: 2013-04-23T14:31+0900

Generated by Org version 7.9.2 with Emacs version 24

© Mathematical Systems Inc. 2012