为什么这个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_，我相信它们被编译成了无堆栈代码。那么，这里的低效率源自何处呢？

- MaiaVictor

---

7.8.4在Yosemite上... - MaiaVictor

对我来说，Haskell版本是12毫秒（使用Criterion），C版本是4.2毫秒（使用<time.h>中的timespec）。 - András Kovács

你的机器和编译选项是什么？你没有改变代码吗？ - MaiaVictor

GHC 7.8.4，x64 Linux，-O2 -fllvm。没有LLVM的话是12.3毫秒。代码没有改变。 - András Kovács

@AndrásKovács，你可以在回答中建议这种风格 :) 但是为什么会有开销呢？为什么没有一种不带开销的累加计算函数呢？ - MaiaVictor

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

- ErikR

---

当我玩弄数组代码时，我自己写了这个。多么美妙的API啊 : ) 请记住，“foldl1'”也适用于非装箱向量：“V.foldl1' (+) vec”。 - John Tyree

Answer 2

抱歉，我想只有我能回答这个问题。对于任何好奇的人，原因与代码无关，而是因为GHC在我对自动构建的二进制文件进行基准测试时未使用-O2重新编译。解决方法是使用force-rrecomp标志：

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

一个更好的解决方案，由#haskell @ freenode上的人们建议，是正确地设置Cabal，并使用它进行构建。

- MaiaVictor

---

你也可以执行 touch bench.hs; ghc -O2 bench.hs -o bench。如果你正在编译多个模块，这将让你只重新编译需要的那个模块。当我想要执行 -ddump-simpl 这样的操作时，我倾向于使用这种方法。 - dfeuer

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，我基本上得到了相同的时间（在 7.6 中，我必须import Data.Array.ST hiding (unsafeFreeze)，但是代码基本相同）。

编辑：哎呀，看我没注意，注意到在我的 32 位机器上，Haskell 中的计数会溢出，但在 JS 中不会，所以我们又有了另一种不可比性；这里可能更公平的比较应该使用 Integer。

我强烈推荐使用 criterion 进行任何类型的微基准测试，否则你就会浪费很多时间。

此外，我不认为在 C 版本中初始化数组会有开销，因此这不是一个完全公平的比较。

- jberryman

---

整数可能有点过头了...也许只需要一个Double，因为这是JavaScript使用的类型。对于导入问题感到抱歉... - MaiaVictor