Dlaczego ten program Haskell traci przestrzeń po kompilacji z optymalizacją?

Question

Rozważmy następujący program zabawkowy, który wylicza wszystkie kombinacje zastąpień znaków w słowie, rodzaju często używanego w hasłach.

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" 

skompilować go i bez optymalizacji:

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

Teraz test0 i test1 wytwarzają taką samą moc, ale test1 korzysta znacznie więcej pamięci i spędza większość czasu w zbieranie śmieci:

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

Dlaczego?

Używam GHC 7.4.1; Prawdopodobnie powinienem użyć nowszego kompilatora, ale to jest właśnie to, co mam w tej chwili pod ręką, a wina prawdopodobnie i tak leży u mnie.

Answer 1

Chcesz

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

być kompilowane do pętli zewnętrznej i wewnętrznej pętli. Ale GHC widzi, że wewnętrzna pętla nie zależy w żaden sposób od zewnętrznego "licznika pętli". Dlatego pełna transformacja lenistwo podnosi wewnętrzną pętlę z zewnętrznej pętli. Jedną z dość skutecznych sztuczek jest ukrywanie faktu, że wewnętrzna pętla jest niezależna. Odbywa się to poprzez podzielenie wewnętrznej pętli na oddzielną funkcję, która pobiera fałszywy argument i ukrywa dumminess przez oznaczenie funkcji jako NOINLINE. Następnie możesz wywołać funkcję z zewnętrznym licznikiem pętli, a GHC na ogół nie będzie się z tobą bawić.

Answer 2

Sztuką jest spowodowanie przeliczenia przyrostków, zamiast ich przechowywania w pamięci. To tak jak z definicją

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

, gdzie dodanie klauzuli where jest szkodliwe (czy jest to powerset (x:xs) = powerset xs ++ map (x:) (powerset xs) ...?).

W twoim przypadku, kod, aby spróbować to mapM subst lub

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

Widać, że te ostatnie prace w „przeciwnym kierunku” z kodem lista ze zrozumieniem, więc może po prostu

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

będzie działać również.

Wszystkie te są równoważne, więc jest to kompilator. Mam nadzieję, że ktoś może podać więcej szczegółów na ten temat.