2012年1月8日日曜日

Criterionを使ったHaskellコードのパフォーマンス計測

LeftistHeapは、要素を挿入するときや削除するときに、右か左の部分木に対して再帰的な操作を行う。この時、左右どちらで再帰しても正しく動作するが、パフォーマンスに影響を与える。という話。

Haskell にはパフォーマンス計測用のフレームワーク Criterion があるので、これを使って調べてみた。

まず、計測対象のプログラムを準備する。デフォルトの実装では右の子供に対して再帰しているので、比較用に、左に再帰する関数 insertL と deleteMinL を実装する。(計測用に使うだけなので、LeftistHeapモジュールの外で実装したかったが、データコンストラクタでパターンマッチしないといけない、つまり、LeftistHeapの内部構造を知らないといけないので、LeftistHeap内で実装するしかない。)コードは github にアップした。

次に、計測用のコードを書く。
main = defaultMain [ bench "Left"  $ whnf (findMax insertL deleteMinL) ns,
                     bench "Right" $ whnf (findMax insert deleteMin) ns ]
whnf は、計測対象の関数(を 1 引数にカリー化したもの)とその関数への引数を取って、Weak Head Normal Form に簡約する。同様に Head Normal Form まで簡約する nf もある。

計測用のコード全体は以下の通り。
import Criterion.Main
import LeftistHeap
import System.Random

type Rand a = StdGen -> (a, StdGen)

randomInts :: Int -> Rand [Int]
randomInts 0 rng = ([], rng)
randomInts n rng = let (x, rng') = next rng
                       (xs, rng'') = randomInts (n - 1) rng'
                    in (x:xs, rng'')

findMax :: (Int -> LeftistHeap Int -> LeftistHeap Int) ->
(LeftistHeap Int -> LeftistHeap Int) -> [Int] -> Int
findMax ins del ns = findMax' $ foldr ins empty ns
  where
    findMax' :: LeftistHeap Int -> Int
    findMax' h = let e  = findMin h
                     h' = del h
                  in if isEmpty h' then e else findMax' h'

main :: IO ()
main = do stdGen <- newStdGen
          let (ns, _) = randomInts 1000 stdGen
           in defaultMain [ bench "Left"  $ whnf (findMax insertL deleteMinL) ns,
                            bench "Right" $ whnf (findMax insert deleteMin) ns
                          ]  
これを ghc でコンパイルして実行する。当然だが、パフォーマンスの計測なので、ghciで実行しても意味ない。
> ghc -O --make PerfLHeap.hs && ./PerfLHeap
warming up
estimating clock resolution...
mean is 4.512760 us (160001 iterations)
found 3996 outliers among 159999 samples (2.5%)
3234 (2.0%) high severe
estimating cost of a clock call...
mean is 81.74308 ns (34 iterations)
found 6 outliers among 34 samples (17.6%)
1 (2.9%) high mild
5 (14.7%) high severe

benchmarking Left
mean: 18.68245 ms, lb 18.60457 ms, ub 18.83024 ms, ci 0.950
std dev: 532.2852 us, lb 332.5989 us, ub 909.0032 us, ci 0.950
found 14 outliers among 100 samples (14.0%)
2 (2.0%) high mild
12 (12.0%) high severe
variance introduced by outliers: 22.891%
variance is moderately inflated by outliers

benchmarking Right
mean: 1.579322 ms, lb 1.574251 ms, ub 1.589812 ms, ci 0.950
std dev: 35.82818 us, lb 20.36439 us, ub 58.87072 us, ci 0.950
found 6 outliers among 100 samples (6.0%)
6 (6.0%) high severe
variance introduced by outliers: 16.123%
variance is moderately inflated by outliers
赤字のとおり Right の方が速いことがわかった。
Leftist Heap は、左の子の rank (一番右末端までの深さ) を、右の子より長く保とうとするので、左の部分木の方が高くなる。insertL, deleteMinL は、右の子に対して再帰的な操作 (merge) を行うことで、木をバランスさせる方向に働くため、Right の方が速い、と直感的には理解した。

Criterion は、単にプログラムの経過時間を測るだけではなく、もっと賢いことをしてくれるようだ。
最初にクロックの分解能や、クロックの値を取得するコストを調べ、これらの測定誤差に影響されないようにするには、測定対象の関数を何回実行すれば良いかを計算し、その回数実行する。
上記の結果は、Thinkpad X121e Core i3 2367M 1.4GHz + Fedora 16 での計測結果だが、分解能が 4.5us で、呼び出しコストが 81ns だった(青字の部分)。Left については、計測 1 回ごとに計測対象 "whnf (findMax insertL deleteMinL) ns" を 1 回呼び出し、これを 100 回ループする。
Right については、計測 1 回ごとに計測対象 "whnf (findMax insert deleteMin) ns" を 3 回呼び出し、これを 100 回ループする。

平均値と標準偏差、そしてそれぞれの信頼度 95% での上限値と下限値(統計素人なので用語がおかしいかも)を表示する。外れ値が標準偏差にどのくらい影響しているかも表示する。

time コマンドを使って、プロセス開始から終了までの経過時間を測定するのと比べると、だいぶ賢く計測するので、「ちゃんと計測したぜ」感が出せる。

ただし、計測対象のコードを正しく書くことが当然必要。今回の場合、Leftist Heap に突っ込む乱数データの生成が測定対象に入っているのかいないのかよくわからない(遅延評価なので)。どっちにしろ Right が優位なのは変わらないが。

0 件のコメント:

コメントを投稿