algorithm - 为什么对本地列表求和比用 `GHC -O2` 对教堂编码列表求和慢？

Question

为了测试 church-encoded lists 对 user-defiend lists 和 native lists 的表现如何，我准备了 3 个基准:

用户定义的列表

data List a = Cons a (List a) | Nil deriving Show
lenumTil n        = go n Nil where
    go 0 result   = result
    go n result   = go (n-1) (Cons (n-1) result)
lsum Nil          = 0
lsum (Cons h t)   = h + (lsum t)

main = print (lsum (lenumTil (100000000 :: Int)))

原生列表

main = print $ sum ([0..100000000-1] :: [Int])

教会名单

fsum   = (\ a -> (a (+) 0))
fenumTil n cons nil = go n nil where
    go 0 result    = result
    go n result    = go (n-1) (cons (n-1) result)
main = print $ (fsum (fenumTil (100000000 :: Int)) :: Int)

基准测试结果出乎意料:

用户定义的列表

-- 4999999950000000
-- real 0m22.520s
-- user 0m59.815s
-- sys  0m20.327s

原生列表

-- 4999999950000000
-- real 0m0.999s
-- user 0m1.357s
-- sys  0m0.252s

教会名单

-- 4999999950000000
-- real 0m0.010s
-- user 0m0.002s
-- sys  0m0.003s

人们会期望，随着针对原生列表的大量特定优化，它们会表现最好。然而，教会名单的表现优于它们 100 倍，并且优于用户定义的 ADT 2250 倍。我用 GHC -O2 编译了所有程序。我尝试用 foldl' 替换 sum，结果相同。我尝试添加用户输入以确保教堂列表版本未优化为常量。 arkeet 在#haskell 上指出，通过检查 Core， native 版本有一个中间列表，但为什么呢？使用额外的 reverse 强制分配，所有 3 个执行大致相同。

Answer 1

GHC 7.10 有 call arity分析，它让我们根据 foldr 定义 foldl，从而让左折叠(包括 sum)参与融合。 GHC 7.8 还用 foldl 定义了 sum 但它不能将列表融合在一起。因此 GHC 7.10 的性能最佳且与 Church 版本相同。

Church 版本在任一 GHC 版本中进行优化都是小菜一碟。我们只需要将 (+) 和 0 内联到 fenumTil 中，然后我们就有了一个明显的尾递归 go 它可以很容易地拆箱，然后由代码生成器变成一个循环。

用户定义的版本不是尾递归的，它在线性空间中工作，这当然会破坏性能。