Haskell'de akıcı hafıza davranışı

Question

Haskell listelerinin ve dizilerinin performansını karşılaştırmaya çalışıyorum ve garip bir davranışla karşılaşıyorum. Bir dizi oluşturup yazdırırsam onu ​​'x' MB bellek alır, ancak diziyi 'elems' işlevini kullanarak bir listeye dönüştürür ve sonra yazdırırsa, 'x' değerinden daha az bellek alır. 'elems' işlevinin diziden yeni bir liste oluşturması gerekmiyor mu? Listeyi oluşturmayan işlevden daha fazla yer almamalı mı? -O2 ve -fspec-constr optimizasyon bayraklarını kullanıyorum. Fonksiyonları izlemek için -p bayrağını da kullanıyorum. peşin

Bu orta liste ile kodudur

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

Bu ara listesi olmadan kodudur

,

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

sayesinde lazyness eksikliği içinde olduğunu

Answer 1

İlk varyant, ve senin hatan değil.

sonucu ise,

birinci kod profil çıkışı: parametresi 6 olan bir seferin profil çıkışı (+RTS -hd) karşılaştırılması birinci ipucu verir ikinci kod. Dizinin kendisi (ARR_WORDS) her ikisinde de aynı alanı alır. Ayrıca, ilk kodun Int yapıcılarının (Int# ismine sahip olduğu) büyük bir liste (: yapıcı tarafından tanınabilir) oluşturduğunu da görebilirsiniz.

Artık bu, yazdırıldığı gibi son dize olamaz, bu Char s olacaktır (kurucu C# ile birlikte). Dizi sıfırlar içerdiğinden ve çöp toplayıcının, (yerine [-16,16] aralıkta) Int s'lik bir önbelleğe sahip olduğu için dizideki öğelerin listesi de olamaz. kopyalama yerine) yeni bir kurucu.

Ayrıca, : yapıcıları için 24MB ve I# yapıcıları için 16 MB aldığını unutmayın. Birincinin 3 kelimeyi ve ikinci 2 kelimeyi gerektirdiğini ve makinemdeki bir kelimenin 8 bayt uzunluğunu bildiğini biliyoruz, listenin 100000 = 10^6 element uzunluğunda olduğunu görüyoruz. Yani çok iyi bir aday, ikinci indeks parametresinin aralığıdır.

Peki bu dizi nerede? Bize show için çağrı iz edelim:

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 Kod). Biz endeksleri listesi için aradığınız beri

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 çağrı yeterince şüpheli görünüyor: Açıkçası, suçlu işte bunun için kaynağıdır, assocs çağrısında olmalıdır.

instance (Ix a, Ix b) => Ix (a, b) where 
    range ((l1,l2),(u1,u2)) = [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ] 

Ve şimdi zanlı bulmuş: Bunun için (maalesef berbat Haddock) GHC.Arr kaynağına içine bakmak zorunda Burada range (l2,u2) listeye [1..1000000] ve değerlendirecek her adım için paylaştı endeksin ilk bileşeninde.

Şimdi ikinci kodda elems yerine assocs kodunu koymaya ve oradaki boşluk sızıntısını beklemeye çalıştığınızı tahmin edersiniz. Ama sen görmeyeceksin. Bunun nedeni, show'un satır içi olmaması, ancak assocs'un kendisinin satır içi olarak alınıp, daha sonra, paylaşımın önlenmesi açısından range da dahil olmak üzere, bir sürü başka işlev de vardır. Sen ghc -ddump-rule-firings geçirerek o (biraz) görebilirsiniz:

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