2016-06-30 31 views
14
import Data.List 

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

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

GHC ottimizza il codice di cui sopra, al punto che il garbage collector non ha nemmeno bisogno di fare qualsiasi cosa:Word foldl 'non è ottimizzato così come Int foldl'

$ 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 

Tuttavia, se Cambio il tipo di test in test :: Word -> Word, quindi viene prodotta molta spazzatura e il codice viene eseguito 40 volte più lentamente.

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 

Perché succede? Mi aspettavo che la performance fosse quasi identica? (sto usando GHC versione 8.0.1 su x86_64 GNU/Linux)

edit: ho presentato un bug: https://ghc.haskell.org/trac/ghc/ticket/12354#ticket

+1

Qual è il core generato in entrambi i casi? – Cactus

+2

È necessario inviare un bug al programma di rilevamento dei problemi di GHC (https://ghc.haskell.org/trac/ghc/newticket). –

+0

Ho inviato un bug: https://ghc.haskell.org/trac/ghc/ticket/12354#ticket – Kevin

risposta

10

Questo è probabilmente in gran parte, anche se non esclusivamente, a causa di riscrivere le regole che esistono per Int e non Word. Dico questo perché se usiamo -fno-enable-rewrite-rules nel caso Int otteniamo un tempo molto più vicino, ma non del tutto negativo, al caso 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 

Se noi scarichiamo le regole di riscrittura con -ddump-rule-rewrites e diff queste regole poi vediamo una regola che spara nel caso Int e non il caso Word:

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

Quel particolare regola è in Base 4.9 GHC.Base line 823 (NB, in realtà sto usando GHC 7.10 da solo) e non menziona Int esplicitamente. Sono curioso del motivo per cui non sta sparando per Word, ma non ho il tempo ora per indagare ulteriormente.

+4

Non l'ho esaminato, ma sto mettendo la mia scommessa sull'istanza 'Enum Word' che è diversa da quella di' Enum Int', impedendo alla enumerazione di essere in grado di fondersi con 'foldr'. – dfeuer

+0

Per iniziare, l'istanza per 'Word' di solito converte il valore in un' Integer', quindi converte il risultato in 'Word'. – chepner

+0

Sì, 'fold/build' è estremamente importante. È l'ottimizzazione che elimina la creazione dell'elenco in memoria. È abbastanza probabile che l'implementazione di 'Enum' di' '' 'non usi' build'. – Carl

2

Come sottolineato da dfeuer in un commento qui, l'istanza Enum per Int è migliore di quella per 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" 

Ora Word utilizza in realtà l'implementazione per Integer

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

che utilizza

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

Ora enumDeltaToInteger ha riscrivere le regole stabilite, ma si scopre che Word s’enumFromTo non è mai inline, quindi questa impostazione non ha alcuna possibilità di fusione qui.

La copia di questa funzione nel mio codice di prova fa in modo che GHC lo incorpori, la regola fold/build attiva e riduce gravemente l'allocazione, ma la conversione da e verso Integer (che viene allocata) rimane.

+0

Quanto sopra è con 7.10. Dovrebbe essere leggermente migliore con 8.0, dove 'remInteger' è diventato severo (vedi [# 10691] (http://hackage.haskell.org/trac/ghc/ticket/10691)). –

+0

Hai o hai inviato una segnalazione di bug per aggiungere un'istanza più efficiente per Word? –

+0

È già stato eseguito: [# 12354] (https://ghc.haskell.org/trac/ghc/ticket/12354#ticket) –