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

在解决一些项目欧拉问题来学习Haskell(所以目前我是一个完全初学者),我来到问题13 。 我写了这个(天真的)解决scheme:

--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 

这个解决schemen = 500(sol 500)极其缓慢(现在运行了2个多小时),所以我想知道如何找出这个解决scheme为什么这么慢。 有没有什么命令可以告诉我大部分的计算时间是花在什么地方,所以我知道我的haskell程序的哪个部分很慢? 就像一个简单的分析器。

为了说清楚,我并不是要求更快的解决scheme,而是寻求解决scheme。 如果你没有Haskell知识,你将如何开始?

我试图写两个triaList函数,但没有办法testing哪一个更快,所以这就是我的问题开始。

谢谢

如何找出为什么这个解决scheme如此缓慢。 有没有什么命令可以告诉我大部分的计算时间是花在什么地方,所以我知道我的haskell程序的哪个部分很慢?

恰恰! GHC提供了许多优秀的工具,包括:

  • 运行时统计
  • 时间分析
  • 堆分析
  • 线程分析
  • 核心分析。
  • 比较基准
  • GC调谐

关于使用时间和空间分析的教程是真实世界Haskell的一部分 。

GC统计

首先,确保你用ghc -O2编译。 你可以确定它是一个现代的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 -auto-all进行编译

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

而且,对于N = 200:

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

创build一个文件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上,也是你所有分配的来源。

堆configuration文件

您也可以通过运行+ RTS -p -hy(创buildA.hp,通过将其转换为后记文件(hp2ps -c A.hp)来查看)来分解这些分配,从而生成:

替代文字

这告诉我们你的内存使用没有任何问题:它在不变的空间分配。

所以你的问题是numDivsalgorithm的复杂性:

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

解决这个问题,这是你运行时间的100%,其他一切都很简单。

优化

这个expression式是stream融合优化的一个很好的候选者,所以我会重写它来使用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工具(对于高级用户)来优化后检查中间代码。

testing这个,ghc -O2 – 制作Z.hs

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

所以它将运行时间缩短了3.5倍,而不改变algorithm本身。

结论

你的问题是numDivs。 这是你运行时间的100%,并且具有非常复杂的可怕性。 想一想numDivs,以及如何为你生成N个N的每个N。 尝试记忆,因为值不会改变。

为了测量哪些函数更快,可以考虑使用标准 ,这将提供关于运行时间的亚微秒级改进的统计学上可靠的信息。


附加物

由于numDivs是你运行时间的100%,所以触摸程序的其他部分不会有太大的差别,但是为了教学目的,我们也可以用stream融合来重写。

我们也可以重写trialList,并依靠融合把它变成你在trialList2中手工编写的循环,它是一个“前缀扫描”函数(aka scanl):

 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 

与整体运行时间相同,但代码更简洁一些。

Dons的答案很好,没有通过直接解决问题而成为一个破坏者。
在这里我想提出一个我最近写的一个小工具 。 当您需要比默认的ghc -prof -auto-all更详细的configuration文件时,它可以节省您手动编写SCC批注的时间。 除此之外,它是多彩的!

下面是你给出的代码(*)的例子,绿色是好的,红色是慢的: 替代文字

一直在创build除数列表。 这表明你可以做一些事情:
1.更快地过滤n rem x == 0 ,但由于它是一个内置函数,所以它可能已经很快了。
2.创build一个较短的列表。 你已经在这个方向上做了一些事情,只检查最多n quot 2
3.完全丢弃列表生成,并使用一些math来获得更快的解决scheme。 这是项目欧拉问题的常用方法。

(*)我把这个代码放在一个名为eu13.hs的文件中,添加一个主函数main = print $ sol 90 。 然后运行visual-prof -px eu13.hs eu13 ,结果在eu13.hs.html

Haskell相关说明: triaList2当然比triaList快,因为后者执行了大量不必要的计算。 它将花费二次时间来计算triaList第一个元素,但对triaList2线性的。 还有另外一个优雅(而且有效)的方法来定义一个三angular形数字的无限懒惰列表:

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

math相关的注意事项:没有必要检查所有除数到n / 2,只要检查sqrt(n)就足够了。

您可以使用标志运行程序以启用时间分析。 像这样的东西:

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

这应该运行程序并生成一个名为program.stats的文件,这将花费多less时间在每个函数中。 您可以在GHC 用户指南中find更多关于GHC分析的信息。 对于基准testing,有Criterion库。 我发现这个博客文章有一个有用的介绍。