我试图测试 Haskell 的性能,但得到了一些出乎意料的糟糕结果:
-- main = do
-- putStrLn $ show $ sum' [1..1000000]
sum' :: [Int] -> Int
sum' [] = 0
sum' (x:xs) = x + sum' xs
我首先从
ghci -O2
运行它:> :set +s
> :sum' [1..1000000]
1784293664
(4.81 secs, 163156700 bytes)
然后我用
ghc -O3
编译了代码,使用 time
运行它得到了这个:1784293664
real 0m0.728s
user 0m0.700s
sys 0m0.016s
不用说,与 C 代码相比,这些结果非常糟糕:
#include <stdio.h>
int main(void)
{
int i, n;
n = 0;
for (i = 1; i <= 1000000; ++i)
n += i;
printf("%d\n", n);
}
用
gcc -O3
编译后并使用 time
运行它我有:1784293664
real 0m0.022s
user 0m0.000s
sys 0m0.000s
性能如此差的原因是什么?我认为 Haskell 永远不会真正构建这个列表,我的假设错了吗?这是别的吗?
UPD:问题是 Haskell 不知道加法是关联的吗?有没有办法让它看到并使用它?
最佳答案
首先,在谈论性能时不要费心讨论 GHCi。废话用-Ox
带有 GHCi 的标志。
你正在建立一个巨大的计算
使用 GHC 7.2.2 x86-64 和 -O2
我得到:
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
使用如此多堆栈空间的原因是在您构建
i+...
表达式的每个循环中。 ,所以你的计算被转换成一个巨大的 thunk:n = 1 + (2 + (3 + (4 + ...
这将占用大量内存。标准是有原因的
sum
不像你的 sum'
那样定义.对
sum
的合理定义如果我改变你的
sum'
至 sum
或等效的,例如 foldl' (+) 0
然后我得到:$ ghc -O2 -fllvm so.hs
$ time ./so
500000500000
real 0m0.049s
这对我来说似乎完全合理。请记住,对于这么短的代码段,您测量的大部分时间都是噪音(加载二进制文件、启动 RTS 和 GC 苗圃、杂项初始化等)。如果您想要精确测量小型 Haskell 计算,请使用 Criterion(一种基准测试工具)。
对比 C
我的
gcc -O3
时间非常短(报告为 0.002 秒),因为主程序由 4 条指令组成 - 整个计算在编译时评估,常量 0x746a5a2920
存储在二进制文件中。有一个相当长的 Haskell 线程(here,但请注意,这是一场史诗般的火焰 war ,几乎 3 年后人们仍然在脑海中燃烧),人们从您的确切基准开始讨论在 GHC 中执行此操作的现实 - 它还没有,但他们确实提出了一些模板 Haskell 工作,如果您希望有选择地实现相同的结果,可以做到这一点。
关于performance - 懒惰列表的 Haskell 性能不佳,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8500021/