为什么这个 Haskell 程序在优化编译时会泄漏 space？

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"
        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

诀窍是重新计算后缀，而不是将它们保留在内存中。就像

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

定义，其中添加 where 子句是有害的（或者是 powerset (x:xs) = powerset xs ++ map (x:) (powerset xs) ...？）。

对于您的情况，要尝试的代码是 mapM subst 或

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

您可以从您的列表理解代码中看到后者在 "opposite direction" 中起作用，所以也许只是

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

也可以。

所有这些都是等价的，所以这是编译器的事情。希望有人能提供更多细节。

Answer 2

你想要

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

编译成外循环和内循环。但是 GHC 发现内部循环不以任何方式依赖于外部 "loop counter"。因此，完全惰性变换将内循环提升到外循环之外。一个相当有效的技巧是隐藏内循环是独立的这一事实。这是通过将内部循环拆分成一个单独的函数来完成的，该函数接受一个伪参数，并通过将函数标记为 NOINLINE 来隐藏伪参数。然后你就可以用外层循环计数器来调用函数了，GHC一般不会乱来的。

为什么这个 Haskell 程序在优化编译时会泄漏 space？

Why does this Haskell program leak space when compiled with optimizations?

optimization

haskell

memory-leaks

ghc