GHC 8 中的 Foldl 内存性能。0.x

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，它们本质上是未完成的计算，最终将保持正确的值。本质上，当尝试计算 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 占用的内存比 space 多于你的 RAM 和你的程序崩溃来说是很大的。