Haskell での並列プログラミングをマスターしたい、とは言わないが、「全然わからない、俺たちは雰囲気で並列プログラミングをやっている」程度のことは言えるようになりたい。

今回は「データ構造の各要素を並列で評価する」ことを目指す。以下の内容は筆者がいい加減な知識で書いているので、そういうつもりでテキトーに読んでほしい。

題材とするプログラムは、適当にでっち上げたこれ：

Test.hs:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

main = do
  let list = map fib [1..35]
  print (sum list)

fib を再帰で定義しているが、メモ化していないので見るからに遅い。

コンパイルと実行：

$ ghc -O Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
$ time ./Test
24157816

real    0m2.253s
user    0m2.195s
sys     0m0.029s

35 という数字は、手元のコンピューター (MacBook Pro) で実行して待てる程度の実行時間となるように選んだ。

この、リストに入っている fib 0, fib 1, …, fib 35 の計算を並列化したい。

parallel パッケージの Control.Parallel モジュールには par 関数と pseq 関数というのがあって、これを使うと並列で計算できる。GHC RTS の実行時オプションに -N を渡すと複数のスレッドが起動して、 Haskell の計算で使えるようになる。

しかし、データ構造の中身を並列で計算させたい場合にはこれらのプリミティブでは原始的過ぎる。そこで、 Control.Parallel.Strategies モジュールによって提供される関数を使う。

大雑把な使い方としては、 using 関数の第2引数に評価戦略 (Strategy) を渡すと、その戦略に従って第1引数を評価する。

Haskell における値の評価

そもそも、 Haskell の値を「評価」するというのはどういうことか。

Maybe a 型を例とすると、

1. Nothing か Just かすらも分からない（未計算）状態
2. Nothing か Just かは確定しているが、（Just の場合は） Just の中身までは分からない状態
3. Nothing か Just かが確定していて、（Just の場合は） Just の中身も確定している状態

の3通りがある。

Haskell で seq とか BangPatterns を使うと得られるのは 2. で、 Weak Head Normal Form とか呼ばれている。

一方、 3. のように再帰的にデータ構造の中身まで評価する、という操作は Haskell の言語では規定されていない。なので、データ型ごとに Control.DeepSeq モジュールの NFData という型クラスを実装してやらなければならない（実装自体は、 GHC の機能を使えば半自動的にできてしまうようだが）。Maybe やリストのような基本的な型についてのインスタンスは Control.DeepSeq で定義済みなので、自分でわざわざ定義してやる必要はない。

（この説明で理解できる人はこの記事を読まなくてもいい気がするが…。）

Control.Parallel.Strategies で使える評価戦略

話を戻す。Control.Parallel.Strategies.using 関数の第2引数には、評価戦略を渡す。 Control.Parallel.Strategies モジュールで定義済みの、基本的な評価戦略には次がある：

• r0: 評価しない。
• rseq: Weak Head Normal Form まで評価する。
• rdeepseq: データ構造の中身まで、再帰的に評価する。（当該データ型は NFData のインスタンスである必要がある）

これらはただの評価戦略であって、並列性とは直接関係がない。

リストの各要素を並列に評価する

本題に入る。

parList 関数に、要素ごとの評価戦略を渡してやると、リストに対する評価戦略が得られる。

今回、リストの要素はただの Integer なので、 rseq を渡しても rdeepseq を渡しても同じ結果となる。

というわけで、 list `using` parList rseq という風に書けば、リストの各要素を並列に計算してくれるプログラムの出来上がりである。

Test.hs 並列版 :

import Control.Parallel.Strategies

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

main = do
  let list = map fib [1..35] `using` parList rseq
  print (sum list)

コンパイル時には -threaded をつけ、実行時に GHC ランタイムへのオプションとして -N を渡す。-N の後に数字を書いて、スレッド数を明示的に指定することもできる。

実行結果：

$ ghc -O -threaded Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
$ time ./Test +RTS -N1
24157816

real    0m2.122s
user    0m2.073s
sys     0m0.022s
$ time ./Test +RTS -N2
24157816

real    0m1.369s
user    0m2.188s
sys     0m0.039s
$ time ./Test +RTS -N3
24157816

real    0m1.333s
user    0m2.590s
sys     0m0.072s

-N1 の場合は、並列化しない場合と同様の結果になった。実行したマシンはデュアルコア（2コア4スレッド）のため、-N2 の場合はそこそこ実行速度が向上した。-N3 を指定しても速度の向上はほとんど見られなかった（所詮ハイパースレッディングと言うべきか）。

さっきの例ではリストの中身はただの Integer なので rseq と rdeepseq の違いがわかりにくい。そこで、プログラムを改変して Maybe Integer のリストを作るようにしてみる。

改変例：

import Data.Maybe
import Control.Parallel.Strategies

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

main = do
  let list = map (Just . fib) [1..35] `using` parList rseq
  print (sum $ map fromJust list)

このプログラムをさっきと同様に -threaded, +RTS -N をつけてコンパイル＆実行しても、シングルスレッドの場合と比べて速度の向上は見られない。これは、「リストの各要素が Nothing か Just なのか」を並列で計算し、「Just の中身」は並列で計算されないからである。

「Just の中身」まで並列で計算したかったら、 rseq を rdeepseq に変えれば良い。

再・改変例：

import Data.Maybe
import Control.Parallel.Strategies

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

main = do
  let list = map (Just . fib) [1..35] `using` parList rdeepseq
  print (sum $ map fromJust list)