performance - 长度与折叠与显式递归的性能特征
问题描述
我已经编写了该length
函数的六个版本。一些性能差异是有道理的,但其中一些似乎与我读过的文章完全不同(例如this和this)。
-- 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
每个函数的版本始终优于使用显式递归的版本? - 尽管有这篇文章的警告,但这些实现都没有在我的机器上达到堆栈溢出。为什么不?
- 为什么不
len3
表现得比len1
or好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
仍然优于所有这些实现?
解决方案
我认为无论您尝试使用什么标志,您都无法正确测试 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
具有几乎相同的性能。实际上,生成的CorelenFold1
是:
lenFold1 = len1
所以它们是相同的功能。不过,我的基准测试中的明显差异是真实的,并且似乎是某些缓存/对齐问题的结果。如果我重新排序len1
和lenFold1
in main
,性能差异会翻转(这len1
就是“慢速”)。
len2
并且len3
具有相同的性能,因为它们是相同的功能。(实际上,为len3
is生成的代码len3 = len2
。) GHC 的严格分析器确定表达式1 + acc
可以严格计算,即使没有显式$!
运算符。
lenFold3
由于没有内联,所以速度稍慢foldl'
,因此组合函数每次都需要显式调用。这可以说是这里报告的错误。我们可以通过更改 的定义lenFold3
来明确提供三个参数来解决它foldl'
:
lenFold3 xs = foldl' (\a _ -> a + 1) 0 xs
len2
然后它的表现和 and一样好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
需要明确的是,在对and进行这两次更改之后lenFold3
,函数len2
、len3
、lenFold2
和lenFold3
都是相同的,除了lenFold2
and以不同的顺序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%,因此您可以使用千兆字节的堆栈而不会真正注意到。在这种情况下,一些快速分析+RTS -hT
显示堆栈增长到大约 60-70 兆字节的单个len1 [1..10000000]
,几乎不足以溢出任何东西。相比之下,len2
家庭没有积累任何可观的堆栈。
最后,让length
他们大吃一惊的原因是它使用 anInt
而不是an 来计算长度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
。
推荐阅读
- c++ - 错误条件后的标准输入状态
- python - 将字符串中的字母临时索引到不同的二进制文件
- android - 发送通知前检查当前接收者状态
- javascript - 使用 AJAX 调用表
- javascript - 如何在rest api中传递查询参数?
- firebase-realtime-database - 是否可以让 Firebase 实时数据库节点仅可供 2 个特定用户访问?
- mongodb - 减少数组元素 (MongoDB)
- javascript - 如何使用带有加密进度/状态指示器的 AES-CBC 算法加密和解密大文件?
- c++ - 'for' 之前的预期不合格 -id
- git - 合并后将gitlab-ci.yml中的include-ref更改为master?