performance - 懒惰列表的 Haskell 性能不佳

Question

我试图测试 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 不知道加法是关联的吗？有没有办法让它看到并使用它？

Answer 1

首先，在谈论性能时不要费心讨论 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 工作，如果您希望有选择地实现相同的结果，可以做到这一点。