Słowo foldl „nie jest zoptymalizowana, a także Int foldl”

Question

import Data.List 

test :: Int -> Int 
test n = foldl' (+) 0 [1..n] 

main :: IO() 
main = do 
    print $ test $ 10^8 

GHC optymalizuje powyższy kod do tego stopnia, że ​​garbage collector nawet nie trzeba robić nic:

$ ghc -rtsopts -O2 testInt && ./testInt +RTS -s 
[1 of 1] Compiling Main    (testInt.hs, testInt.o) 
Linking testInt ... 
5000000050000000 
      51,752 bytes allocated in the heap 
      3,480 bytes copied during GC 
      44,384 bytes maximum residency (1 sample(s)) 
      17,056 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0   0 colls,  0 par 0.000s 0.000s  0.0000s 0.0000s 
    Gen 1   1 colls,  0 par 0.000s 0.000s  0.0001s 0.0001s 

    INIT time 0.000s ( 0.000s elapsed) 
    MUT  time 0.101s ( 0.101s elapsed) 
    GC  time 0.000s ( 0.000s elapsed) 
    EXIT time 0.000s ( 0.000s elapsed) 
    Total time 0.103s ( 0.102s elapsed) 

    %GC  time  0.1% (0.1% elapsed) 

    Alloc rate 511,162 bytes per MUT second 

    Productivity 99.8% of total user, 100.9% of total elapsed 

Jednakże, jeśli Zmieniłem typ test na test :: Word -> Word, a następnie produkuje się dużo śmieci, a kod działa 40 razy wolniej.

ghc -rtsopts -O2 testWord && ./testWord +RTS -s 
[1 of 1] Compiling Main    (testWord.hs, testWord.o) 
Linking testWord ... 
5000000050000000 
    11,200,051,784 bytes allocated in the heap 
     1,055,520 bytes copied during GC 
      44,384 bytes maximum residency (2 sample(s)) 
      21,152 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  21700 colls,  0 par 0.077s 0.073s  0.0000s 0.0000s 
    Gen 1   2 colls,  0 par 0.000s 0.000s  0.0001s 0.0001s 

    INIT time 0.000s ( 0.000s elapsed) 
    MUT  time 4.551s ( 4.556s elapsed) 
    GC  time 0.077s ( 0.073s elapsed) 
    EXIT time 0.000s ( 0.000s elapsed) 
    Total time 4.630s ( 4.630s elapsed) 

    %GC  time  1.7% (1.6% elapsed) 

    Alloc rate 2,460,957,186 bytes per MUT second 

    Productivity 98.3% of total user, 98.3% of total elapsed 

Dlaczego tak się dzieje? Spodziewałem się, że wydajność będzie prawie identyczna? (używam wersji 8.0.1 GHC na GNU/Linux x86_64)

EDIT: I złożony bug: https://ghc.haskell.org/trac/ghc/ticket/12354#ticket

Answer 1

Jest to prawdopodobnie głównie, choć nie wyłącznie, ze względu na przepisy, które istnieją przepisać do Int a nie Word. Mówię tak, ponieważ jeśli użyjemy numeru -fno-enable-rewrite-rules na obudowie Int, otrzymamy czas znacznie bliższy, ale nie tak zły jak w przypadku Word.

% ghc -O2 so.hs -fforce-recomp -fno-enable-rewrite-rules && time ./so 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
5000000050000000 
./so 1.45s user 0.03s system 99% cpu 1.489 total 

Jeśli zrzucić reguły przepisywania z -ddump-rule-rewrites i diff tych zasad potem widzimy zasadę, że pożary w przypadku Int a nie przypadek Word:

Rule: fold/build 
Before: GHC.Base.foldr 
... 

Ta szczególna zasada jest w Bazie 4,9 GHC.Base line 823 (NB sam w rzeczywistości korzystam z GHC 7.10) i nie wymieniam wyraźnie nazwy Int. Ciekawi mnie, dlaczego nie strzela do Word, ale nie mam teraz czasu na dalsze badania.

Answer 2

Jak podkreślił dfeuer w komentarzu tutaj, instancja Enum dla Int jest lepsza niż dla Word:

Int:

instance Enum Int where 
    {-# INLINE enumFromTo #-} 
    enumFromTo (I# x) (I# y) = eftInt x y 

{-# RULES 
"eftInt"  [~1] forall x y. eftInt x y = build (\ c n -> eftIntFB c n x y) 
"eftIntList" [1] eftIntFB (:) [] = eftInt 
#-} 
{- Note [How the Enum rules work] 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
* Phase 2: eftInt ---> build . eftIntFB 
* Phase 1: inline build; eftIntFB (:) --> eftInt 
* Phase 0: optionally inline eftInt 
-} 

{-# NOINLINE [1] eftInt #-} 
eftInt :: Int# -> Int# -> [Int] 
-- [x1..x2] 
eftInt x0 y | isTrue# (x0 ># y) = [] 
      | otherwise   = go x0 
       where 
       go x = I# x : if isTrue# (x ==# y) 
           then [] 
           else go (x +# 1#) 

{-# INLINE [0] eftIntFB #-} 
eftIntFB :: (Int -> r -> r) -> r -> Int# -> Int# -> r 
eftIntFB c n x0 y | isTrue# (x0 ># y) = n 
        | otherwise   = go x0 
       where 
        go x = I# x `c` if isTrue# (x ==# y) 
            then n 
            else go (x +# 1#) 
         -- Watch out for y=maxBound; hence ==, not > 
     -- Be very careful not to have more than one "c" 
     -- so that when eftInfFB is inlined we can inline 
     -- whatever is bound to "c" 

Teraz Word rzeczywiście wykorzystuje implementację Integer

enumFromTo n1 n2  = map integerToWordX [wordToIntegerX n1 .. wordToIntegerX n2] 

która używa

instance Enum Integer where 
    enumFromTo x lim  = enumDeltaToInteger x 1  lim 

Teraz enumDeltaToInteger ma przepisać zasady ustanowione, ale okazuje się, że Word „s enumFromTo nigdy nie jest wstawiane, więc ta konfiguracja nie ma szans na fuzję tutaj.

Kopiowanie tej funkcji do mojego kodu testu powoduje, że GHC wprowadza ją, reguła fold/build do strzelania, i surowo zmniejsza alokację, ale konwersja zi do Integer (która przydziela) pozostaje.