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

$time./a+rts-s
/A+RTS—S
七十四万九千七百
堆中分配的9961432992字节
GC期间复制的2463072字节
最大居住面积29200字节(1个样本)
最大坡度187336字节
**2 MB**正在使用的总内存(由于碎片而丢失0 MB)

第0代:19002个集合,0个并行,0.11秒,0.15秒
第1代:1个集合,0个并行,0.00s,0.00s已用

初始化时间0.00s(已过0.00s)
MUT时间13.15s(经过13.32s)
GC时间0.11s(0.15s)
RP时间0.00s(0.00s)
教授时间0.00s(0.00s)
退出时间0.00s(0.00s)
总时间13.26s(经过13.47s)

%GC时间**0.8%**(1.1%已用)

每秒分配速率757764753字节

生产力占总用户的99.2%,占总运行时间的97.6%

/A+RTS-S 13.26S用户0.05S系统98%CPU 13.479总计
< /代码> 

这已经给了我们很多信息:您只有一个200万的堆,GC占用了0.8%的时间。因此,无需担心分配问题。


时间配置文件


获取程序的时间配置文件是直接的:使用-prof-auto all编译

$ghc-o2--make a.hs-prof-auto all
[1/1]编译主(A.HS,A.O)
连接…
< /代码> 

当n=200时:

$time./a+rts-p
七十四万九千七百
/A+RTS-P 13.23S用户0.06S系统98%CPU 13.547总计
< /代码> 

创建一个文件a.prof,其中包含:

sun jul 18 10:08 2010时间和分配分析报告(最终)

A+RTS-P-RTS

总时间=13.18秒(20毫秒时659滴答)
总分配=4904116696字节(不包括分析开销)

成本中心模块%时间%分配

NumDivs主100.0 100.0
< /代码> 

表示您的时间花费在numdivs,它也是所有分配的来源。


堆配置文件


您还可以通过运行+rts-p-hy来获得这些分配的细分,它创建一个.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,like so:。


numdivs n=fromintegral$
2美元
u.filter(\x->fromintegral n`rem`x==0)$
(U.EnumFromn 2((FromIntegraln n`Div`2)+1)::U.Vector int)
< /代码> 

它应该融合成一个单独的循环,没有不必要的堆分配。也就是说,它将比列表版本具有更好的复杂性(按常量因子)。您可以使用GHC核心工具(对于高级用户)在优化后检查中间代码。


测试这个,ghc-o2——制造z.hs

$time./z
七十四万九千七百
/Z 3.73S用户0.01S系统99%CPU 3.753总计
< /代码> 

因此,它将n=150的运行时间减少了3.5倍,而不改变算法本身。


结论


你的问题是麻木。这是你100%的运行时间,而且非常复杂。考虑numdivs,例如,如何为生成的每个n生成[2..ndiv2+1]n次。
试着记住这一点,因为值不会改变。。


要测量哪个函数更快,请考虑使用criteria,它将提供有关运行时间亚微秒改进的统计可靠信息。




附录


因为numdivs是你运行时间的100%,触摸程序的其他部分不会有太大的区别,
然而,为了教学目的,我们也可以使用流融合重写那些内容。


我们还可以重写Triallist,并依靠Fusion将其转换为您在Triallist2中手工编写的循环,
这是一个“前缀扫描”功能(又名scanl):

trialist=U.scanl(+)0(U.EnumFrom 1 Top)
在哪里?
顶部=10 ^ 6
< /代码> 

同样,对于sol:

sol::int->int
sol n=U.head$U.filter(\x->numdivs x>n)三列表
< /代码> 

在相同的总体运行时间,但代码更干净一点。

太慢了。有没有命令告诉我大部分的计算时间花在哪里,这样我就知道我的haskell程序的哪个部分是慢的?


准确地说!GHC提供了许多优秀的工具,包括:


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


关于使用时间和空间分析的教程是part of Real World Haskell.

气相色谱统计

首先,确保您正在使用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


这已经给了我们很多信息:您只有一个200万的堆,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来获得这些分配的细分,它创建了一个.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核心工具(对于高级用户)在优化后检查中间代码。

测试这个,ghc-o2——制造z.hs

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


因此,它将n=150的运行时间减少了3.5倍,而不改变算法本身。

结论

你的问题是麻木。这是你100%的运行时间,而且非常复杂。考虑numdivs,以及如何为每个n生成[2..ndiv2±1次n次。
试着记住这一点,因为价值观不会改变。

要测量哪个函数更快,请考虑使用criterion这将提供有关运行时间亚微秒改进的统计可靠信息。



附录

因为numdivs是你运行时间的100%,触摸程序的其他部分不会有太大的区别,
然而,为了教学目的,我们也可以使用流融合来重写那些内容。

我们还可以重写Triallist,并依靠Fusion将其转换为您在Triallist2中手工编写的循环,
这是一个“前缀扫描”功能(又名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


总体运行时间相同,但代码更干净。