为什么对本机列表进行求和比将教会编码列表与"GHC -O2"相加更慢？

Question

为了测试教会编码列表如何针对用户定义列表和本机列表执行,我准备了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.我试着更换sum的foldl',相同的结果.我尝试添加用户输入以确保教堂列表版本未针对常量进行优化.arkeet在#haskell上指出,通过检查Core,本机版本有一个中间列表,但为什么呢？强制分配额外的reverse,所有3执行大致相同.

Answer 1

GHC 7.10具有通话元数分析,这可以让我们定义foldl来讲foldr,从而让左边的褶皱,其中包括sum,参与融合.GHC 7.8也定义sum了foldl但不能将列表融合在一起.因此,GHC 7.10与教会版本的表现最佳且相同.

教会版本是儿童游戏,可以在GHC版本中进行优化.我们只需内联(+)和0进入fenumTil,然后我们有一个明显的尾递归go,可以很容易地取消装箱,然后由代码生成器转换成循环.

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