使用惰性列表的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.使用-OxGHCi标志是无稽之谈.

你正在建立一个巨大的计算

使用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托儿所,misc初始化等).如果您想要精确测量小型Haskell计算,请使用Criterion(基准测试工具).

与C相比

我的gcc -O3时间是不可估量的低(报告为0.002秒),因为主程序包含4个指令 - 整个计算在编译时进行评估,常量0x746a5a2920存储在二进制中.

有一个相当长的Haskell线程(在这里,但它是一个史诗般的火焰战争的东西,仍然在人们的思想中燃烧近3年后),人们从你的确切基准开始讨论在GHC中这样做的现实 - 它不是'但是他们确实提出了一些模板Haskell工作,如果你想有选择地达到相同的结果,它会做到这一点.