Perché una severa funzione di lunghezza ha prestazioni sensibilmente più veloci?

Question

Mi sono divertito con le definizioni per comprendere meglio il modello di valutazione e ne ho scritte due per la lunghezza di un elenco.

La definizione naive:

len :: [a] -> Int 
len [] = 0 
len (_:xs) = 1 + len xs 

La rigida (e coda ricorsiva) definizione:

slen :: [a] -> Int -> Int 
slen [] n = n 
slen (_:xs) !n = slen xs (n+1) 

len [1..10000000] richiede circa 5-6 secondi per eseguire.
slen [1..10000000] 0 richiede circa 3-4 secondi per eseguire.

Sono curioso perché. Prima di controllare le performance, ero certo che avrebbero suonato allo stesso modo perché lo len avrebbe dovuto avere solo un thunk in più per valutare al massimo. A scopo dimostrativo:

len [a,b,c,d] 
= 1 + len [b,c,d] 
= 1 + 1 + len [c,d] 
= 1 + 1 + 1 + len [d] 
= 1 + 1 + 1 + 1 + len [] 
= 1 + 1 + 1 + 1 + 0 
= 4 

E

slen [a,b,c,d] 0 
= slen [b,c,d] 1 
= slen [c,d] 2 
= slen [d]  3 
= slen []  4 
= 4 

Ciò che rende slen notevolmente più veloce?

P.S. Ho anche scritto una funzione lenta ricorsiva in coda (proprio come slen ma pigra) come un tentativo di chiudere la ragione - forse perché era ricorsiva in coda - ma si è comportata all'incirca come nella definizione ingenua.

Answer 1

Il passaggio finale di len non è O (1). È O (n) per sommare n numeri. len utilizza anche la memoria O (n) mentre slen utilizza la memoria O (1).

Il motivo per cui utilizza la memoria O (n) è che ogni thunk consuma un po 'di memoria. Così, quando si ha qualcosa di simile:

1 + 1 + 1 + 1 + len [] 

ci sono cinque thunk non valutate (tra cui len [])

In GHCi, siamo in grado di esaminare questo comportamento thunk un po 'più facile con il comando :sprint. Il comando :sprint stampa il valore dato senza forzare la valutazione di qualsiasi thunk (si può imparare di più da :help). Userò le conse ((:)) dal momento che possiamo valutare più facilmente ogni thunk uno alla volta, ma il principio è lo stesso.

λ> let ys = map id $ 1 : 2 : 3 : [] :: [Int] -- map id prevents GHCi from being too eager here 
λ> :sprint ys 
ys = _ 
λ> take 1 ys 
[1] 
λ> :sprint ys 
ys = 1 : _ 
λ> take 2 ys 
[1,2] 
λ> :sprint ys 
ys = 1 : 2 : _ 
λ> take 3 ys 
[1,2,3] 
λ> :sprint ys 
ys = 1 : 2 : 3 : _ 
λ> take 4 ys 
[1,2,3] 
λ> :sprint ys 
ys = [1,2,3] 

thunk non valutata sono rappresentati da _ e si può vedere che nell'originale ys ci sono 4 thunk annidati uno dentro l'altro, uno per ogni parte della lista (compreso []).

Non c'è un buon modo che io conosca per vedere questo in Int perché la sua valutazione è più o nulla, ma crea ancora un thunk annidato allo stesso modo. Se lo vedessi in questo modo, la sua valutazione sarebbe simile a questa:

len [a,b,c,d] 
= 1 + len [b,c,d] 
= 1 + 1 + len [c,d] 
= 1 + 1 + 1 + len [d] 
= 1 + 1 + 1 + 1 + len [] 
= 1 + 1 + 1 + 1 + 0 
= 1 + 1 + 1 + 1  -- Here it stops building the thunks and starts evaluating them 
= 1 + 1 + 2 
= 1 + 3 
= 4 

Answer 2

La risposta di David Young fornisce la spiegazione corretta della differenza nell'ordine di valutazione. Dovresti pensare alla valutazione di Haskell nel modo in cui lui delinea.

Lascia che ti mostri come puoi vedere la differenza nel Core. Penso che sia effettivamente più visibile con le ottimizzazioni, perché la valutazione finisce come un'esplicita dichiarazione case. Se non hai mai giocato con Core prima, consulta la domanda canonica SO sull'argomento: Reading GHC Core.

Generare l'uscita core con ghc -O2 -ddump-simpl -dsuppress-all -ddump-to-file SO27392665.hs. Vedrai che GHC suddivide sia len che slen in una funzione "worker" ricorsiva, $wlen o $wslen e una funzione "wrapper" non ricorsiva. Perché la stragrande maggioranza del tempo è speso nelle "lavoratori", ricorsive attenzione su di loro:

Rec { 
$wlen 
$wlen = 
    \ @ a_arZ w_sOR -> 
    case w_sOR of _ { 
     [] -> 0; 
     : ds_dNU xs_as0 -> 
     case $wlen xs_as0 of ww_sOU { __DEFAULT -> +# 1 ww_sOU } 
    } 
end Rec } 

len 
len = 
    \ @ a_arZ w_sOR -> 
    case $wlen w_sOR of ww_sOU { __DEFAULT -> I# ww_sOU } 

Rec { 
$wslen 
$wslen = 
    \ @ a_arR w_sOW ww_sP0 -> 
    case w_sOW of _ { 
     [] -> ww_sP0; 
     : ds_dNS xs_asW -> $wslen xs_asW (+# ww_sP0 1) 
    } 
end Rec } 

slen 
slen = 
    \ @ a_arR w_sOW w1_sOX -> 
    case w1_sOX of _ { I# ww1_sP0 -> 
    case $wslen w_sOW ww1_sP0 of ww2_sP4 { __DEFAULT -> I# ww2_sP4 } 
    } 

Si può vedere che $wslen ha una sola case, mentre $wlen ha due. Se andare a vedere la risposta di David, è possibile rintracciare ciò che accade in $wlen: lo fa la sua analisi caso sulla lista del costruttore più esterno ([]/:), poi fa la chiamata ricorsiva a $wlen xs_as0 (cioè len xs), che anche case s, vale a dire costringe il thunk accumulato.

In $wslen, d'altra parte, c'è solo una dichiarazione case. Nel ramo ricorsivo, c'è semplicemente un'aggiunta non registrata, (+# ww_sP0 1), che non crea un thunk.

(Nota: una versione precedente di questa risposta ha dichiarato che con -O GHC potrebbe specializzarsi $wslen ma non $wlen utilizzare disimballati Int# s Non è questo il caso..)