このエントリは、Haskell Performance Advent Calendar 2016 3日目の記事です。
導入
偉い人は言いました。パフォーマンスについて云々する前に、まず測れ。
という訳で本記事では、クイックソートを例に取り、Haskellでのパフォーマンス計測を実施してみます。
Haskellのパフォーマンス改善をするなら、ITProの本物のプログラマはHaskellを使うという連載記事がためになります。クイックソートの改良をはじめ、本記事で扱われている内容のほとんどは該当連載に既に書かれているのですが、ものによってはだいぶ昔の記事だったりするので、2016年現在の状況を踏まえて、as_capablが実際にやった事を書いていこうと思います。
TL;DR
Haskellコードのパフォーマンス計測にはcriterionを使おう
やっぱりリストより配列が速い
やっぱりC++の方が速い
ソースリポジトリ
今回使用したソースコードは、全て以下のリポジトリにアップロードしています。
https://github.com/as-capabl/haskell-qsort-pfm/
計測の方針
- クイックソートを何種類か書いて速度を計測する
- リストと配列の比較
- リストクイックソートは普通に書いた物と、改良したものを作成
- 配列クイックソートは、配列型が何種類かあるので、それぞれ比較
- 参考データとしてC++で書いたものも比較
- ソートするデータは64bit符号なし整数、一様乱数
- 環境はCore i7 4770k(Haswell)。メモリ8G。
- コンパイラはghc-8.0.1。最適化オプションはstack(およびbjam)リリース版のデフォルト
- ビルドシステムはstack(およびbjam)を使用
計測手段:criterion
速度計測にはcriterionというフレームワークを使用します(本物の〜43回)。
フレームワークというと、どうしても初期導入が面倒で尻込みしてしまうもので、今回も「C++との異種比較があるし、bashのtimerコマンドで測ればいいかな」などと考えていました。しかし、やってみると乱数発生や入出力の部分が無視できない影響を与える事が発覚し、「C++コードもFFI呼びして全部criterionで測る」という方針に途中で変更となりました。
実際にやってみれば、criterionの導入はとても簡単でした。普通にプロジェクトを新規作成(stack new)してcriterionを依存ライブラリに追加、適当にインポートを追加して、main関数から以下のように呼べば、～～の部分に掛かる速度を測って良い感じに画面に表示してくれます。
defaultMain [ bench "タイトル" (簡約関数 ～～), ... ]
Haskellは遅延評価なので、単に式を書いただけでは評価されず、処理に掛かる時間を計測できません。そこで、強制的に値を評価するための簡約関数がcriterionライブラリで用意されています。詳細はドキュメントを参照して頂くとして、今回は純粋ならnf、副作用ありならwhnfIOを呼びます。
(12/18追記)副作用ありのものについては少し注意事項があるので、次回記事も参照して下さい。
結果のグラフ化なども可能ですが、今回は省略。
またcriterionの姉妹ライブラリであるprogressionを使うと、ライブラリごとに複数の条件で計測を取ってグラフ化などができます(本物の〜44回)。クイックソートで使うなら、データ数を変えてプロットし、O(N log N)に従っているかを確認したりといった所でしょうか。
実測
データ点数: 500,000
| 項目 | 結果(msec) |
|---|---|
| list/trivial | |
| list/improved | |
| vector/boxed | |
| vector/unboxed | |
| c++/wrote |
(12/18)上記結果にはミスがあります。次回記事で再計測しています。
もっとデータ数の多いものも測ってみましたが、大体傾向は同じでした。測定精度パない。
以下それぞれの解説。
list/trivial
ソースはhttps://github.com/as-capabl/haskell-qsort-pfm/blob/master/src/List.hs
よくHaskell初心者への導入に使われるリストクイックソートです。
コードはたったのこれだけ。
quicksort [] = []
quicksort (x:xs) =
let lt = filter (<x) xs
gteq = filter (>=x) xs
in
quicksort lt ++ [x] ++ quicksort gteq
何をしているのか分かりやすいのがメリット。
list/improved
ソースはhttps://github.com/as-capabl/haskell-qsort-pfm/blob/master/src/List2.hs
list/trivialを改良したもの。大体倍速くらいで走るようになりました。
改良点は以下二つ。
- アキュムレータ引数ysを導入し、++演算子を使わないでリストを連結できるようにした
- filterでの比較を2重に行っていたのを、1つにまとめた
++演算子はリストの連結だから遅そうだ、というのはよく言われますが、色々試しながらやってみたところ、実処理時間を取っていたのは主に後者であった事が発覚したりしました(12/18)条件次第ですが両方とも時間短縮に効果があります。もし明日以降リストのソートに関して記事を書く機会があれば、詳しく扱うかもしれません。
なお、今回はデータを乱数に決め打ちしているため、ピボット選びの工夫はしていません。
vector/boxed
ソースはhttps://github.com/as-capabl/haskell-qsort-pfm/blob/master/src/BV.hs
Data.Vector.Mutableを使用したインプレースアルゴリズム。Data.Vector.Mutableは普通のHaskell型の値を入れる配列で、メモリ上ではC言語でいえばポインタの配列という持ち方をしています。Unboxedよりかなり遅いという印象がありましたが、意外にも健闘。
vector/unboxed
ソースはhttps://github.com/as-capabl/haskell-qsort-pfm/blob/master/src/UV.hs
Data.Vector.Unboxed.Mutableを使用した以外はboxedと同じ。Unboxed型はC言語の配列と同様、メモリ上に直接値を持つので高速です。プリミティブ型しか扱えないのが難点。
なお、Haskellで配列を扱うライブラリにはarrayとvectorがありますが、vectorの方が機能が多いので基本的にこちらを使います。arrayを試したところ、添字チェックなしで要素にアクセスする方法がないので、vectorには敵いませんでした。
c++/wrote
ソースはhttps://github.com/as-capabl/haskell-qsort-pfm/blob/master/cxx/wrote.cpp
vector/unboxedと全く同じアルゴリズムをC++で書いたもの。最初はdivideも再帰で書いていましたが、一瞬でスタックが溢れたのでループに直しました。
当然、C++なので速いです。
今回のテーマからは外れますが、FFIを使うソースをcabalでビルドする場合に、(libではなく)C++ソースファイルをコンパイル、リンクする方法が分かりませんでした。情報を調べてもc2hsを使う方法/使わない方法など色々あって判然としなかったので、今回はその場しのぎで、bjamでlibを作ってからリンクしています。
結論
Unboxed Vectorで書けば、HaskellでもC系に近い速度が出るとされていましたが、残念ながら実測では結構な差が出てしまいました。再帰がうまくループになってないのかな、などと疑って色々直してみましたが、今のところ状況を打開できていません。
今回、なんとなくの目標として「HaskellでC++に匹敵する速度を出せたらいいな」「リストアルゴリズムでも、配列に敵わないにせよ比較になる速度を出せたらいいな」という目論見があったのですが、本日公開分では両方とも未達成となっています。
parによる並列化(本物の〜10回)も試しているのですが、現状シングルスレッドより遅いので略。
引き続き、高速化する方法を探っていこうと思います。何かあったらこのアドベントカレンダーで発表しようと思うので、よろしくお願いします。