Haskell PINNED 或 STACK 内存以提高性能
Haskell PINNED or STACK memory for performance
我正在尝试从 GHC (8.4.3) 中有时发生的优化中获益，其中大量数据的“构建”被放入 PINNED 内存中。 （我这里可能没有正确的所有术语）。这是一个简单的例子：
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 PINNED 并且几乎没有使用 STACK，并且 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 内存，几乎没有堆栈，此配置文件输出：
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 的值完成，我没有看到 PINNED 内存和 STACK 使用（~100M）。 （我认为是 STACK 的使用使它 运行 慢得多，不知何故）。
我看到的Pinned2和Pinned3的主要区别在于Pinned3在返回状态中包含了递归调用的信息（返回对的fst：后续值的累加和），而Pinned2只包含参数到wgoC.
所以我的问题是：
Q1) 使用 PINNED 内存的决定发生在什么地方（在 compiler pipeline 中）？ -ddump-simpl 和 -ddump-cmm 没有明显区别（虽然它有点复杂，所以我可能遗漏了一些东西）。
Q2) PINNED/STACK的决定依据是什么？ （我能找到的关于 PINNED 的唯一参考资料，例如 this，说它对 FFI 调用很有用，但它似乎也被用于此“优化”）。
Q3) 有什么方法可以修改 Pinned3 使其使用 PINNED？
Q4)（作为最后的手段）是否对 Pinned3 进行了一些其他调整，以便有足够的堆栈 space，并在合理的时间内 运行s？ （天真地，我希望性能与 Pinned2 相似）。
[请注意，我只是想了解这里的 PINNED/STACK 机制。我敢肯定还有其他方法可以编写 Pinned3，因此它可以很好地融合并且几乎不需要任何内存，但这个问题与此无关。]
谢谢！
固定内存在这里不起作用。
这个程序：
main = print $ sum $ tail ([1..100000000] :: [Int])
不使用任何固定内存直接。您看到的固定内存来自 运行 时间系统本身的初始化。固定内存由 GHC 的字节数组原语分配；在用户代码中，您最有可能在使用 Data.Text 或 Data.ByteString 时看到固定内存使用情况，它们都使用字节数组进行内部实现。对于这个程序，我猜测 stdin 和 stdout 的 I/O 缓冲区是固定的，但也许是别的原因。无论如何，Int 的列表不会固定任何内容。
像（几乎）所有 Haskell 程序一样，Pinned1.hs 使用大量堆和大量堆栈（每个数以千兆字节计），但至关重要的是，在分配它时尽快释放它（或者如果在谈论堆栈时，您更喜欢“弹出”它就像它“推动”它一样快）。 Pinned2.hs也是如此。这些程序运行正常。
Pinned3.hs 的问题不在于它使用堆栈而不是固定内存，而是它使用比 Pinned1 和 Pinned2 更多的堆栈并且无法将其弹出推动它的速度很快，因此堆栈会累积。
那么，为什么Pinned3会累积堆栈？
一般来说，如果递归调用结果的某些部分是函数应用程序的目标，则堆栈在递归调用中累积 returns AND评估结果本身的那一部分需要另一个递归调用。考虑程序：
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
产生通常的 pyramid-shaped 堆栈累积（峰值为 1.4G 左右）。这里的问题是递归 eatStack (n+1) 调用的 return 值在 return 时受函数应用程序 \x -> 1 + x 的影响，并且计算该结果本身需要进一步递归。也就是说，计算eatStack 0需要在调用eatStack 1之前将\x -> 1 + x压入堆栈，而在调用[=之前将\x -> 1 + x压入堆栈后只能return其结果34=]，等等。结果就是堆栈堆积。
值得注意的是，构造函数应用程序的处理方式不同。以下程序：
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 求值。因为这个return值是受函数应用（即\x -> 1 + x * 9）的影响，所以使用了一点栈，但是递归调用的求值：
wgoC 2 0 =
let (nxt, ys') = wgoC 3 0
in (2, 2 + nxt * 9 : ys')
立即生成 wgoC 1 0 调用中本地绑定 nxt 所需的值，即 returned 元组 fst (wgoC 2 0) = 2 的第一个元素，无需进一步递归。因此，我们取值 2，弹出延续 \x -> 1 + x * 9 并将该值传递给延续以产生 1 + 2 * 9 = 19。这给出了列表的第一个元素，没有使用净堆栈。列表的其余部分，即 wgoC 1 0 调用中的本地绑定 ys'，仍处于由 wgoC 2 0 调用关闭的 thunk 2 + nxt * 9 : ys' 中。
当需要下一个元素时，我们需要一些堆栈来将延续 \x -> 2 + x * 9 应用到递归 (nxt, ys') = wgoC 3 0 中的结果 nxt，但这将被评估同样，立即 returning nxt = 3 和 ys' 的 thunk，因此延续 \x -> 2 + x * 9 将被弹出堆栈并应用于 nxt = 3 而无需进一步递归，产生 2 + 3 * 9 = 29 和一个 thunk 3 + nxt * 9 : ys' 由 wgoC 3 0 调用关闭。
可以在不使用网络堆栈的情况下强制每个元素。我们推送一个延续，然后立即将其弹出并将其应用于递归调用中 return 值的一部分 本身 不需要进一步递归。结果是没有净堆栈积累。
现在，考虑 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')
只能通过评估return元组ttl' + 2的第一个组件来为wgoC 1 0调用中的本地绑定ttl'提供所需的值，但这需要通过递归 wgoD 3 0 调用强制 ttl'。因为ttl'受函数applica的约束ion \x -> x + 2 当它 returns 时，我们再推一点堆栈并继续评估：
wgoD 3 0 =
let (ttl', ys') = wgoD 4 0
in (ttl' + 3, 3 + (ttl' + 3) * 9 : ys')
为了在 wgoD 2 0 调用中获得所需的 ttl' 作为本地绑定，我们需要评估 wgoD 3 0 中 return 元组的第一个组件，即 ttl' + 3。这是我们压入堆栈的函数应用程序 \x -> x + 3，应用于 ttl' return 来自递归调用 wgoD 4 0.
因此，Pinned3 将一系列延续 \x -> x + 2、\x -> x + 3、\x -> x + 4' 等推入堆栈，所有这些都是为了评估第一个由 wgoD 2 0 编辑的元组 return 的组成部分，在它到达 wgoD 100000000 0 之前永远没有机会弹出任何东西，然后它最终得到一个数字 finalState = 0 作为第一个元组组件，如果有足够的堆栈可以做到这一点。然后所有的堆栈都将在应用延续时弹出，我们将拥有列表的第一个元素！
一旦它通过了，事情就不会那么糟糕了。此时所有表达式 ttl' + n 都已求值，并且可以在计算表达式 n + (ttl' + n) * 9 时重复使用它们某处 - 您还将以与堆栈使用率大致相同的速度累积堆使用率。
您可以将 100000000 换成 10000000（七个零）之类的东西，然后 运行 在合理的时间内显示金字塔形状的堆栈和堆的累积；它在回落到零之前达到 1.4 演出左右的峰值。
我没有看到任何真正直接的方法来“修复”这个问题，同时仍然保持 Pinned3 的算法结构完好无损。
我正在尝试从 GHC (8.4.3) 中有时发生的优化中获益，其中大量数据的“构建”被放入 PINNED 内存中。 （我这里可能没有正确的所有术语）。这是一个简单的例子：
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 PINNED 并且几乎没有使用 STACK，并且 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 内存，几乎没有堆栈，此配置文件输出：
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 的值完成，我没有看到 PINNED 内存和 STACK 使用（~100M）。 （我认为是 STACK 的使用使它 运行 慢得多，不知何故）。
我看到的Pinned2和Pinned3的主要区别在于Pinned3在返回状态中包含了递归调用的信息（返回对的fst：后续值的累加和），而Pinned2只包含参数到wgoC.
所以我的问题是：
Q1) 使用 PINNED 内存的决定发生在什么地方（在 compiler pipeline 中）？ -ddump-simpl 和 -ddump-cmm 没有明显区别（虽然它有点复杂，所以我可能遗漏了一些东西）。
Q2) PINNED/STACK的决定依据是什么？ （我能找到的关于 PINNED 的唯一参考资料，例如 this，说它对 FFI 调用很有用，但它似乎也被用于此“优化”）。
Q3) 有什么方法可以修改 Pinned3 使其使用 PINNED？
Q4)（作为最后的手段）是否对 Pinned3 进行了一些其他调整，以便有足够的堆栈 space，并在合理的时间内 运行s？ （天真地，我希望性能与 Pinned2 相似）。
[请注意，我只是想了解这里的 PINNED/STACK 机制。我敢肯定还有其他方法可以编写 Pinned3，因此它可以很好地融合并且几乎不需要任何内存，但这个问题与此无关。]
谢谢！
固定内存在这里不起作用。
这个程序：
main = print $ sum $ tail ([1..100000000] :: [Int])
不使用任何固定内存直接。您看到的固定内存来自 运行 时间系统本身的初始化。固定内存由 GHC 的字节数组原语分配；在用户代码中，您最有可能在使用 Data.Text 或 Data.ByteString 时看到固定内存使用情况，它们都使用字节数组进行内部实现。对于这个程序，我猜测 stdin 和 stdout 的 I/O 缓冲区是固定的，但也许是别的原因。无论如何，Int 的列表不会固定任何内容。
像（几乎）所有 Haskell 程序一样，Pinned1.hs 使用大量堆和大量堆栈（每个数以千兆字节计），但至关重要的是，在分配它时尽快释放它（或者如果在谈论堆栈时，您更喜欢“弹出”它就像它“推动”它一样快）。 Pinned2.hs也是如此。这些程序运行正常。
Pinned3.hs 的问题不在于它使用堆栈而不是固定内存，而是它使用比 Pinned1 和 Pinned2 更多的堆栈并且无法将其弹出推动它的速度很快，因此堆栈会累积。
那么，为什么Pinned3会累积堆栈？
一般来说，如果递归调用结果的某些部分是函数应用程序的目标，则堆栈在递归调用中累积 returns AND评估结果本身的那一部分需要另一个递归调用。考虑程序：
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
产生通常的 pyramid-shaped 堆栈累积（峰值为 1.4G 左右）。这里的问题是递归 eatStack (n+1) 调用的 return 值在 return 时受函数应用程序 \x -> 1 + x 的影响，并且计算该结果本身需要进一步递归。也就是说，计算eatStack 0需要在调用eatStack 1之前将\x -> 1 + x压入堆栈，而在调用[=之前将\x -> 1 + x压入堆栈后只能return其结果34=]，等等。结果就是堆栈堆积。
值得注意的是，构造函数应用程序的处理方式不同。以下程序：
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 求值。因为这个return值是受函数应用（即\x -> 1 + x * 9）的影响，所以使用了一点栈，但是递归调用的求值：
wgoC 2 0 =
let (nxt, ys') = wgoC 3 0
in (2, 2 + nxt * 9 : ys')
立即生成 wgoC 1 0 调用中本地绑定 nxt 所需的值，即 returned 元组 fst (wgoC 2 0) = 2 的第一个元素，无需进一步递归。因此，我们取值 2，弹出延续 \x -> 1 + x * 9 并将该值传递给延续以产生 1 + 2 * 9 = 19。这给出了列表的第一个元素，没有使用净堆栈。列表的其余部分，即 wgoC 1 0 调用中的本地绑定 ys'，仍处于由 wgoC 2 0 调用关闭的 thunk 2 + nxt * 9 : ys' 中。
当需要下一个元素时，我们需要一些堆栈来将延续 \x -> 2 + x * 9 应用到递归 (nxt, ys') = wgoC 3 0 中的结果 nxt，但这将被评估同样，立即 returning nxt = 3 和 ys' 的 thunk，因此延续 \x -> 2 + x * 9 将被弹出堆栈并应用于 nxt = 3 而无需进一步递归，产生 2 + 3 * 9 = 29 和一个 thunk 3 + nxt * 9 : ys' 由 wgoC 3 0 调用关闭。
可以在不使用网络堆栈的情况下强制每个元素。我们推送一个延续，然后立即将其弹出并将其应用于递归调用中 return 值的一部分 本身 不需要进一步递归。结果是没有净堆栈积累。
现在，考虑 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')
只能通过评估return元组ttl' + 2的第一个组件来为wgoC 1 0调用中的本地绑定ttl'提供所需的值，但这需要通过递归 wgoD 3 0 调用强制 ttl'。因为ttl'受函数applica的约束ion \x -> x + 2 当它 returns 时，我们再推一点堆栈并继续评估：
wgoD 3 0 =
let (ttl', ys') = wgoD 4 0
in (ttl' + 3, 3 + (ttl' + 3) * 9 : ys')
为了在 wgoD 2 0 调用中获得所需的 ttl' 作为本地绑定，我们需要评估 wgoD 3 0 中 return 元组的第一个组件，即 ttl' + 3。这是我们压入堆栈的函数应用程序 \x -> x + 3，应用于 ttl' return 来自递归调用 wgoD 4 0.
因此，Pinned3 将一系列延续 \x -> x + 2、\x -> x + 3、\x -> x + 4' 等推入堆栈，所有这些都是为了评估第一个由 wgoD 2 0 编辑的元组 return 的组成部分，在它到达 wgoD 100000000 0 之前永远没有机会弹出任何东西，然后它最终得到一个数字 finalState = 0 作为第一个元组组件，如果有足够的堆栈可以做到这一点。然后所有的堆栈都将在应用延续时弹出，我们将拥有列表的第一个元素！
一旦它通过了，事情就不会那么糟糕了。此时所有表达式 ttl' + n 都已求值，并且可以在计算表达式 n + (ttl' + n) * 9 时重复使用它们某处 - 您还将以与堆栈使用率大致相同的速度累积堆使用率。
您可以将 100000000 换成 10000000（七个零）之类的东西，然后 运行 在合理的时间内显示金字塔形状的堆栈和堆的累积；它在回落到零之前达到 1.4 演出左右的峰值。
我没有看到任何真正直接的方法来“修复”这个问题，同时仍然保持 Pinned3 的算法结构完好无损。