length vs fold vs 显式递归的性能特征

Question

我已经编写了 length 函数的六个版本。一些性能差异是有道理的，但其中一些似乎与我读过的文章完全不一致（例如 this one and this one）。

-- len1 and lenFold1 should have equivalent performance, right?

len1 :: [a] -> Integer
len1 [] = 0
len1 (x:xs) = len1 xs + 1

lenFold1 :: [a] -> Integer
lenFold1 = foldr (\_ a -> a + 1) 0


-- len2 and lenFold2 should have equivalent performance, right?

len2 :: [a] -> Integer
len2 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs (1 + acc)

lenFold2 :: [a] -> Integer
lenFold2 = foldl (\a _ -> a + 1) 0


-- len3 and lenFold3 should have equivalent performance, right?
-- And len3 should outperform len1 and len2, right?

len3 :: [a] -> Integer
len3 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs $! (1 + acc)

lenFold3 :: [a] -> Integer
lenFold3 = foldl' (\a _ -> a + 1) 0

我机器上的实际性能令人费解。

*Main Lib> :set +m +s
*Main Lib> xs = [1..10000000]
(0.01 secs, 351,256 bytes)
*Main Lib> len1 xs
10000000
(5.47 secs, 2,345,244,016 bytes)
*Main Lib> lenFold1 xs
10000000
(2.74 secs, 1,696,750,840 bytes)
*Main Lib> len2 xs
10000000
(6.02 secs, 2,980,997,432 bytes)
*Main Lib> lenFold2 xs
10000000
(3.97 secs, 1,776,750,816 bytes)
*Main Lib> len3 xs
10000000
(5.24 secs, 3,520,354,616 bytes)
*Main Lib> lenFold3 xs
10000000
(1.24 secs, 1,040,354,528 bytes)
*Main Lib> length xs
10000000
(0.21 secs, 720,354,480 bytes)

我的问题：

为什么每个函数的 fold 版本始终优于使用显式递归的版本？

this article

None 这些实现在我的机器上曾经达到堆栈溢出。为什么不呢？
为什么 len3 的表现不如 len1 或 len2？
为什么 Prelude 的 length 比这些实现中的任何一个都要好得多？

编辑：

感谢 Carl 的建议，我的第一个和第二个问题得到了解决，因为 GHCI 默认解释代码。运行它再次与 -fobject-code 解释了显式递归和折叠之间的不同性能。新三围：

Prelude Lib Main> xs = [1..10000000]
(0.00 secs, 354,136 bytes)
Prelude Lib Main> len1 xs
10000000
(1.62 secs, 1,612,661,544 bytes)
Prelude Lib Main> lenFold1 xs
10000000
(1.62 secs, 1,692,661,552 bytes)
Prelude Lib Main> len2 xs
10000000
(2.46 secs, 1,855,662,888 bytes)
Prelude Lib Main> lenFold2 xs
10000000
(2.53 secs, 1,772,661,528 bytes)
Prelude Lib Main> len3 xs
10000000
(0.48 secs, 1,680,361,272 bytes)
Prelude Lib Main> lenFold3 xs
10000000
(0.31 secs, 1,040,361,240 bytes)
Prelude Lib Main> length xs
10000000
(0.18 secs, 720,361,272 bytes)

我对此还有一些疑问。

为什么 lenFold3 优于 len3？我运行这几次
length 如何仍然优于所有这些实施？

Answer 1

我认为无论您尝试使用什么标志，您都无法正确测试 GHCi 的性能。

一般来说，对 Haskell 代码进行性能测试的最佳方法是使用 Criterion 基准测试库并使用 ghc -O2 进行编译。转换为标准基准，您的程序如下所示：

