Haskellの入門者向け解説ではHaskellのエレガントさのデモンストレーションとして、以下のように非常にシンプルなクイックソートが紹介される事があります。

quicksort [] = []
quicksort (x:xs) = quicksort lt ++ [x] ++ quicksort gteq
  where
    lt = filter (<x) xs
    gteq = filter (>=x) xs in

しかし、このソートは「遅い」「というかクイックソートじゃない」と、批判の対象になっています。

• https://togetter.com/li/445854
• https://cpplover.blogspot.jp/2017/12/haskell.html

メモリ上のデータの置き方まで定義した狭義のin-placeクイックソートに当てはまらないのは仕方ないとして、「遅い」というのは本当でしょうか。
「パフォーマンスを云々する前に、まず測れ」の金言に従い、検証してみようと思ったのが、去年のアドベントカレンダー時期の事でした。

これまでのあらすじ

この記事は、昨年のHaskell Performance Advent Calendar 2016に投稿した、以下二本の記事の続報になります。

• Haskellクイックソート計測大会2016
• クイックソート計測大会2 criterionの注意事項 他

が、適宜内容はフォローするので未読でも問題ありません。
さしあたってまず、前年の計測の結果を転載します。

残念ながら配列系、特にC++でやったものと比べ、リストクイックソートは100倍近い時間が掛かってしまいます。
計測してみたけどやっぱり遅かったわ、が結論になりそうですが、本当にそうでしょうか。

計測は本当にフェアなのか

ここで再検証してみたいのが、ソート本体ではなく、ソートの計測コードです。

今回の計測では、Haskellのパフォーマンス計測を行うライブラリのデファクトであるcriterionを使用しており、リスト系ソートの記述は、以下のようになっています。

            bench "trivial" $ nf List.quicksort orig,

これは、「List.quicksortにorigを適用した結果をNF(Normal Form, 正規形)まで簡約し、それにかかる時間を計測する」という意味のコードです。正規形とは、これ以上評価できない状態を意味します。つまり、上記コードは要素数分の長さの片方向リンクリストを作成するということです。

ところで、片方向リンクリストは要素数Nに対して枝N個、葉N個、合計2N個のノードをヒープ領域に確保します。たとえば10万要素をソートするとして、10万要素のクイックソートと、20万回のmallocはどちらが時間が掛かるでしょうか。クイックソートはO(NlogN)でN回のmallocはO(N)なので単純比較はできないものの、一般的にはmallocの方が重い処理です。リスト側の結果には、この分の時間が含まれてしまっています。

そこで、条件を揃えるためにリストソートの結果を配列に書き込んだらどうでしょう。Haskellは遅延評価なので、リストを返す関数だからといって中間データとしてのリストを必ず作成する訳ではありませんから、結果を即座にfromListで書き込めば実質的に配列を出力する事が可能です。
そうするとリスト入力→配列出力という処理ができます。条件を揃えるために、配列側も入力をリストとしてみましょう。

つまり、以下の処理の時間を計測してやれば、よりフェアな条件で確認ができることになります。

• リスト系ソートは、ソート結果を配列に書き込むまでの時間を計測する
• 配列系ソートは、リストで与えた入力を配列に書き込んでからソートする

コードはこちら。

なお、trivialを(U)と(S)に分けたのは「C++で使っているVector.Storableが、Vector.Unboxedより遅いのではないか」と疑ったためです。結果としてこれは「大して差がない」という結論に落ち着きました。
あと、処理が全体的に高速化したため、データ件数を前回記事の2倍に増やしています。

実測1

実行は https://github.com/as-capabl/haskell-qsort-pfm をビルド後に stack exec qsort-pfm3 。

(　ﾟдﾟ) ・・・
　
(つд⊂)ｺﾞｼｺﾞｼ
　
(；ﾟдﾟ) ・・・
　
(つд⊂)ｺﾞｼｺﾞｼｺﾞｼ
　　_, ._
（；ﾟ Дﾟ） STLより速い、だと…！？

さらなる条件設定

リストを入力して配列を出力する、という条件において、リストソートは配列ソートを上回る事が分かりました。しかし、この条件は必ずしも実用途に合っているとはいえません。メモリ効率などから考えて、大きいデータ列はリストより配列に置きたいところです。

配列ソート側からすれば、前回の計測は余計な変換処理で時間をロスしている事になります。

そこで、次の計測では5行クイックソートとSTLのソートに絞り、以下のように計測条件を増やしてみます。

