Haskell中令人费解的内存行为

Question

我试图比较Haskell列表和数组的性能，但遇到了一个奇怪的行为。我观察到，如果我创建一个数组，然后打印它，它需要'x‘MB的内存，但是如果我使用'elems’函数将数组转换为一个列表，然后打印它，它占用的内存少于'x‘。'elems‘函数不是应该从数组中创建一个新的列表吗？它不应该比不创建列表的函数占用更多的空间吗？我使用了-O2和-fspec-constr优化标志。我还使用了-p标志来分析函数。

这是没有中间列表的代码，

fun  n = runST $  do
      final_soln <- newArray_ ((1,1), (n, (10 ^ n))) :: ST s ((STUArray s)  (Int,Int) Int)
      U.unsafeFreeze final_soln

main = do 
    [n] <- getArgs
    {-#  SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt"  $ show $ fun (read n))

这是带有中间列表的代码，

fun :: Int -> UArray (Int,Int) Int
fun  n = runST $  do
      final_soln <- newArray_ ((1,1), (n, (10 ^ n))) :: ST s ((STUArray s)  (Int,Int) Int)
      U.unsafeFreeze final_soln

main = do 
    [n] <- getArgs
    {-#  SCC "file-writing" #-} (writeFile "cprod-starray-creation.txt"  $ show $ elems $ fun (read n))

提前感谢

Answer 1

第一个变种缺乏惰性，这不是你的错。将运行的性能分析输出(+RTS -hd)与参数6进行比较会给出第一个提示：

​

​

是第一个代码的性能分析输出，而

​

​

是第二个代码的结果。数组本身(ARR_WORDS)在两者中占用相同的空间。您还可以看到，第一段代码生成了一个很大的Int构造函数列表(可由:构造函数识别)(这些构造函数的名称恰好是Int#)。

现在，这不可能是打印出来的最后一个字符串，因为这将是Chars (使用构造函数C#)。它也不能是数组中的元素列表，因为数组包含零，并且垃圾收集器有一个小Int的缓存(在-16，16范围内)，它将使用它而不是分配(或实际不是复制)一个新的构造函数。

还要注意，:构造函数大约需要24MB，I#构造函数大约需要16MB。知道前者需要3个单词，后2个单词，并且在我的机器上有一个单词是8字节长，我们发现这个列表是100000=10^6元素长度。所以一个非常好的候选者是第二个索引参数的范围。

那么这个数组在哪里呢？让我们追踪您对show的呼叫

showsIArray :: (IArray a e, Ix i, Show i, Show e) => Int -> a i e -> ShowS
showsIArray p a =
    showParen (p > 9) $
    showString "array " .
    shows (bounds a) .
    showChar ' ' .
    shows (assocs a)

(代码来自Data.Array.Base)。显然，罪魁祸首一定是在assocs调用中，所以下面是它的源代码：

assocs :: (IArray a e, Ix i) => a i e -> [(i, e)]
assocs arr = case bounds arr of
    (l,u) -> [(i, arr ! i) | i <- range (l,u)]

由于我们正在查找索引列表，因此range调用看起来足够可疑。为此，我们必须研究GHC.Arr的来源(不幸的是，它搞砸了)：

instance (Ix a, Ix b) => Ix (a, b) where
    range ((l1,l2),(u1,u2)) = [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]

现在我们已经找到了罪魁祸首:在这里，range (l2,u2)将计算结果为列表[1..1000000]，并为索引的第一个组件中的每一步进行共享。

现在，我猜您会好奇地尝试在第二个代码中使用assocs而不是elems，并预料到那里会有空间泄漏。但你看不到它。原因是show不是内联的，但assocs本身是内联的，然后还有一大堆其他函数，包括range有效地避免了共享。您可以通过将-ddump-rule-firings传递给GHC(在某种程度上)看到这一点：

$ ghc --make -O2 -fspec-constr -ddump-rule-firings -fforce-recomp code2.hs -prof -fprof-auto
[1 of 1] Compiling Main             ( code2.hs, code2.o )
Rule fired: SPEC GHC.Arr.$fIx(,)
Rule fired: unpack
Rule fired: Class op fail
Rule fired: unpack
Rule fired: Class op show
Rule fired: Class op newArray_
Rule fired: unsafeFreeze/STUArray
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op showList
Rule fired: Class op rangeSize
Rule fired: Class op rangeSize
Rule fired: Class op bounds
Rule fired: Class op bounds
Rule fired: Class op numElements
Rule fired: Class op index
Rule fired: Class op unsafeAt
Rule fired: Class op range
Rule fired: fold/build
Rule fired: SPEC GHC.Real.^
Rule fired: unpack-list
Rule fired: foldr/app
Rule fired: unpack-append
Rule fired: foldr/app
Rule fired: unpack-append
Rule fired: >#
Rule fired: >#
Rule fired: x# <=# x#
Rule fired: x# -# x#
Rule fired: 0# *# x#
Rule fired: 0# +# x#
Linking code2 ...