为什么这个Haskell数组填充操作如此之慢？

Question

对于特定的任务,我需要在可变数组中进行大量快速的单独写入.为了检查性能,我使用了以下测试:

size :: Int
size = 256*256*16

arr :: UArray Int Int
arr = runST $ do
    arr <- newArray (0,size) 0 :: ST s (STUArray s Int Int)
    forM_ [0..size] $ \i -> do
        writeArray arr i i 
    unsafeFreeze arr

arr_sum = foldl' (\ sum i -> sum + (arr ! i)) 0 [0..size-1]

main = print arr_sum

结果如下:

vh:haskell apple1$ ghc -O3 bench.hs -o bench; time ./bench
Linking bench ...
549755289600

real    0m0.748s
user    0m0.697s
sys 0m0.048s

我怀疑它不应该花0.7秒来填充内存上的256*256*16数组,所以我在JavaScript中测试了一个等效的程序:

size = 256*256*16;
x = new Array(size);
s = 0;
for (var i=0; i<size; ++i)
    x[i] = i;
for (var i=0; i<size; ++i)
    s += x[i];
console.log(s);

结果是:

vh:haskell apple1$ time node bench.js
549755289600

real    0m0.175s
user    0m0.150s
sys 0m0.024s

在C上,时间是0.012s,这是一个很好的下限.

#include <stdio.h>

#define SIZE (256*256*16)
double x[SIZE];

int main(){
    int i;
    double s = 0;
    for (i = 0; i<SIZE; ++i)
        x[i] = i;
    for (i = 0; i<SIZE; ++i)
        s += x[i];
    printf("%f",s);
};

所以这几乎证实了我的假设,即我的Haskell程序正在做其他事情,而不仅仅是填充数组并在之后对它进行求和.有可能是一个隐藏的堆的地方,但我不能确定它,因为我所用foldl'和forM_,我相信被编译到免费堆栈的代码.那么,这里效率低下的根源是什么？

Answer 1

GHC不会像你用C完成的那样产生很好的紧密循环.根据我的经验,在运行时间中,因子为3.

要获得更好的性能,请使用Vector库:

import qualified Data.Vector.Unboxed as V

size = 256*256*16 :: Int

doit = V.foldl' (+) 0 vec
  where vec = V.generate size id 

main = print doit