Perché questo programma Haskell perde spazio quando compilato con ottimizzazioni?

Question

Si consideri il seguente programma giocattolo che calcola tutte le combinazioni di sostituzioni di caratteri in una parola, del tipo spesso utilizzato nelle password.

import Data.Char (isLower, toUpper) 

variants :: String -> [String] 
variants "" = [""] 
variants (c:s) = [c':s' | c' <- subst c, s' <- variants s] 
    where subst 'a' = "aA@" 
     subst 'e' = "eE3" 
     subst 'i' = "iI1" 
     subst 'l' = "lL1" 
     subst 'o' = "oO0" 
     subst 's' = "sS$5" 
     subst 'z' = "zZ2" 
     subst x | isLower x = [x, toUpper x] 
     subst x = [x] 

main :: IO() 
main = putStrLn $ show $ length $ variants "redistributables" 

posso compilare con e senza ottimizzazioni:

$ ghc -fforce-recomp -Wall Test.hs -o test0 
[1 of 1] Compiling Main    (Test.hs, Test.o) 
Linking test0 ... 

$ ghc -fforce-recomp -O -Wall Test.hs -o test1 
[1 of 1] Compiling Main    (Test.hs, Test.o) 
Linking test1 ... 

Ora test0 e test1 produrre la stessa uscita, ma test1 utilizza molta più memoria e trascorre la maggior parte del suo tempo in garbage collection:

$ ./test0 +RTS -s 2>&1 | grep total 
       2 MB total memory in use (0 MB lost due to fragmentation) 
    Productivity 93.2% of total user, 93.3% of total elapsed 

$ ./test1 +RTS -s 2>&1 | grep total 
      188 MB total memory in use (0 MB lost due to fragmentation) 
    Productivity 15.0% of total user, 15.0% of total elapsed 

Perché?

Sto utilizzando GHC 7.4.1; Probabilmente dovrei usare un compilatore più recente, ma questo è quello che ho a portata di mano in questo momento, e l'errore probabilmente ricade comunque su di me.

Answer 1

Volete

variants (c:s) = [c':s' | c' <- subst c, s' <- variants s] 

da compilare in un loop esterno e un ciclo interno. Ma GHC vede che il ciclo interno non dipende in alcun modo dal "contatore di loop" esterno. Pertanto, la completa trasformazione della pigrizia solleva il ciclo interno dal ciclo esterno. Un trucco abbastanza efficace è quello di nascondere il fatto che il ciclo interno è indipendente. Questo viene fatto dividendo il loop interno in una funzione separata prendendo un argomento fittizio, e nascondendo il dumminess contrassegnando la funzione come NOINLINE. Quindi puoi chiamare la funzione con il contatore del ciclo esterno, e GHC generalmente ti mancherà di fare scherzi con te.

Answer 2

Il trucco è di causare il ricalcolo dei suffissi, invece della loro conservazione in memoria. E 'come con la definizione

powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs 

, dove l'aggiunta della clausola where è dannoso (o è powerset (x:xs) = powerset xs ++ map (x:) (powerset xs) ...?).

Nel tuo caso, il codice per provare è mapM subst, o

variants (c:cs) = variants cs >>= \s-> map (:s) (subst c) 

Si può vedere che queste ultime opere in "direzione opposta" dal codice di lista, in modo forse solo

variants (c:s) = [c':s' | s' <- variants s, c' <- subst c] 

funzionerà anche.

Tutti questi sono equivalenti, quindi è una cosa del compilatore. Spero che qualcuno possa fornire ulteriori dettagli su questo.