长度、折叠和显式递归的性能特征

Question

我已经编写了六个版本的length函数。其中一些性能差异是有道理的，但有些似乎完全不符合我阅读过的文章（例如这篇和这篇）。

-- 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)

我的问题：

1. 为什么每个函数的fold版本始终比使用显式递归的版本表现更出色？
2. 尽管这篇文章发出警告，但在我的计算机上，这些实现从未导致堆栈溢出。为什么？
3. 为什么len3的性能不如len1或len2好？
4. 为什么Prelude中的length执行效果比这些实现都要好得多？

编辑：

感谢Carl的建议，我的第一个和第二个问题得到了解答，原因是GHCI默认解释代码。使用-fobject-code再次运行程序可解释显式递归和fold之间的不同性能。新的测量结果如下：

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)

我还有几个关于这个问题的疑问。

1. 为什么 lenFold3 的性能优于 len3？我已经运行了几次。
2. length 如何仍然优于所有这些实现？

- dan p

---

你正在比较解释型代码和编译型代码，并且想知道为什么编译型代码更快？ - Carl

@Carl，你提出了有用的观点，但是无论你是否有意，你的措辞显得有些傲慢，我认为这并不是很有帮助。 - amalloy

@Carl，这是一种有趣的说法，“GHCI默认通过解释器解释代码。尝试使用-fobject-code再次运行它。”但还是感谢您的建议！更新测量数据。 - dan p

不要在 GHCi 中进行基准测试。使用 -O2 进行编译，并使用类似 criterion 的工具进行测试。 - Thomas M. DuBuisson

Answer 1

我认为无论你尝试使用什么标志，都不能在GHCi中正确地测试性能。

一般来说，测试Haskell代码性能最好的方法是使用Criterion基准测试库并通过ghc -O2进行编译。将您的程序转换为Criterion基准测试的样式如下：

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

因此它们是相同的功能。尽管在我的基准测试中表现出明显的差异，但这似乎是某些缓存/对准问题的结果。如果我在main中重新排序len1和lenFold1，性能差异就会反转（使len1成为“慢的”）。

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

lenFold3稍微慢一些，因为foldl'没有内联，所以每次都需要显式调用组合函数。这可能是已报告的错误（在此处）。我们可以通过更改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版本编译的代码中，最大堆栈大小默认为物理内存的80％，因此您可以使用几个GB的堆栈而不会真正注意到。 在这种情况下，使用+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一样快。

- K. A. Buhr