• リストを入力して配列を出力する(前節と同じ)
• 配列を入力して、別領域の配列を出力する(out-of-place)
• 入力配列を直接ソートする(in-place)

マニュアルを見ながら頑張った結果、コードは以下のようになりました。

    defaultMain
      [
        bgroup "List -> Vector"
          [
            bench "trivial(U)" $ whnfIO $
                return (List.quicksort origL) >>= listToVec numElems,
            bench "c++_STL" $ whnfIO $
                listToVecS numElems origL >>= \sv -> CXX.quicksortStl sv 0 numElems
          ],
        bgroup "Vector -> Vector"
          [
            bench "trivial(U)" $ whnfIO $
                return (List.quicksort $ U.toList origU) >>= listToVec numElems,
            bench "c++_STL" $ whnfIO $
                thaw origS >>= \sv -> CXX.quicksortStl sv 0 numElems
          ],
        bgroup "Vector (in-place)"
          [
            env (return $ U.force origU) $ \copyU -> bench "trivial(U)" $ whnfIO $
              do
                uv2 <- listToVec numElems $ List.quicksort (U.toList copyU)
                uv <- U.unsafeThaw copyU
                UV.unsafeCopy uv uv2,
            env (S.thaw origS) $ \sv -> bench "c++_STL" $ whnfIO $
              do
                CXX.quicksortStl sv 0 numElems
          ]
      ]

コード全体はこちら。

リストソートでは最後の条件のコードは書けないので、「いったん別の配列に書き込んでからメモリコピーで書き戻す」という条件で替えました。
また、最速同士の対決なのでデータ数を10倍に増やしました。

計測2

実行は上記リポジトリをビルド後に stack exec qsort-pfm3-2 。

うんうん、やっぱりin-placeならSTLは速いな……あれ？

なぜリストソートまで高速化するのか

確かに、入力を配列とすれば配列ソートは高速化します。しかし「入力を配列にした事でリストソートまで高速化する」という想定外の現象が発生しています。

高速化した Vector -> Vector のコードを、List -> Vector と比べてみると、fromListでわざわざリストを作ってから元と同じ流れで処理をするという、一見してムダな処理が増えただけに見えます。

しかし、出力を配列化した時と同様の議論で、これは高速化に寄与することがいえます。
Haskellは遅延評価なので、fromListを適用したからといってすぐに片方向リンクリストを作る訳ではありません。イメージ的には、「評価されるたびに配列のポインタを一つずつ進めるサンク」を生成すると考えればいいでしょう。

つまり Vector -> Vector のリストソートは、実際は配列へのインデックスアクセスで処理される事になります。となれば、メモリアクセスの局在性によって、入力がリストだった時より有利になるのは明らかです。

結論として入力と出力をUnboxed Vectorにすれば、途中がリストでもUnboxed型の恩恵を得られるという教訓が得られました。

その他の検証

そして、リストと配列それぞれの最速ケースはSTLのin-placeソートと、リストのout-of-place配列ソートで、これはリストソートの圧勝になっています。
in-placeアルゴリズムが負けるというのは、にわかに信じられませんが、(もしも私が何かミスっているので無い限り)以下のどれかが理由なのでは、と推測できます。

• GHCのLLVMバックエンドによる自動ベクトル化
• out-of-placeソートは連続メモリへの読み込み/書き込みなので速い

強いて言えば、ちょっと不可解なのが Vector -> Vector のSTLの結果です。in-placeから比べるとmemcpy一回分しか処理が増えていないのに、処理時間が数倍に増えています。リストのout-of-placeとin-placeの差も同様にmemcpy一回分ですが、こちらは10%程度のコストです。

理由は結局不明です。以下、推測で3つほど挙げておきます。

• 何らかの要因でmemcpyにコンパイルされなかった
  →Vector.Storableのコードを追ってみると、最終的にcopyBytesという関数で処理されるので、memcpyになりそうな感じがします
• memcpyとstd::sortの間にFFIの壁があるので、何らかの最適化が効かなくなっている
• in-placeアルゴリズムはいきなり配列の末尾にアクセスするので、memcpyと連続実行した場合、常に先頭からアクセスするリストソートよりキャッシュメモリの関係で不利

それで結局、どれを使えばいいの？

実際の用途ではData.Listのsortを使うのが最善となります。

ここまで書いておいて何ですが、5行クイックソートにはもう一つ、ピボットの選択がまずいという問題があり、それは今回は解決しませんでした。やり方はネットで検索すればヒットしますが、Data.Listのsortがあるのでそっちを使った方が早いでしょう。