haskell - 在Haskell中避免分配

Question

我正在开发一个更复杂的程序，我想提高效率，但是我现在将我的担忧归结为以下简单程序：

main :: IO ()
main = print $ foldl (+) 0 [(1::Int)..1000000]

在这里，我构建并运行它。

$ uname -s -r -v -m
Linux 3.12.9-x86_64-linode37 #1 SMP Mon Feb 3 10:01:02 EST 2014 x86_64
$ ghc -V
The Glorious Glasgow Haskell Compilation System, version 7.4.1
$ ghc -O -prof --make B.hs
$ ./B +RTS -P
500000500000
$ less B.prof
        Sun Feb 16 16:37 2014 Time and Allocation Profiling Report  (Final)

           B +RTS -P -RTS

        total time  =        0.04 secs   (38 ticks @ 1000 us, 1 processor)
        total alloc =  80,049,792 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc  ticks     bytes

CAF         Main    100.0   99.9     38  80000528


                                                      individual     inherited
COST CENTRE MODULE                  no.     entries  %time %alloc   %time %alloc  ticks     bytes

MAIN        MAIN                     44           0    0.0    0.0   100.0  100.0      0     10872
 CAF        Main                     87           0  100.0   99.9   100.0   99.9     38  80000528
 CAF        GHC.IO.Handle.FD         85           0    0.0    0.0     0.0    0.0      0     34672
 CAF        GHC.Conc.Signal          83           0    0.0    0.0     0.0    0.0      0       672
 CAF        GHC.IO.Encoding          76           0    0.0    0.0     0.0    0.0      0      2800
 CAF        GHC.IO.Encoding.Iconv    60           0    0.0    0.0     0.0    0.0      0       248

每次迭代似乎分配了80个字节。我认为期望编译器在此处生成无分配代码是很合理的。

我的期望不合理吗？分配是否有启用分析的副作用？我该如何整理事情以摆脱分配？

Answer 1

在这种情况下，GHC看起来足够聪明，可以将foldl优化为更严格的形式，但是GHC无法优化中间列表，因为foldl不是good consumer，因此推测这些分配是针对< cc>构造函数。 （EDIT3：不，看起来并非如此；请参阅评论）

通过使用(:)融合踢，您可以摆脱中间列表：

main :: IO ()
main = print $ foldr (+) 0 [(1::Int)..1000000]

...如你看到的：

       k +RTS -P -RTS

    total time  =        0.01 secs   (10 ticks @ 1000 us, 1 processor)
    total alloc =      45,144 bytes  (excludes profiling overheads)

对我来说具有相同的内存配置文件

main = print $ (1784293664 :: Int)

编辑：在这个新版本中，我们正在交易堆栈中一堆 foldr的堆分配。为了真正获得一个好的循环，我们必须像这样手工编写它：

main = print $ add 1000000

add :: Int -> Int
add nMax = go 0 1 where
    go !acc !n
        | n == nMax = acc + n
        | otherwise = go (acc+n) (n+1)

显示：

    total time  =        0.00 secs   (0 ticks @ 1000 us, 1 processor)
    total alloc =      45,144 bytes  (excludes profiling overheads)

EDIT2我还没有使用Gabriel Gonzalez foldl library，但是对于您的应用程序可能也值得一试。