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

最初のバリアントには怠惰さが欠けていますが、それはあなたのせいではありません。パラメータ 6 を使用した実行のプロファイリング出力 ( +RTS -hd) を比較すると、最初のヒントが得られます。

最初のコードのプロファイリング

は最初のコードのプロファイリング出力ですが、

最初のコードのプロファイリング

2 番目のコードの結果です。配列自体 ( ARR_WORDS) は両方で同じスペースを取ります。:また、最初のコードが (コンストラクターによって認識可能な)Intコンストラクター (たまたま という名前)の大きなリストを生成することもわかりますInt#。

Charこれは、（コンストラクターを使用して） s になるため、印刷された最終的な文字列にすることはできませんC#。また、配列にはゼロが含まれており、ガベージ コレクターIntには割り当ての代わりに (または実際にはコピーの）新しいコンストラクター。

:また、コンストラクターに約 24MB、コンストラクターに約 16MBかかることにも注意してくださいI#。前者には 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のソースを調べる必要があります(残念ながら haddock が台無しになっています)。

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ここで、2 番目のコードの代わりに入れようとしてelems、そこにスペース リークがあることを期待することに興味があると思います。しかし、あなたはそれを見ません。その理由は、インライン化されshowていないためですが、assocsそれ自体がインライン化され、range共有を効果的に回避するなど、他の多くの関数もインライン化されます。-ddump-rule-firingsGHCに渡すことで (ある程度) 確認できます。

$ 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 に答える