algorithm - ¿Por qué sumar listas nativas es más lento que sumar listas codificadas por la iglesia con `GHC-O2`?

performance haskell

Question

Para probar cómo se comportan las listas codificadas por la iglesia en comparación con las listas de usuarios y listas nativas, he preparado 3 puntos de referencia:

Listas definidas por el usuario

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)))

Listas nativas

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

Listas de la iglesia

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)

Los resultados de referencia son inesperados:

Listas definidas por el usuario

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

Listas nativas

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

Listas de la Iglesia

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

Uno esperaría que, con la enorme cantidad de optimizaciones específicas dirigidas a listas nativas, obtendrían el mejor rendimiento. Sin embargo, las listas de iglesias superan a las de ellos por un factor de 100x, y superan a las ADT definidas por el usuario por un factor de 2250x. He compilado todos los programas con GHC -O2 . He intentado reemplazar la sum por foldl'' , mismo resultado. He intentado agregar entradas de usuario para asegurarme de que la versión de la lista de la iglesia no estuviera optimizada a una constante. arkeet señaló en # haskell que, al inspeccionar Core, la versión nativa tiene una lista intermedia, pero ¿por qué? Forzando la asignación con un reverse adicional, los 3 realizan aproximadamente lo mismo.

Answer 1

GHC 7.10 tiene un análisis de aridad de llamada , que nos permite definir foldl en términos de foldr y así permitir que los pliegues a la izquierda, incluida la sum , participen en la fusión. GHC 7.8 también define la sum con foldl pero no puede fusionar las listas. Así, GHC 7.10 se desempeña de manera óptima e idéntica a la versión de la Iglesia.

La versión de la Iglesia es un juego de niños para optimizar en cualquiera de las versiones de GHC. Solo tenemos que fenumTil en línea (+) y 0 en fenumTil , y luego tenemos una fenumTil -recursiva que puede ser fácilmente desempacada y luego convertida en un bucle por el generador de código.

La versión definida por el usuario no es recursiva y funciona en un espacio lineal, lo que destruye el rendimiento, por supuesto.