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

前回記事の続きです。
前回は「Haskellクイックソート計測大会2016」という事でcriterionによる速度計測の実例をレポートしましたが、計測結果を本記事で少し修正しようと思います。

Criterionの補足：初期化処理について

まずはcriterionの使い方についての補足です。
というか、前回記事で使用したソースに間違いが一つあったため、その訂正になります。

前回記事で使用したソースでは、MutableなVectorに対する計測を以下のように書いていました。

bench "boxed" $ whnfIO (BV.quicksort bv 0 numElems),

しかし、criterionのエンジンは、計測コードを複数回実行し平均を取る仕組みになっています。そのため、二回目以降はソート済みの配列に対して時間計測を行ってしまっていました。
今回の配列ソートではピボットを中央から取っているため、ソート済みの配列に対しては最大効率になります。つまり前回記事の計測スコアでは、Vector関係は実際より良い数値が出てしまっている事になります。

という訳で、毎回のテストごとに初期化処理を入れるように修正します。
これを行うのは、以下の関数になります。

env ::
  NFData env =>
  IO env -> (env -> Benchmark) -> Benchmark

型を見ればおおよそ使い方が想像できると思いますが、第一引数のIOアクションにより、env型の値を計測外で作成し、それを引数として計測を実施します。
envはNFDataのインスタンスである必要があります。NFDataはseqによく似た、値の簡約を促す関数rnfを公開するクラスです。seqではリスト等の構造に対して最外のコンストラクタまでしか簡約できない(WHNF、弱頭部正規形)のに対し、NFDataが定義されていれば再帰的に中まで簡約する事ができます。
これにより、初期化部の処理が遅延評価されて計測時に時間を取ってしまうというトラブルを防ぐ仕組みになっています。
同じ仕組みは、前回から使用しているnfなどの関数でも使われています。

NFDataによる簡約は、Haskellの「遅延評価ゆえのチューニングの困難」に対する一つの武器となります。詳しくは、What I Wish I Knew When Learning Haskell 日本語訳の該当記事などを参照して下さい。

ところが今回の場合、問題が一つ発生します。
MutableなVectorはNFDataではないため、envの値にできないのです。
こちらのissueでは「newtypeで包んでダミーのNFDataインスタンスを宣言する」という方法が薦められていますが、今回の場合は下記のように書いた方が簡単でしょう。

env (copyList bv orig) $ \_ ->
  bench "boxed" $ whnfIO $ BV.quicksort bv 0 numElems

IOアクションが使えるので、戻り値ではなく副作用で配列を初期化すればいいわけです。
これで、bvが毎回origに初期化されるようになりました。

計測の追加

クイックソートの計測ですが、以下のような先行研究があるとコメント欄でご指摘を頂きました。
http://d.hatena.ne.jp/kazu-yamamoto/20120706/1341546985

こちらを元に、計測項目を追加してみます。
quickSortが前回記事のlist/trivial、quickSortVecがvector/unboxedに相当します。
STを使用したものはvectorとほぼ一緒のため割愛。

という訳で以下の3点を、計測対象に追加します。

##library/Data.List
Data.Listに標準で入っている、リストのソートです。中身はマージソートらしいです。

##library/Vector.Algorithms
vector-algorithmsパッケージに含まれる、配列のイントロソートです。BoxedにもUnboxedにも適用可能ですが、今回はUnboxedで計測しています。

##library/C++_STL
リンク先の記事には含まれていませんが、せっかくFFIが準備できているのでC++のSTLのソートも追加します。アルゴリズムはイントロソートだったと思います。

#実測

項目	結果(msec)
list/trivial	693
list/improved	391
vector/boxed	84.2
vector/unboxed	33.2
c++/wrote	5.17
library/Data.List	1003
library/Vector.Algorithms	19.6
library/C++_STL	4.12

vector/boxedとlist/improvedの差が、若干ですが縮まりました。
ソートにおいては、さすがに結果を逆転するには至りませんが、もっとリスト向きのアルゴリズムならばリストも悪くないかもしれません。
「リストは実用に耐えないほど遅い」という印象が少しでも払拭できればと思います。

今回のようなトップスピードの比較では、イントロソートは純粋なクイックソートより遅かったはずですが、vector-algorithmsとSTLにはもう少し工夫がされているようです(恐らく、要素数が少なくなったら挿入ソートに切り替えるなど)。手書き同士にしろライブラリ実装同士にしろ、C++とHaskellで比較すると5倍程度の実行時間の差になる、というのが結論になるかと思います。

#もう一つの訂正事項と次回予告
今回の再計測は以上ですが、前回記事にはもう一つ訂正点があります。

改良版リストソート(list/improved)について、以下のような記述をしました。

改良点は以下二つ。

• アキュムレータ引数ysを導入し、++演算子を使わないでリストを連結できるようにした
• filterでの比較を2重に行っていたのを、1つにまとめた

++演算子はリストの連結だから遅そうだ、というのはよく言われますが、色々試しながらやってみたところ、実処理時間を取っていたのは主に後者であった事が発覚したりしました。

この件なのですが、測り直してみたところ以下のようにアキュムレータもきちんと効いています。

項目	結果(msec)
list/trivial	745
アキュムレータのみ	544
filterの改良のみ	534
list/improved	423

計測コードはこちら。

アキュムレータとfilterの改良は、それぞれ同じくらい時間短縮に効いていて、両方を合わせたものが最速となります。

前回記事のように書いてしまったのは、このソートをチューニングしている頃はcriterionを使用せず、
time関数で時間を測っていて、計測方法の違いによる影響が出たためです。

次回はカレンダーをもう一コマとって、この事について説明してみたいと思います。