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

Question

我以为我了解 Haskell 中折叠性能的基础知识，如Haskell Wiki和许多其他地方的foldr、foldl、foldl'中所述。特别是，我了解到对于累积函数，应该使用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 指出的那样，这是一个错误选择的示例，因为默认实例实际上并不严格。但是，主要问题仍然存在，因为如下所述，这发生在许多其他真正基于严格折叠的功能。）

• 替换lengthwithfoldl' (\n _ -> n+1) 0似乎会使性能恶化一个常数因子；空间使用似乎仍然是线性的。
• 用foldl和定义的版本foldr具有更差的内存使用（正如预期的那样），但只是一个小的常数因子，而不是渐近地更糟（正如大多数讨论似乎表明的那样）。
• 替换length为sum、last或其他简单的累加器，或者使用这些的明显定义，foldl'似乎也不会改变线性空间的使用。
• 使用[1..n]作为测试列表，以及其它类似的变化，也似乎毫无显著差异。
• 一般版本之间切换sum，foldl'等从Data.Foldable，在专业的人Data.List，并通过模式匹配直接定义本地版本，似乎也没有什么区别。
• 编译而不是工作ghci似乎也只能通过一个常数因子来提高空间使用率。
• 在几个最近的 GHC 版本（8.8.4、8.10.5 和 9.0.1）之间切换似乎也没有显着差异。

Answer 1

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

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

但更大的问题是 GHCI 不是优化编译器。如果您完全关心性能特征，那么 GHCI 是错误的工具。相反，将 GHC 与 -O2 一起使用，并打开 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在评论中正确指出，这-s将是比-p.