この連載では第37回から前回まで，逐次処理を行うプログラムを効率化するテクニックやツールを説明してきました。こうした知識を前提に，今回から何回かに分けて，並列プログラムの処理の効率化について解説していきます。これまで説明したテクニックやツールの中には，並列プログラムで利用できるものと利用できないものがあります。これらを明らかにしていきます。

並列化の前に逐次処理の効率を上げる

　第10回から第14回にかけて，GHCを使ったHaskellでの並行/並列プログラミングについて説明しました。もっとも，プログラムの並列化は目的ではなく，あくまでプログラムを高速化する手段の一つに過ぎません（参考リンク）。並列化したコードが逐次処理のコードに比べて処理が遅くなる場合には，並列化する意味はありません。

　並列プログラムの効率は，処理を並列化する前の逐次処理プログラムの効率に依存します。高速な並列プログラムを目指すなら，効率の良い逐次処理を行うプログラムを書いてから，それを並列化すべきです。逐次的な処理の効率と並列化による性能の向上にトレードオフが存在する場合もありますが，まず処理効率が高いコードを書いた後で検討すべきです。

　第11回で取り上げた並列処理版のクイックソート関数を例に考えてみましょう。この関数は並列処理を説明するために取り上げたものなので，必ずしも高速なプログラムにはなっていないからです。なお，第43回のコラムで説明したparallelパッケージの変更に合わせて，定義を少し変更しています。

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

　この関数は性能面で問題を抱えています。基になる逐次処理の効率があまり良くないのです。qsortPar関数で並列化している逐次処理のquickSort関数は，以下の定義になります。

quickSort [] = []
quickSort [x] = [x]
quickSort (x:xs) =  quickSort [y | y <- xs, y < x]
                 ++ x:(quickSort [y | y <- xs, y >= x])

　quickSort関数では，リストの先頭の要素で比較を行っています。この手法は，第44回で性能を検討したように，ランダムな要素を格納したリストに対してはうまく働きますが，昇順もしくは降順に整列したリストでは，リストを極端に偏った形で分割することになるため，性能が悪化してしまいます。

　この問題を解決するには，リストの先頭の要素を比較するのではなく，リストをなるべく均等に分割できるような値を選択して比較する必要があります。昇順や降順に整列したリストでもリストの分割が偏らないような値の選び方には，以下の3種類があります（参考リンク）。

  • 中央の要素を選択
  • ランダムな要素を選択
  • 先頭，中央，末尾の三つの要素を選択し，その中央値を利用（参考リンク）

　とりあえず，中央の要素を選択するという最も単純な戦略を採ってみましょう。今回は処理の効率化の基本方針を説明するのが目的なので，詳細な性能比較は行いません。実装による性能の違いに興味がある方は，第43回で説明したcriterionや第44回で説明したprogressionなどを使って，それぞれの実装の性能を比較してみてください。

betterQsort :: (Ord a) => [a] -> [a] 
betterQsort = quickSortWithPivot selectMiddle

-- 中央の要素を選択
selectMiddle :: (Ord a) => [a] -> a
selectMiddle xs = let midIndex = div (length xs) 2
                  in  xs !! midIndex

quickSortWithPivot :: (Ord a) => ([a] -> a) -> [a] -> [a]
quickSortWithPivot _ [] = []
quickSortWithPivot _ [x] = [x]
quickSortWithPivot f xs  = losort ++ hisort
    where x      = f xs
          losort = quickSortWithPivot f [y | y <- xs, y < x]
          hisort = quickSortWithPivot f [y | y <- xs, y >= x]

　これで，昇順もしくは降順に整列したリストでも極端に性能が悪化することはなくなりました。しかし，これでもまだ十分に効率的な実装とはいえません。

　ここまで見てきたクイックソートでは，リストの要素の整列のために，リストの要素を2分割したリストを再帰的に作成していました。しかし，中間データ構造を作成すると，処理の効率が落ちてしまいます。効率的なクイックソートを実装するには，データ構造内の要素を破壊的に更新するin-placeアルゴリズムを採用する必要があります。

　ところが，Haskellではリストの要素を直接変更することはできません。in-placeアルゴリズムでクイックソートを行いたいなら，第19回で説明したMArrayや第42回で説明したMVectorといった，要素を破壊的に更新できる可変配列にリストの要素を移し替えるか，最初からリストではなく可変配列を使う必要があります（参考リンク）。

　クイックソートではなく，データ構造や目的に合った別のアルゴリズムを使うという選択肢もあります。GHCのData.Listモジュールでは，sort関数の実装としてクイックソートではなくマージソートを採用しています。また，MVectorに対して探索や整列などのアルゴリズムを提供するvector-algorithmsパッケージでは，クイックソートが苦手とするようなデータを効率良く扱えるよう，クイックソートにヒープソートなどを組み合わせたイントロソートを提供しています（参考リンク）。

　並列データ構造や並列アルゴリズムは，効率的な逐次データ構造や逐次アルゴリズムの上に成り立つものです。データ構造やアルゴリズムには並列化に適するものと適さないものがありますが，それよりもまず逐次プログラムとして処理効率を上げるのを優先してください。

　第24回のコラムで説明したように，第10回で紹介したデータ並列Haskellでは，同一のコードから逐次プログラムと並列プログラムの両方を作成できます。このため，「処理効率が高い逐次プログラムを書き，それを並列化する」「処理効率が悪い並列プログラムのアルゴリズムの問題を探るため，逐次プログラムに変換する」といった作業をスムーズに行えます。データ並列Haskellはまだ開発中ですが，将来は高速な並列プログラムを作成するのに役立つでしょう。