Haskellで困惑しているメモリの動作

Question

私はHaskellのリストと配列の性能を比較しようとしており、奇妙な動作に陥っています。 配列を作成して印刷すると 'x' MBのメモリが必要になりますが、 'elems'関数を使って配列をリストに変換して印刷すると、 'x'よりもメモリが少なくなります。 'elems'関数は配列から新しいリストを作成するはずですか？リストを作成しない関数よりも多くのスペースを取るべきではありませんか？ -O2と-fspec-constrの最適化フラグを使用しています。また、関数のプロファイルに-pフラグを使用しています。

これは中lazynessの欠如があり、これは中間リストとコードで、事前に

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

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

中間リストのないコードであります最初の変種であり、それはあなたのせいではありません。

での結果であるが、

は、最初のコードのプロファイリング出力される：パラメーター6とランのプロファイリング出力（+RTS -hd）を比較すると、最初のヒントを与えます2番目のコード配列自体（ARR_WORDS）は、両方で同じスペースをとります。また、最初のコードはIntコンストラクタ（Int#の名前を持つ）の大きなリスト（:コンストラクタで認識可能）を生成することがわかります。

これは、Char（コンストラクタC#）のように、最終的な文字列を印刷することはできません。配列にはゼロが含まれており、ガーベッジコレクタには割り当ての代わりに使用する小数のInt（範囲[-16,16]）のキャッシュがあるため、配列内の要素のリストにすることもできません新しいコンストラクタをコピーするのではなく）。

:コンストラクタの場合は約24MB、コンストラクタI#の場合は16MBが必要です。前者が3ワードと後ろ2ワードを必要とし、マシン上の1ワードが8バイトであることを知ると、リストは100000 = 10^6エレメント長であることがわかります。したがって、非常に良い候補は、2番目のインデックスパラメータの範囲です。

この配列はどこですか？私たちは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]に評価され、は、すべてのステップのためのを共有しましたインデックスの最初の要素に

elemsの代わりにassocsを2番目のコードに入れて、スペースリークが予想されることに興味があると思います。しかし、あなたはそれを見ません。その理由は、showがインライン化されておらず、assocs自体がインライン化され、rangeなどの他の関数も効果的に共有されないためです。あなたはGHCに-ddump-rule-firingsを渡すことで（やや）それを見ることができます。

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