为什么这个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

我怀疑在内存上填充一个 256*256*16 的数组不应该需要 0.7 秒，所以我用 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 倍大约是课程的标准。

要获得更好的性能，请使用矢量库：

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

Answer 2

对不起，我想只有我才能正确回答这个问题。对于任何好奇的人来说，原因与代码无关，但事实上，当我对它们进行基准测试时，GHC 并没有用-O2重新编译我自动构建的二进制文件。解决方案是使用 force-rrecomp 标志：

ghc -fforce-recomp -O2 bench.hs -o bench

#haskell@ freenode上的人建议的一个更好的解决方案是正确设置阴谋集团，并使用它进行构建。

Answer 3

这对于评论来说太大了，但不是真正的答案。您的导入有点烦人，我还压制了-Wall的警告（当您查看性能时要注意）：

module Main where
import Data.Array.Unboxed
import Data.Array.ST
import Data.Array.Unsafe
import Control.Monad.ST
import Control.Monad
import Data.List
size :: Int
size = 256*256*16
ar :: UArray Int Int
ar = runST $ do
    a <- newArray (0,size) 0 :: ST s (STUArray s Int Int)
    forM_ [0..size] $ i -> do
        writeArray a i i 
    unsafeFreeze a
arrSum :: Int
arrSum = foldl' ( s i -> s + (ar ! i)) 0 [0..size-1]
main :: IO ()
main = print arrSum

对于Haskell和Node重复：

jberryman /tmp » time ./t         
-524288
./t  0.04s user 0.01s system 92% cpu 0.056 total
jberryman /tmp » time nodejs t.js 
549755289600
nodejs t.js  0.19s user 0.01s system 100% cpu 0.200 total

对于 GHC 7.8 和 7.6，我得到的时间基本相同（我必须import Data.Array.ST hiding (unsafeFreeze)，但除此之外代码是相同的）。

编辑：哎呀，看我不是很善于观察;请注意，在我的32位机器上，计数在Haskell中溢出，但在JS中没有溢出，所以我们有另一个苹果到橙子;这里可能Integer更公平的比较。

我绝对推荐进行任何类型的微观基准测试的标准，否则您将浪费大量时间。

此外，我不相信您有在C版本中初始化数组的开销，因此这不是一个公平的比较。