単純なHaskellパフォーマンス解析

Question

私はバイナリ検索ツリーでN番目に小さい番号を見つける2つの実装の性能を比較しようとしています。これは単なるおもちゃの学習問題です。測定での私のナイーブの試みは、次のとおりです。

私は私がそれをしたい怠惰を含め、私がいないところ、それを防ぐ方法を考え出す苦労しています

getNth :: Tree Int -> Int -> Either String Int 

eval :: [Either b Int] -> Int 
eval = (foldl (+) 0) . rights 

main :: IO() 
main = do 
    let t = foldl treeInsertBalanced EmptyTree [1..1000000] 
     first = getNth t 100000 
     iterations = 100000000000 
     second = take iterations $ repeat $ getNth t 100 
     third = take iterations $ repeat $ getNth' t 100 

    print $ "dummy to cause eval: " ++ (show first) 
    print "" 

    time1 <- System.CPUTime.getCPUTime 
    print $ eval second 
    time2 <- System.CPUTime.getCPUTime 
    print $ eval third 
    time3 <- System.CPUTime.getCPUTime 

    let secondTime = time2-time1 
     thirdTime = time3-time2 
     timeDiff = secondTime - thirdTime 
    print $ "take version = " ++ (show secondTime) 
    print $ "opt version = " ++ (show thirdTime) 
    print $ "diff   = " ++ (show timeDiff) 

。

ツリーを完全に構築してから、そのツリーで操作する関数の測定を開始します。このため、getNthを呼び出して印刷することで、tの評価を強制しようとしています。

1. これは私が望んでいることをやっているのですか？
2. 後で使用すると完全に評価されます。

2つのgetNth関数の実装の違いは、ツリーの単純な深さの最初の検索で最初の関数が 'take'関数を使用することです。 2番目の方法は明示的な早期リターンで深さの最初の検索を行います。シンプルな「テイク」の実装がツリー全体を歩かなければならないかどうかを知りたい。どのようにすれば、2つの機能の性能を測定するより簡単な方法でそれを判断できますか。ツリー内の値として「エラー」または「未定義」を導入しようとしましたが、ツリーのN番目の要素でない限り評価されませんでした。 getNth関数が本当に怠惰であるかどうかを判断する別の簡単な方法はありますか？ （http://pastebin.com/jpg0vSNdで.lhsとして入手可能）

Answer 1

いくつかの観察：値のevalutionを強制する

1. 良い方法は、Control.DeepSeqからdeepseqを使用することです。

2. repeatそれは議論を再評価しません。

3. GHCは同じものを検出するのにはかなり良いので、GHCが関数呼び出しを再評価するために同じ引数で関数呼び出しを偽装しなければならないことがあります。ここで

はdeepseqを使用した例である：

import Control.DeepSeq (deepseq) 
import Control.Monad 
import Debug.Trace 
import System.TimeIt 
import System.Environment 

theList = [1..8] ++ [undefined] ++ [10] :: [Int] 

main1 = do 
    print $ length theList 
    print $ deepseq theList (length theList) 

最初print文が10を発します。 deepseq呼び出しがundefined要素を評価しようとしたため、2番目の例外がスローされます。

この例を検討し、repeatを再評価して、引数だしないことを確認するには、次の

foo = repeat $ trace "(here)" 2 

main2 = print $ take 3 foo 

main2の実行結果は次のとおりです。何が起こっている

[(here) 
2,2,2] 

は、そのときの頭でありますfooが呼び出され、repeatが評価されます。これはtraceを呼び出し、(here)を出力し、2を返します。残りのリストfooが必要な場合、この値はrepeatで保存されます。

最後に、同じarguemntを持つ関数呼び出しの呼び出しで、GHCがどれだけ優れているかを示します。

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

theN = 34 -- use 24 if running under ghci 

compute1 = fib theN 
compute2 k = fib theN 
compute3 k = fib (k+theN-k) 

fib theN実行時間は、あなたが-O2かでコンパイルするかどうかに依存して（約0.6秒）を計算するためには時間がかかるだけで関数呼び出し

loop1 n = forM_ [1..n] $ \_ -> print compute1 
loop2 n = forM_ [1..n] $ \k -> print (compute2 k) 
loop3 n = forM_ [1..n] $ \k -> print (compute3 k) 

timeLoop loop = do timeIt $ loop 1 
        timeIt $ loop 2 
        timeIt $ loop 3 
        timeIt $ loop 10 

main4 = timeLoop loop1 
main5 = timeLoop loop2 
main6 = timeLoop loop3 

main = do (arg:_) <- getArgs 
      case arg of 
      "4" -> main4 
      "5" -> main5 
      "6" -> main6 

です。 典型的なreutsは以下のとおりです。

  w/o -O2 with -O2 
main4  1 secs 0.1 sec 
main5 13 secs 0.1 sec 
main6 13 secs 1.0 sec 

いくつかの結論：compute1のようなトップレベルの式がメモ化され

• 。
• 無視されたパラメータ（例：compute2）を追加すると、-O2が使用されていない場合、GHCはファンクションコールを再計算します。
• -O2を使用すると、ループ内でGHCを再評価するために、関数呼び出しを偽装するトリッキーな方法が必要な場合があります。