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 ，所以大概这些分配是针对(:)构造函数的。(EDIT3:不，看起来情况并非如此；请参阅评论)

通过使用 foldr 融合启动，您可以摆脱中间列表:

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)

编辑:在这个新版本中，我们将堆分配换成一堆 (1 + (2 + (3 +...))) 堆。为了真正获得一个好的循环，我们必须手动编写它，如下所示:

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但它也可能值得您的应用程序使用。