GHC の Spark と GC

はじめに

GHC の並列化について調査していたところ、 GHC のバージョン 6 と 7 との間に並列化の方法に関わる大きな変更が入っていたことを知りました。

Spark の解説

GHC には、 Haskell プログラムを SMP (Symmetric Multiprocessing, 対称型マルチプロセッシング) 環境で効率よく実行するための拡張機能が含まれており、 "Parallel Haskell" と呼称されています。この Parallel Haskell の実装には、 Spark と呼ばれる構造が使用されます。

Haskell コード上で、以下の様に記述すると:

 x `par` y

GHC のランタイムに、 「 x を(できれば)並列に評価しながら、y の値を評価して返してくれ」 と伝える効果があります。例えば、 y の評価の過程で x の値が必要ならば、 あらかじめ x を並行して評価するようにランタイムに通知しておくことで、 評価全体の経過時間を短縮することが出来ます。 このように、par 関数によって生成される、並行して評価する計算単位が Spark と呼ばれます。

Spark は、アイドル状態のCPUコアがあれば、それを使用して評価されて行くのですが、 資源不足でアイドル状態のCPUコアがない場合は、全く実行されないということもあります。 上記の例で言えば、アイドル状態のCPUコアがないため、 y の評価中に x の値が必要になったのに、x を評価する Spark がまだ実行されていない、 という状況です。この場合は、 'par' を使わなかった時と同様、 y の評価の過程として x が評価されます。 そして、 x を評価する Spark は単純に放棄されます。 この挙動は、 「 x の評価は、どのタイミングで行なっても、同じ値が得られる」という仮定、 つまり、 pure で決定的な計算であるという点に基づいており、 そのような計算を高速化するためのものとして Spark が設計されているためでもあります。

Spark について、複数 CPU コアを活用するという点を考えると、いわゆるスレッドが思い浮かびます。 一般的にスレッドというと、 個々のスレッド同士のメッセージ交換や、 スレッドの実行順序などを考慮することになり、 つまり Haskell で言うところの IO が付随してきます。そのような IO を伴う並列実行は、 Haskell では "Concurrent Haskell" という名の拡張機能で扱われています。 一方 Spark は、 IO が絡む動作となる、複雑な制御は出来ません。 むしろ、それらを隠すことで、 pure な計算の高速化に使いやすい形式に収めています。

Spark GC Policy の変更

GHC 7.0.1 のリリースノートには、「ランタイムシステムの変更により、 Control.Parallel.Strategiesパッケージを用いている場合には version 2 以上に上げて下さい」 とあります。この変更は、 Spark を GC する際のポリシーの変更によるものでした。 GC だけの話とも取れるのですが、 実は Spark の使い方にも影響する重大な変更だったのです。

GHC 6 までは、 GC は Spark を、常に生存しているオブジェクトとして扱っていました。 そのため、過度に Spark を作った場合、それへの参照が失なわれ、 ランタイムから見て不要ということが明らかになっても、 その Spark が回収されることはありませんでした。結果として、 不要な計算を抱えた Spark でも存在し続け、(不要ながらも)評価されてしまうことになります。 こうして、Spark が参照するメモリ領域や、 Spark を評価するための処理時間が無駄になっていたのです。 このような事情により、この時期に書かれた文献では、 Spark を立てすぎないようにすることが性能最適化の実践例として紹介されていました。

GHC 7.0.1 になって、 どこからも参照されていない Spark は、 GC によって回収されるようになりました。 どこからも参照されていない Spark とは、もはや不要となった計算を抱えた Spark ということなので、 これが回収されることで上記の問題は解消されます。 Spark を立てすぎるということは問題にならなくなりました。 さらに、「もしかしたら不要になるかもしれない計算」に Spark を立てるという、 投機的な Spark 作成も可能になりました。必要な計算かどうか分からなくても、 Spark をアイドル状態のCPUコアに任せられるなら経過時間での損はないですし、 それが有効な計算なら時間短縮になります。不要であると分かれば、 その Spark は実行されないというだけで、経過時間の損失はありません。

まとめ

調査の結果、並列化の方針自体を考えなおさないといけないような、 基盤レベルの変更があることが分かりました。現在、この方針に基づいて、 どんどん Spark を立てていくことで既存のプログラムを高速化できないかと目論んでいます。

特に性能最適化ということについては、このような基盤回りの変化が、 大きな方針変更につながるものですから、ひきつづき最新の動向に注目していきたいと思っています。

References

Author: YOKOTA Yuki

Date: 2013-06-24T16:04+0900

Generated by Org version 7.9.2 with Emacs version 24

© Mathematical Systems Inc. 2013