为什么这个Haskell程序在使用优化编译时会泄漏空间？

Question

考虑下面的玩具程序,该程序计算密码中经常使用的单词中字符替换的所有组合.

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"

我在有和没有优化的情况下编译它:

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

现在test0并test1产生相同的输出,而test1使用更多的内存,并花费大量的时间在回收:

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

为什么？

我正在使用GHC 7.4.1; 我应该使用一个更新的编译器,但这是我现在所用的方便,而且错误可能在于我.

Answer 1

你要

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

被编译成外循环和内循环.但GHC认为内循环并不以任何方式依赖外部"循环计数器".因此,完全惰性变换将内环提升出外环.一个相当有效的技巧是隐藏内环是独立的这一事实.这是通过将内部循环拆分为一个单独的函数来获取虚拟参数,并通过将函数标记为隐藏dumminess来完成的NOINLINE.然后你可以使用外循环计数器调用该函数,GHC通常会避免与你搞乱.