令人费解的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#).它也可以不是数组中的元素列表,因为数组包含零,垃圾收集器有一个小Ints 的缓存(在[-16,16]范围内),它将使用而不是分配(或实际上是复制)一个新的构造函数.

另请注意,:构造函数大约需要24MB,构造函数大约需要16MB I#.知道前者需要3个单词而后两个单词,并且我机器上的一个单词长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 ...