Haskell/GHC中`any`/`all`函数的性能表现

Question

我为Haskell的内置列表数据类型“[]”编写了量化函数“exists”，“forall”和“none”。在多个场合中，它们似乎比“Prelude / Data.List”的“any”和“all”更有效。我天真地认为，这种性能是因为使用Θ（n）折叠实现了“any”和“all”。由于我对Haskell相对较新，我认为我一定是错的，或者存在一个好的原因解释这种现象。

来自“Data.Foldable”：

-- | Determines whether any element of the structure satisfies the predicate.
any :: Foldable t => (a -> Bool) -> t a -> Bool
any p = getAny #. foldMap (Any #. p)

-- | Determines whether all elements of the structure satisfy the predicate.
all :: Foldable t => (a -> Bool) -> t a -> Bool
all p = getAll #. foldMap (All #. p)

我的实现：

exists :: (a -> Bool) -> [a] -> Bool
exists _    []                   = False
exists pred (x : xs) | pred x    = True
                     | otherwise = exists pred xs

并且

forall pred  =  not . exists (not . pred)
none pred  =  not . exists pred  =  forall (not . pred)

消除布尔反转：

forall, none :: (a -> Bool) -> [a] -> Bool

forall _    []                   = True
forall pred (x : xs) | pred x    = forall pred xs
                     | otherwise = False

none _    []                   = True
none pred (x : xs) | pred x    = False
                   | otherwise = none pred xs

all:

time                 327.8 μs   (322.4 μs .. 333.0 μs)
                     0.997 R²   (0.996 R² .. 0.998 R²)
mean                 328.7 μs   (324.1 μs .. 334.2 μs)
std dev              16.95 μs   (14.63 μs .. 22.02 μs)

以及 对于所有:

time                 113.2 μs   (111.2 μs .. 115.0 μs)
                     0.997 R²   (0.996 R² .. 0.998 R²)
mean                 112.0 μs   (110.0 μs .. 113.9 μs)
std dev              6.333 μs   (5.127 μs .. 7.896 μs)

使用准则nf来衡量性能。

---

正如预期的那样，我没有重新发明折叠方法，但是低估了编译器标志，并且天真地认为与默认优化级别性能相比，-O2不会产生如此激烈的整体差异，也没有预料到单独定制和库式表述之间的优化效果差异。许多高度有效的专业标准函数优化显然只有在明确启用时才会启动。

Haskell标签信息中的“性能”部分强调了测试代码效率时优化级别编译器标志的重要性。通常建议信任库函数实现的复杂性，而不是重新编写RULES规范或重新构思基本形式，而是尝试利用已经培养的优化潜力。

- user6428287

---

如果你想推理代码在这个层面上的性能，你可能应该看看核心。性能差距与渐近性无关（它怎么可能有关呢？你的函数显然也是O(n)）——我猜测这可能是由于Foldable函数中缺乏内联所致。所有你的函数都等价于某个f、z的foldr f z，而List.foldr即使在Foldable.foldr不行时也可能进行内联。 - user2407038

我无法通过简单的“all”/“forall”来复现这个问题。毫不奇怪，当涉及可熔合操作时，这是毫无竞争力的：http://sprunge.us/RQdO 当然，你可以为“forall”和其他函数编写融合规则。 - Michael

请阅读Haskell标签信息部分，了解有关性能问题的内容。 - jberryman

你也应该尝试使用-O。它的编译速度比-O2快得多，而且它生成的代码通常已经足够好了。 - dfeuer

此外，请注意，基本上所有的“可折叠”函数在与“错误”的容器一起使用时都可能存在严重的性能问题。 “可折叠”是一个“泄漏”的抽象概念：您确实必须考虑您正在使用它的内容。有些人正在努力改善这种情况，但似乎本质上很困难。 - dfeuer

Answer 1

我觉得重新实现any方法很有启发意义，可以采用多种方式：

import Prelude hiding (any)
import Criterion.Main
import Data.Foldable (foldMap)
import Data.Monoid

您的 exists:

exists :: (a -> Bool) -> [a] -> Bool
exists _ [] = False
exists pred (x : xs)
    = if pred x
      then True
      else exists pred xs

使用(||)的版本：

existsOr :: (a -> Bool) -> [a] -> Bool
existsOr _ [] = False
existsOr pred (x : xs) = pred x || existsOr pred xs

使用 foldr 函数：

any :: (a -> Bool) -> [a] -> Bool
any pred = foldr ((||) . pred) False

使用 foldr 和 Any:

