9

我正在尝试比较 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))

提前致谢

4

1 回答 1

16

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

分析第一个代码

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

分析第一个代码

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

现在这不能是打印的最终字符串，因为那将是Chars then （使用构造函数C#）。它也不能是数组中的元素列表，因为数组包含零，并且垃圾收集器有一个小Ints 的缓存（在 [-16,16] 范围内），它将使用它来代替分配（或实际上代替复制）一个新的构造函数。

另请注意，构造函数大约需要 24MB，:构造函数大约需要 16MB I#。知道前者需要 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 ...
于 2012-10-08T13:30:03.397 回答