用于分析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。