Warum verliert dieses Haskell-Programm Speicherplatz, wenn es mit Optimierungen kompiliert wird?

Question

Betrachten Sie das folgende Spielzeugprogramm, das alle Kombinationen von Zeichensubstitutionen in einem Wort berechnet, wie es oft in Passwörtern verwendet wird.

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" 

ich kompilieren Sie es mit und ohne Optimierungen:

$ 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 ... 

Jetzt test0 und test1 die gleiche Leistung erzeugen, aber test1 verwendet viel mehr Speicher und verbringt die meiste Zeit in der 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 

Warum?

Ich benutze GHC 7.4.1; Ich sollte wahrscheinlich einen neueren Compiler verwenden, aber das ist es, was ich im Moment praktisch habe, und der Fehler liegt wahrscheinlich bei mir.

Answer 1

Sie wollen

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

in eine äußere Schleife und eine innere Schleife erstellt werden. GHC sieht jedoch, dass die innere Schleife in keiner Weise vom äußeren "Schleifenzähler" abhängt. Daher hebt die vollständige Faulheitsumwandlung die innere Schleife aus der äußeren Schleife heraus. Ein ziemlich effektiver Trick ist es, die Tatsache zu verbergen, dass die innere Schleife unabhängig ist. Dies geschieht durch Aufteilen der inneren Schleife in eine separate Funktion unter Verwendung eines Dummy-Arguments und Verbergen der Dummheit durch Markieren der Funktion als NOINLINE. Dann können Sie die Funktion mit dem äußeren Schleifenzähler aufrufen, und GHC wird im Allgemeinen davon absehen, mit Ihnen zu spielen.

Answer 2

Der Trick besteht darin, die Neuberechnung von Suffixen zu veranlassen, anstatt sie im Speicher zu behalten. Es ist wie mit der

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

Definition, wo Hinzufügen der where Klausel schädlich ist (oder ist es powerset (x:xs) = powerset xs ++ map (x:) (powerset xs) ...?).

In Ihrem Fall der Code ist zu versuchen, mapM subst oder

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

Sie können sehen, daß diese Arbeiten in der „entgegengesetzten Richtung“ aus der Liste Verständnis Code, also vielleicht nur

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

wird auch funktionieren.

Alle diese sind gleichwertig, also ist es eine Compiler-Sache. Hoffentlich kann jemand genauere Angaben dazu machen.