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