Haskell中的PINNED内存或STACK内存对性能有何影响？

Question

Haskell中的PINNED内存或STACK内存对性能有何影响？

3

我正在尝试从 GHC（8.4.3）中的优化中受益，其中大量数据的“构建”存储在固定内存中。（这里可能术语不完全正确）。下面是一个简单的例子：

Pinned1.hs:

main = print $ sum $ tail ([1..100000000] :: [Int])

然后：

ghc -O2 Pinned1.hs -prof -rtsopts
Pinned1 +RTS -hc -p -xt
hp2ps -e8in -c Pinned1.hp

展示了约40K的固定内存使用，几乎没有堆栈使用，而Pinned1 +RTS -hd -p -xt则显示这约40K是ARR_WORDS。

Pinned1.prof显示：

total time  =        2.14 secs   (2137 ticks @ 1000 us, 1 processor)
total alloc = 8,000,046,088 bytes  (excludes profiling overheads)

通过查看-sdump-simpl，我可以看到导致这种情况的代码类型。以下是一个稍微复杂一些的例子，从Core反向翻译成Haskell代码，其中发生了同样的事情：

Pinned2.hs:

main = print $ sum $ snd $ wgoC 1 0
wgoC :: Int -> Int -> (Int, [Int])
wgoC n finalState =
  let (nxt, ys') = case n of 100000000 -> (finalState, [])
                             _         -> wgoC (n+1) finalState
  in (n, n + nxt * 9: ys')

wgoC将下一个n传递回来，用于计算列表中的值。它报告了约40K的PINNED/ARR_WORDS内存，几乎没有STACK，并输出以下配置文件：

total time  =        5.50 secs   (5500 ticks @ 1000 us, 1 processor)
total alloc = 16,800,046,112 bytes  (excludes profiling overheads)

然而，这个：

Pinned3.hs:

main = print $ sum $ snd $ wgoD 1 0
wgoD :: Int -> Int -> (Int, [Int])
wgoD n finalState =
  let (ttl', ys') = case n of 100000000 -> (finalState, [])
                              _         -> wgoD (n+1) finalState
  in (ttl' + n, n + (ttl' + n) * 9 : ys')

在2分钟后没有完成。它只有一个值为1000000时才会完成，我看不到任何固定内存和堆栈使用（约100M）。（我认为是堆栈使用使其运行速度变慢了。）

我看到Pinned2和Pinned3之间的主要区别在于Pinned3包括来自返回状态的递归调用的信息（返回对的fst：后续值的累积和），但Pinned2仅包括参数wgoC。

所以我的问题是：

Q1）在编译器管道的哪个阶段决定使用固定内存？-ddump-simpl没有明显的区别，也没有-ddump-cmm（虽然有点复杂，所以可能我错过了什么）。

问题2：PINNED/STACK的决策基于什么？（我能找到的关于PINNED的唯一参考资料，比如this，说它对FFI调用很有用，但似乎它也被采用为这种“优化”）。

问题3：是否有一种修改Pinned3的方法，使其使用PINNED？

问题4：（作为最后的手段）是否有其他的Pinned3调整方法，以便有足够的STACK空间，并在合理的时间内运行？（天真地说，我希望与Pinned2具有类似的性能。）

【请注意，我只是想了解PINNED/STACK机制。我相信还有其他的方法可以编写Pinned3，使其融合得很好，几乎不需要任何内存，但这个问题不是关于那个的。】

谢谢！

- David

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- K. A. Buhr · Answer 1

固定内存在这里没有作用。

这个程序：

main = print $ sum $ tail ([1..100000000] :: [Int])

程序中没有直接使用任何固定内存。你看到的固定内存来自运行时系统本身的初始化。 GHC 的字节数组原语分配固定内存；在用户代码中，当使用 Data.Text 或 Data.ByteString 时，你最有可能看到固定内存的使用，因为它们都使用字节数组作为其内部实现。对于这个程序，我猜测标准输入和标准输出的 I/O 缓冲区是固定的，但也许是其他什么东西。无论如何，Int 列表不会固定任何东西。

像（几乎）所有的 Haskell 程序一样，Pinned1.hs 使用大量的堆和栈（各几 GB），但至关重要的是，它在分配内存的同时迅速释放它（或者如果你更喜欢谈论栈的话，“推”和“弹”速度相同）。Pinned2.hs 也是如此。这些程序正在正确地运行。

Pinned3.hs 的问题不在于它使用了堆栈而非固定内存，而是它使用的堆栈比 Pinned1 和 Pinned2 更多，并且在推入堆栈时没有及时弹出，导致堆栈积累。

那么，为什么 Pinned3 会积累堆栈呢？

一般来说，在递归调用中，如果递归调用的某个结果部分是函数应用程序的目标，当它返回并且评估该结果部分本身需要另一个递归调用时，堆栈就会积累。考虑以下程序：

eatStack 100000000 = 1
eatStack n = 1 + eatStack (n + 1)
main = print $ eatStack 1

使用以下编译和运行：

stack ghc -- -O2 -prof -rtsopts EatStack.hs
./EatStack +RTS -hd -p -xt
stack exec hp2ps -- -e8in -c EatStack.hp

这段程序会产生通常的金字塔形堆栈累积（峰值大约为1.4G）。问题在于递归调用eatStack (n+1)的返回值受到函数应用\x -> 1 + x的影响，而计算该结果本身需要进一步递归。也就是说，计算eatStack 0需要将\x -> 1 + x推入堆栈然后调用eatStack 1，但只有在将\x -> 1 + x推入堆栈并调用eatStack 2之前，eatStack 1才能返回其结果。结果是堆栈累积。

特别注意，构造函数应用是以不同的方式处理的。以下程序：

noStack 100000000 = []
noStack n = 1 : noStack (n + 1)
main = print $ last (noStack 1)

应用部分应用的构造函数 (:) 1 到递归结果 noStack (n+1) 使用无栈。（它似乎使用了40k的固定内存，但这实际上是运行时系统。EatStack 也使用了40k的固定内存。）在某些情况下（不在此处），像这样的构造函数应用会导致堆积累，但通常不会堆积栈。

对于你的 Pinned2 和 Pinned3 示例，类似的情况正在发生，尽管显然有点更加复杂。首先看一下 Pinned2，考虑评估 wgoC 1 0。匹配情况并将参数替换后，该评估等价于：

wgoC 1 0 = 
  let (nxt, ys') = wgoC 2 0
  in (1, 1 + nxt * 9 : ys')

当sum . snd要求列表的第一个元素，即thunk 1 + nxt * 9时，这将通过递归调用来强制评估nxt。因为这个返回值受到函数应用（即\x -> 1 + x * 9）的影响，所以会使用一些堆栈，但是递归调用的评估：

wgoC 2 0 = 
  let (nxt, ys') = wgoC 3 0
  in (2, 2 + nxt * 9 : ys')

立即返回本地绑定的nxt在wgoC 1 0调用中所需的值，即返回元组的第一个元素fst (wgoC 2 0) = 2，无需进一步递归。因此，我们获取该值2，弹出延续\x -> 1 + x * 9并将值传递给延续以产生1 + 2 * 9 = 19。这给出了列表的第一个元素，没有净堆栈使用。列表的其余部分，即在wgoC 1 0调用中本地绑定的ys'仍处于惰性求值环境2 + nxt * 9 : ys'中，由wgoC 2 0调用封闭。

当下一个元素被需要时，我们需要一些栈来对结果nxt应用递归(nxt, ys') = wgoC 3 0中的继续函数\x -> 2 + x * 9，但是这将以相同的方式进行评估，立即返回nxt = 3和一个ys'的thunk，因此继续函数\x -> 2 + x * 9将从栈中弹出并应用于nxt = 3而不需要进一步递归，得到2 + 3 * 9 = 29和由wgoC 3 0调用关闭的thunk 3 + nxt * 9：ys'。

每个元素都可以无需使用净堆栈进行强制操作。我们推入一个继续函数然后立即弹出它并将其应用于递归调用的返回值的某个部分，该部分本身不需要进一步递归。结果是没有净堆栈积累。

现在考虑Pinned3和调用wgoD 1 0：

wgoD 1 0 =
  let (ttl', ys') = wgoD 2 0
  in (ttl' + 1, 1 + (ttl' + 1) * 9 : ys')

当sum . snd要求列表的第一个元素，即thunk 1 + (ttl' + 1) * 9时，这将通过递归调用强制评估ttl'。因为有一个待处理的函数应用程序\x -> 1 + (ttl' + 1) * 9，这将使用一些堆栈。递归调用：

wgoD 2 0 =
  let (ttl', ys') = wgoD 3 0
  in (ttl' + 2, 2 + (ttl' + 2) * 9 : ys')

只能通过评估返回元组的第一个组件 ttl' + 2 来为本地绑定的 ttl' 在 wgoC 1 0 调用中提供所需的值，但这需要通过递归的 wgoD 3 0 调用来强制执行 ttl'。因为当它返回时，ttl' 受到函数应用 \x -> x + 2 的影响，我们稍微增加一点堆栈并继续评估：

wgoD 3 0 =
  let (ttl', ys') = wgoD 4 0
  in (ttl' + 3, 3 + (ttl' + 3) * 9 : ys')

为了在 wgoD 2 0 调用中本地绑定所需的 ttl'，我们需要评估从 wgoD 3 0 返回元组的第一个组件，即 ttl' + 3。这是一个函数应用 \x -> x + 3，我们将其推入堆栈，并应用于从递归调用 wgoD 4 0 返回的 ttl'。

所以，Pinned3将一系列的continuations \x -> x + 2、\x -> x + 3、\x -> x + 4等推到堆栈上，所有这些的目的都是为了计算由wgoD 2 0返回的元组的第一个组件，直到它到达wgoD 100000000 0，然后才最终得到一个数字finalState = 0作为第一个元组组件（如果有足够的堆栈跨越这个距离）。然后，当continuations被应用时，所有堆栈将被弹出，并且我们将得到列表的第一个元素！

一旦通过这一点，事情就不那么糟糕了。此时已经计算了所有表达式ttl' + n，它们可以在计算表达式n + (ttl' + n) * 9时重复使用，因此剩余的元素可以相对快速地生成。但是，由于它们的值必须被保留在某个地方，所以您还会以大约与堆栈使用率相同的速率获得累积的堆使用率。

你可以将100000000替换为类似于10000000（七个零）的数字，这将在合理的时间内运行，并显示堆栈和堆的累积成金字塔形状; 它的峰值约为1.4 GB，然后再降至零。

我没有看到任何真正简单的方法来“修复”这个问题，同时仍然保持Pinned3算法结构不变。