Haskell/GHC性能的`任何'/`所有`

Question

我寫了通用量化函數exists,forall和none爲Haskell的內置[]列表數據類型。在多次情況下，這些證明比Prelude/Data.List的any和all更有效。我天真地懷疑這個表現是由於any和all使用Θ（n）摺疊實現的。由於我對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 

resultive

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) 

和forall：使用標準的nf測量

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) 

性能。

---

正如預期的那樣，我沒有重新推翻摺疊，但低估了編譯器標誌。

我天真地沒有想到-O2與默認的優化級別性能相比產生如此巨大的整體差異，也沒有在個人自定義編寫和庫文件制定之間的優化效果不一致。許多高效的專業標準功能優化顯然只有在明確啓用時纔會啓動。

Haskell標記信息的「性能」部分強調測試代碼效率時優化級別編譯器標誌的重要性。一般建議相信庫函數實現的複雜性，而不是重新編譯或重新編寫基本表單，以嘗試利用已經培育出來的優化潛力。

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) 

如果觀察到簡易核心代碼（ghc -O2 -ddump-simpl），人們看到沒有foldr了（與-O0，一切仍然在那裏，包括fold s）。因此，我會冒昧地說你的代碼比庫代碼更快（在未優化的版本中，-O0），因爲它更簡單（對於潛在的不太普遍的代價）。優化後的庫代碼比你的版本更快，因爲它的編寫方式是它的優化潛力被編譯器識別。 （無可否認，這是一個猜測工作）