用於分析Haskell程序性能的工具

Question

在解決一些Project Euler問題以學習Haskell（所以目前我是一個完全初學者）時，我超過了Problem 13。我寫這個（天真）解決方案：

--Get Number of Divisors of n 
numDivs :: Integer -> Integer 
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2 

--Generate a List of Triangular Values 
triaList :: [Integer] 
triaList = [foldr (+) 0 [1..n] | n <- [1..]] 

--The same recursive 
triaList2 = go 0 1 
    where go cs n = (cs+n):go (cs+n) (n+1) 

--Finds the first triangular Value with more than n Divisors 
sol :: Integer -> Integer 
sol n = head $ filter (\x -> numDivs(x)>n) triaList2 

這種解決方案對於n = 500（SOL 500）的極端慢（運行2個多小時了），所以我不知道如何找出爲什麼這個解決方案是這樣慢。是否有任何命令告訴我大部分計算時間花在哪裏，因此我知道我的haskell程序的哪個部分很慢？就像一個簡單的分析器。

要清楚，我不要求爲更快的解決方案，但對於的方式找到這個解決方案。如果你沒有Haskell知識，你會如何開始？

我試着寫兩個triaList函數，但沒有辦法測試哪一個更快，所以這就是我的問題開始。

感謝

Answer 1

如何找出爲什麼這個解決方案如此之慢。是否有任何命令告訴我大部分計算時間花在哪裏，因此我知道我的haskell程序的哪個部分很慢？

準確！ GHC提供了許多優秀的工具，包括：

• runtime statistics
• time profiling
• heap profiling
• thread analysis
• core analysis.
• comparative benchmarking
• GC tuning

關於使用時間和空間分析的教程是part of Real World Haskell。

GC統計

首先，確保你使用GHC -02編譯。您可以確保它是現代GHC（例如GHC 6.12.x）

我們可以做的第一件事是檢查垃圾回收是不是問題。 運行程序與+ RTS -s

$ time ./A +RTS -s 
./A +RTS -s 
749700 
    9,961,432,992 bytes allocated in the heap 
     2,463,072 bytes copied during GC 
      29,200 bytes maximum residency (1 sample(s)) 
     187,336 bytes maximum slop 
       **2 MB** total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 19002 collections,  0 parallel, 0.11s, 0.15s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 13.15s (13.32s elapsed) 
    GC time 0.11s ( 0.15s elapsed) 
    RP time 0.00s ( 0.00s elapsed) 
    PROF time 0.00s ( 0.00s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 13.26s (13.47s elapsed) 

    %GC time  **0.8%** (1.1% elapsed) 

    Alloc rate 757,764,753 bytes per MUT second 

    Productivity 99.2% of total user, 97.6% of total elapsed 

./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total 

這已經給了我們很多的信息：你只有2M堆和GC佔據了0.8％的時間。所以不必擔心分配問題。

時間輪廓

獲得你的程序的時間曲線直線前進：與-prof - 自動所有

$ ghc -O2 --make A.hs -prof -auto-all 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

編譯而且，對於N = 200：

$ time ./A +RTS -p     
749700 
./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total 

它創建一個文件，A.prof，包含：

Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final) 

     A +RTS -p -RTS 

    total time =  13.18 secs (659 ticks @ 20 ms) 
    total alloc = 4,904,116,696 bytes (excludes profiling overheads) 

COST CENTRE   MODULE   %time %alloc 

numDivs   Main   100.0 100.0 

指示全部您的時間花在numDivs上，它也是所有分配的來源。

堆型材

您還可以得到這些分配的分解，通過與+ RTS-HY -p，創造A.hp，您可以通過將其轉換爲PostScript文件查看正在運行（hp2ps -c A.hp），產生：

它告訴我們沒有什麼不對您的內存使用：它是在不斷的空間分配。

所以你的問題是算法numDivs的複雜性：

toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2 

解決這個問題，這是你的運行時間爲100％，和其他一切很容易。

優化

這表達了stream fusion優化的一個很好的候選人，所以我把它改寫 使用Data.Vector，像這樣：

numDivs n = fromIntegral $ 
    2 + (U.length $ 
     U.filter (\x -> fromIntegral n `rem` x == 0) $ 
     (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int)) 

這應該融合成一個單一的環沒有不必要的堆分配。也就是說，它比列表版本具有更好的複雜性（通過不變的因素）。您可以使用ghc-core工具（對於高級用戶）在優化後檢查中間代碼。

測試這個，ghc -O2 --make Z.hs

$ time ./Z  
749700 
./Z 3.73s user 0.01s system 99% cpu 3.753 total 

因此，它將運行時間減少了3.5倍，而不改變算法本身。

結論

你的問題是numDivs。它是你運行時間的100％，並且具有可怕的複雜性。 想一想numDivs，以及如何爲您生成的每個N [2 .. n div 2 + 1] N次。 嘗試記憶，因爲值不會改變。

要測量您的哪些功能更快，請考慮使用criterion，這將提供關於運行時間的亞微秒改進的統計學健壯信息。

---

附錄

由於numDivs是你的運行時間100％，觸及程序的其它部分將沒有太大的差別，但是 ，用於教學目的，我們還可以使用那些重寫流融合。

我們也可以重寫trialList，並依靠融合把它變成是一個「前綴掃描」功能（又名scanl）你trialList2手工編寫的循環， ：

triaList = U.scanl (+) 0 (U.enumFrom 1 top) 
    where 
     top = 10^6 

同樣，對於sol：

sol :: Int -> Int 
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList 

與整體運行時間相同，但代碼更簡潔一點。

Answer 2

哈斯克爾相關注意事項：triaList2當然比triaList更快，因爲後者執行了很多不必要的計算。需要二次時間來計算triaList的n個第一元素，但是對於triaList2線性計算。還有一種優雅（高效的）的方式來定義三角形數的無限懶惰列表：

triaList = 1 : zipWith (+) triaList [2..] 

數學相關的注意事項：沒有必要檢查所有除數達N/2，這是不夠的檢查達SQRT（N）。

Answer 3

您可以使用標誌運行程序以啓用時間分析。例如：

./program +RTS -P -sprogram.stats -RTS 

這應該運行該程序並生成一個名爲program.stats的文件，這將在每個函數中花費多少時間。您可以在GHC user guide中找到有關使用GHC分析的更多信息。對於基準測試，有Criterion庫。我發現this博客文章有一個有用的介紹。

Answer 4

Dons的答案很好，不會因爲直接解決問題而成爲一個擾流板。
這裏我想提一下我最近寫的一點tool。當您想要比默認的ghc -prof -auto-all更詳細的配置文件時，它可以節省您手動編寫SCC批註的時間。除此之外，它是多彩的！

這裏是你給了代碼（*）爲例，綠色正常，紅色爲慢：

所有時間的推移創建除數的列表。這表明你可以做一些事情：
1.使過濾n rem x == 0更快，但由於它是一個內置函數，可能它已經很快了。
2.創建一個較短的列表。您已經完成了該方面的工作，只檢查最多n quot 2。
3.完全丟棄列表生成，並使用一些數學來獲得更快的解決方案。這是項目歐拉問題的常用方法。 （*）我通過將你的代碼放入一個名爲eu13.hs的文件中，添加了一個主函數main = print $ sol 90。然後運行visual-prof -px eu13.hs eu13，結果在eu13.hs.html。