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

目前缺乏lazyness在第一个变体，这不是你的错。一个游程的概要分析输出（+RTS -hd）与参数6比较给人的第一提示：

是第一码的分析输出，而

是的结果第二个代码。阵列本身（ARR_WORDS）在两者中占用相同的空间。您还会看到第一个代码生成了一个大型列表（:构造函数可识别）的Int构造函数（正好名称为Int#）。

现在这不能是最终打印的字符串，因为那将是Char（然后是构造函数C#）。它也可以不是数组中元素的列表，因为数组包含了零，并且垃圾收集器有一个小型的Int s（在范围[-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 ...