performance - Haskell 的严格折叠真的使用线性空间吗？

Question

我以为我了解了 Haskell 中折叠性能的基础知识，如 foldr, foldl, foldl' on the Haskell Wiki 中所述和许多其他地方。特别是，我了解到对于累积函数，应该使用 foldl'，以避免空间泄漏，并且编写标准库函数就是为了尊重这一点。所以我假设像 length 这样的简单累加器，应用于像 replicate n 1 这样的简单列表，应该在列表的长度中需要恒定的空间(或至少是次线性的) .我的直觉是，在足够简单的列表上，它们的行为大致类似于命令式语言中的 for 循环。

但今天我发现这在实践中似乎并不成立。例如，length $ replicate n 1 似乎在 n 中使用空间线性。 在 ghci 中:

ghci> :set +s
ghci> length $ replicate (10^6) 1
1000000
(0.02 secs, 56,077,464 bytes)
ghci> length $ replicate (10^7) 1
10000000
(0.08 secs, 560,078,360 bytes)
ghci> length $ replicate (10^8) 1
100000000
(0.61 secs, 5,600,079,312 bytes)
ghci> length $ replicate (10^9) 1
1000000000
(5.88 secs, 56,000,080,192 bytes)

简而言之，我的问题是:length 和其他严格折叠真的使用线性空间吗？如果是这样，为什么？这是不可避免的吗？下面是我如何尝试理解这一点的更多细节，但它们可能不值得一读 - tl;dr 是线性空间的使用似乎会持续任何变化我试试。

(我最初使用 sum 作为示例函数。正如 Willem Van Onsem 指出的那样，这是一个选择不当的示例，因为默认实例实际上并不严格。但是，主要问题仍然存在，因为如下所述，这种情况发生在许多其他真正基于严格折叠的函数中。)

• 将 length 替换为 foldl' (\n _ -> n+1) 0 似乎会使性能下降一个常数因子；空间使用似乎仍然是线性的。
• 用 foldl 和 foldr 定义的版本的内存使用率更差(正如预期的那样)，但只是一个小的常数因素，而不是渐近更差的(正如大多数讨论所暗示的那样)。
• 将 length 替换为 sum、last 或其他简单的累加器，或者使用 foldl'，似乎也没有改变线性空间使用情况。
• 使用 [1..n] 作为测试列表，以及其他类似的变体，似乎也没有显着差异。
• 在Data.Foldable中的sum、foldl'等通用版本之间切换，Data.列表，以及直接通过模式匹配定义的本地版本，似乎也没有什么区别。
• 编译而不是在 ghci 中工作似乎也只能通过一个常数因子来提高空间使用率。
• 在 GHC 的几个最新版本(8.8.4、8.10.5 和 9.0.1)之间切换似乎也没有显着差异。

Answer 1

“他们是否使用线性空间”是一个有点不清楚的问题。通常当我们谈论算法使用的空间时，我们谈论的是它的工作集:它一次需要的最大内存量。 “如果我的电脑只有 X 字节的内存，我可以运行这个程序吗？”但这不是 GHCI 的 :set +s 措施。它测量所有内存分配的总和，包括中途清理的内存分配。在你的实验中，内存的最大用途是什么？当然是列表本身。

所以您实际上只是测量了大小为 N 的列表占用的字节数。您可以通过使用 last 而不是 length 来确认这一点，我希望您同意不分配中间结果，并且是严格的。使用度量标准时，它占用与 length 相同的内存量 - length 不会为总和分配额外的内存。

但更大的问题是 GHCI 不是优化编译器。如果您完全关心性能特征，那么 GHCI 是错误的工具。相反，使用带有 -O2 的 GHC，并打开 GHC 的分析器。

import System.Environment (getArgs)

main = do
  n <- read . head <$> getArgs
  print $ length (replicate (10^n) 1)

并运行它:

$ ghc -O2 -prof -fprof-auto stackoverflow.hs
$ ./stackoverflow 6 +RTS -p
1000000
$ grep "total alloc" stackoverflow.prof
    total alloc =      54,856 bytes  (excludes profiling overheads)
$ ./stackoverflow 9 +RTS -p
1000000000
$ grep "total alloc" stackoverflow.prof
    total alloc =      55,008 bytes  (excludes profiling overheads)

我们可以看到，尽管输入大小增加了一千倍，但空间使用量大致保持不变。

Will Ness 是否正确指出 in a comment -s 将是比 -p 更好的测量工具。