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

Question

在解决一些项目Euler问题以学习Haskell(所以目前我是一个完全初学者)时,我遇到了问题12.我写了这个(天真的)解决方案:

--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程序的哪一部分很慢？像一个简单的探查器.

为了明确这一点,我不要求为更快的解决方案,但对于一个办法找到这个解决方案.如果你没有哈斯克尔的知识,你会如何开始？

我试着编写两个triaList函数但是没有办法测试哪一个更快,所以这就是我的问题开始的地方.

谢谢

Answer 1

如何找出这个解决方案为何如此缓慢的原因.有没有命令告诉我大部分计算时间花在哪里,所以我知道我的haskell程序的哪一部分很慢？

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

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

使用时间和空间分析的教程是Real World 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, 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 -p -hy来分解这些分配,这会创建A.hp,您可以通过将其转换为postscript文件(hp2ps -c A.hp)来查看,生成:

这告诉我们你的内存使用没有任何问题:它是在恒定空间中分配的.

所以你的问题是numDivs的算法复杂性:

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

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

优化

这个表达式是流融合优化的一个很好的候选者,因此我将重写它以使用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 - 制作Z.hs

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

因此它将N = 150的运行时间减少了3.5倍,而没有改变算法本身.

结论

你的问题是numDivs.这是100%的运行时间,并且具有可怕的复杂性.想想numDivs,以及例如,对于每N个生成[2 .. n div2 + 1] N次的方式.请记住,因为值不会改变.

要测量哪些功能更快,请考虑使用标准,该标准将提供有关运行时间亚微秒改进的统计上可靠的信息.

附加物

由于numDivs是你运行时间的100%,触摸程序的其他部分不会有太大的区别,但是,出于教学目的,我们也可以使用流融合来重写它们.

我们还可以重写trialList,并依靠fusion将其转换为您在trialList2中手动编写的循环,这是一个"前缀扫描"函数(aka scanl):

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

溶胶类似:

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

与整体运行时间相同,但代码有点清晰.

Answer 2

通过直接解决问题,Dons的答案很棒而且不会成为扰流板.
在这里,我想建议一个我最近写的小工具.当您需要比默认配置文件更详细的配置文件时,它可以节省您手动编写SCC注释的时间ghc -prof -auto-all.除此之外,它色彩缤纷!

以下是您给出的代码示例(*),绿色表示正常,红色表示缓慢:

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

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