anyF :: (a -> Bool) -> [a] -> Bool
anyF pred = getAny . foldr (mappend . (Any . pred)) mempty

使用foldMap和Any：

anyFM :: (a -> Bool) -> [a] -> Bool
anyFM pred = getAny . foldMap (Any . pred)

使用ghc -O0进行基准测试：

benchmarking exists
time                 1.552 μs   (1.504 μs .. 1.593 μs)
                     0.989 R²   (0.983 R² .. 0.993 R²)
mean                 1.482 μs   (1.427 μs .. 1.545 μs)
std dev              196.1 ns   (168.8 ns .. 229.2 ns)
variance introduced by outliers: 93% (severely inflated)

benchmarking existsOr
time                 2.699 μs   (2.616 μs .. 2.768 μs)
                     0.992 R²   (0.988 R² .. 0.995 R²)
mean                 2.629 μs   (2.554 μs .. 2.704 μs)
std dev              277.8 ns   (235.8 ns .. 351.1 ns)
variance introduced by outliers: 89% (severely inflated)

benchmarking any
time                 5.551 μs   (5.354 μs .. 5.777 μs)
                     0.990 R²   (0.986 R² .. 0.995 R²)
mean                 5.553 μs   (5.395 μs .. 5.750 μs)
std dev              584.2 ns   (447.5 ns .. 835.5 ns)
variance introduced by outliers: 88% (severely inflated)

benchmarking anyF
time                 7.330 μs   (7.081 μs .. 7.612 μs)
                     0.988 R²   (0.982 R² .. 0.994 R²)
mean                 7.502 μs   (7.272 μs .. 7.762 μs)
std dev              848.2 ns   (712.6 ns .. 1.022 μs)
variance introduced by outliers: 89% (severely inflated)

benchmarking anyFM
time                 5.668 μs   (5.451 μs .. 6.008 μs)
                     0.987 R²   (0.975 R² .. 0.996 R²)
mean                 5.807 μs   (5.659 μs .. 5.975 μs)
std dev              542.5 ns   (446.4 ns .. 721.8 ns)
variance introduced by outliers: 86% (severely inflated)

你的版本 (exists) 确实是最快的，而 foldr 版本则相当慢。

使用 ghc -O2，你的版本 (exists) 是最慢的，而所有其他函数的速度几乎都相同。

benchmarking exists
time                 753.5 ns   (725.4 ns .. 779.9 ns)
                     0.990 R²   (0.986 R² .. 0.995 R²)
mean                 762.4 ns   (737.0 ns .. 787.0 ns)
std dev              82.47 ns   (66.79 ns .. 105.1 ns)
variance introduced by outliers: 91% (severely inflated)

benchmarking existsOr
time                 491.5 ns   (478.2 ns .. 503.2 ns)
                     0.994 R²   (0.992 R² .. 0.996 R²)
mean                 494.5 ns   (481.1 ns .. 512.9 ns)
std dev              54.97 ns   (42.54 ns .. 80.34 ns)
variance introduced by outliers: 92% (severely inflated)

benchmarking any
time                 461.2 ns   (442.0 ns .. 479.7 ns)
                     0.989 R²   (0.985 R² .. 0.993 R²)
mean                 456.0 ns   (439.3 ns .. 476.3 ns)
std dev              60.04 ns   (47.27 ns .. 89.47 ns)
variance introduced by outliers: 94% (severely inflated)

benchmarking anyF
time                 436.9 ns   (415.8 ns .. 461.0 ns)
                     0.978 R²   (0.967 R² .. 0.988 R²)
mean                 450.8 ns   (430.1 ns .. 472.6 ns)
std dev              70.64 ns   (57.04 ns .. 85.92 ns)
variance introduced by outliers: 96% (severely inflated)

benchmarking anyFM
time                 438.9 ns   (426.9 ns .. 449.5 ns)
                     0.993 R²   (0.989 R² .. 0.996 R²)
mean                 435.8 ns   (421.4 ns .. 447.6 ns)
std dev              45.32 ns   (36.73 ns .. 58.74 ns)
variance introduced by outliers: 90% (severely inflated)

如果你查看简化的Core代码（ghc -O2 -ddump-simpl），会发现没有foldr了（在-O0中，所有内容仍然存在，包括fold）。

因此，我敢说在未优化版本（-O0）中，你的代码比库中的代码更快，因为它更简单（可能以失去一些通用性为代价）。优化后的库代码比你的版本更快，因为它是以一种被编译器认可的方式编写的。（诚然，这是有些猜测的）

- marc_r