GHC 8.0.x中的Foldl内存性能

Question

在检查我正在处理的一些代码的内存使用情况时,我遇到了一个奇怪的问题.

使用foldl总和一个非常大的列表的元素,我得到一个恒定的内存使用.

使用foldl'我也得到一个恒定的内存使用(如预期的那样).

使用foldr内存增长并使我的系统屈膝(没有像我期望的堆栈溢出异常).

触发它所需的最小代码是: main = print $ foldx (+) 0 [1..100000000000000000000]

foldx是哪个foldl,foldr或者foldl'

我的印象是(按照Foldr Foldl Foldl的说法),情况恰恰相反.

我用上述代码设置了一个repo:https: //github.com/framp/hs-fold-perf-test

这里发生了什么？是GHC 8.0.x太聪明了吗？我在macOS Sierra上

谢谢

Answer 1

foldl 和 foldl'

在这种情况下,GHC认为foldl可以严格并且基本上重写它以便利用foldl'.请参阅下文GHC如何优化foldl构造.

请注意,这仅适用于您使用优化进行编译-O.没有优化,foldl程序会消耗我所有的内存和崩溃.

查看输出,ghc -O -fforce-recomp -ddump-simpl foldl.hs我们可以看到GHC消除了完全使用的巨大列表,并将表达式优化为尾递归函数:

Rec {
-- RHS size: {terms: 20, types: 5, coercions: 0, joins: 0/0}
Main.main_go [Occ=LoopBreaker] :: Integer -> Integer -> Integer
[GblId, Arity=2, Str=<S,U><S,1*U>]
Main.main_go
  = \ (x_a36m :: Integer) (eta_B1 :: Integer) ->
      case integer-gmp-1.0.0.1:GHC.Integer.Type.gtInteger#
             x_a36m lim_r4Yv
      of wild_a36n
      { __DEFAULT ->
      case GHC.Prim.tagToEnum# @ Bool wild_a36n of {
        False ->
          Main.main_go
            (integer-gmp-1.0.0.1:GHC.Integer.Type.plusInteger
               x_a36m 1)
            (integer-gmp-1.0.0.1:GHC.Integer.Type.plusInteger eta_B1 x_a36m);
        True -> eta_B1
      }
      }
end Rec }

这解释了为什么它以恒定的内存使用率运行.

为什么foldr需要那么多记忆？

foldr构建了很多thunk,这些thunk本质上是未完成的计算,最终将保持正确的值.从本质上讲,当尝试评估foldr表达式时,会发生以下情况:

foldr (+) 0 [1..100]
== (+) 1 $ foldr 0 [2..100]
== (+) 1 $ (+) 2 $ foldr [3..100]
...
== (+) 1 $ (+) 2 $ .. $ (+) 99 $ (+) 100 0 -- at this point there are 100
== (+) 1 $ (+) 2 $ .. $ (+) 99 $ 100       -- unevaluated computations, which
== (+) 1 $ (+) 2 $ .. $ (+) 199            -- take up a lot of memory
...
== (+) 1 $ 5049
== 5050

100000000000000000000对于thunk来说,占用更多空间而不是内存并且编程崩溃的限制很大.