import Criterion.Main
import GHC.List
import Prelude hiding (foldr, foldl, foldl', length)

len1 :: [a] -> Integer
len1 [] = 0
len1 (x:xs) = len1 xs + 1

lenFold1 :: [a] -> Integer
lenFold1 = foldr (\_ a -> a + 1) 0

len2 :: [a] -> Integer
len2 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs (1 + acc)

lenFold2 :: [a] -> Integer
lenFold2 = foldl (\a _ -> a + 1) 0

len3 :: [a] -> Integer
len3 xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs $! (1 + acc)

lenFold3 :: [a] -> Integer
lenFold3 = foldl' (\a _ -> a + 1) 0

testLength :: ([Int] -> Integer) -> Integer
testLength f = f [1..10000000]

main = defaultMain
  [ bench "lenFold1" $ whnf testLength lenFold1
  , bench "len1" $ whnf testLength len1
  , bench "len2" $ whnf testLength len2
  , bench "lenFold2" $ whnf testLength lenFold2
  , bench "len3" $ whnf testLength len3
  , bench "lenFold3" $ whnf testLength lenFold3
  , bench "length" $ whnf testLength (fromIntegral . length)
  ]

我机器上的缩写结果是：

len1                 190.9 ms   (136.8 ms .. 238.6 ms)
lenFold1             207.8 ms   (151.6 ms .. 248.6 ms)
len2                 69.96 ms   (69.09 ms .. 71.63 ms)
lenFold2             1.191 s    (917.1 ms .. 1.454 s)
len3                 69.26 ms   (69.20 ms .. 69.35 ms)
lenFold3             87.14 ms   (86.95 ms .. 87.35 ms)
length               26.78 ms   (26.50 ms .. 27.08 ms)

请注意，这些结果与您从 GHCi 观察到的运行这些测试的性能有很大不同，无论是绝对值还是相对值，有或没有 -fobject-code。为什么？打败我了。

无论如何，基于这个正确的基准，len1 和 lenFold1 具有几乎相同的性能。实际上，为lenFold1生成的Core是：

lenFold1 = len1

所以它们是相同的函数。不过，我的基准测试中的明显差异是真实存在的，而且它似乎是某些 cache/alignment 问题的结果。如果我在 main 中重新排序 len1 和 lenFold1，性能差异就会翻转（因此 len1 是“慢的”）。

len2 和 len3 也具有相同的性能，因为它们是相同的函数。（实际上，len3 的生成代码是 len3 = len2。）GHC 的严格性分析器确定表达式 1 + acc 可以严格求值，即使没有显式的 $! 运算符。

lenFold3 稍微慢一些，因为 foldl' 不是内联的，所以组合函数每次都需要显式调用。这可以说是一个已报告的错误 here。我们可以通过更改 lenFold3 的定义来明确地为 foldl':

提供三个参数来解决这个问题

lenFold3 xs = foldl' (\a _ -> a + 1) 0 xs

然后它的性能与 len2 和 len3 一样好：

lenFold3             66.99 ms   (66.76 ms .. 67.30 ms)

lenFold2 的糟糕表现是同一问题的体现。如果没有内联，GHC 将无法执行适当的优化。如果我们将定义更改为：

lenFold2 xs = foldl (\a _ -> a + 1) 0 xs

它的表现和其他的一样好：

lenFold2             66.64 ms   (66.58 ms .. 66.68 ms)

明确地说，在对 lenFold2 和 lenFold3 进行这两个更改后，函数 len2、len3、lenFold2 和 lenFold3 完全相同，只是 lenFold2 和 lenFold3 以不同的顺序应用 + 运算符。如果我们使用定义：

lenFold2 xs = foldl (\a _ -> 1 + a) 0 xs
lenFold3 xs = foldl' (\a _ -> 1 + a) 0 xs

那么生成的Core（可以用ghc -O2 -ddump-simpl -dsuppress-all -dsuppress-uniques -fforce-recomp查看）实际是：

len2 = ...actual definition...
lenFold2 = len2
len3 = len2
lenFold3 = len2

所以它们完全相同。

它们与 len1（或等同于 lenFold1）真正不同，因为 len1 构建了大量堆栈帧，然后在到达末尾时需要处理这些堆栈帧列表并“发现”空列表的长度为零。没有堆栈溢出的原因是很多关于 Haskell 堆栈溢出的博客文章似乎已经过时或基于 GHCi 测试。在使用现代 GHC 版本编译的代码中，maximum stack size 默认为物理内存的 80%，因此您可以在不知不觉中使用千兆字节的堆栈。在这种情况下，使用 +RTS -hT 进行的一些快速分析表明，对于单个 len1 [1..10000000]，堆栈增长到大约 60-70 兆字节，几乎不足以溢出任何东西。相比之下，len2 家族没有积累任何可观的堆栈。

最后，length 让他们大吃一惊的原因是它使用 Int 而不是 Integer 来计算长度。如果我将类型签名更改为：

len1 :: [a] -> Int
len2 :: [a] -> Int

然后我得到：

len1                 144.7 ms   (121.8 ms .. 157.9 ms)
len2                 27.38 ms   (27.31 ms .. 27.44 ms)
length               27.50 ms   (27.45 ms .. 27.54 ms)

和len2（因此lenFold2、len3和lenFold3）都和length一样快。

length vs fold vs 显式递归的性能特征

Performance characteristics of length vs fold vs explicit recursion

performance

haskell

recursion

performance-testing

fold