Rätselhaftes Speicherverhalten in Haskell

Question

Ich versuche, die Leistung von Haskell Listen und Arrays zu vergleichen und in einem seltsamen Verhalten zu laufen. Ich habe beobachtet, dass, wenn ich ein Array erstellen und es dann drucken es 'x' MB Speicher, aber wenn ich das Array in eine Liste mit der 'Elems' -Funktion konvertieren und dann drucken nimmt es Speicher weniger als 'x'. Soll die Funktion 'elems' nicht eine neue Liste aus dem Array erstellen? Sollte es nicht mehr Platz beanspruchen als die Funktion, die die Liste nicht erstellt? Ich verwende die -O2- und -fspec-constr-Optimierungsflags. Ich verwende auch das Flag -p, um die Funktionen zu profilieren.

Dies ist der Code ohne Zwischen Liste,

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

Dies ist der Code mit der Zwischen Liste,

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

Vielen Dank im Voraus

Answer 1

Es gibt einen Mangel an lazyness in der erste Variante, und es ist nicht deine Schuld. Vergleichen der Profilierungs Ausgang (+RTS -hd) eines Laufes mit dem Parameter 6 gibt den ersten Hinweis:

ist die Profilierung Ausgang des ersten Codes, während

ist das Ergebnis der zweite Code. Das Array selbst (ARR_WORDS) nimmt in beiden den gleichen Platz ein. Sie sehen auch, dass der erste Code eine große Liste (erkennbar an dem :-Konstruktor) von Int Konstruktoren (die zufällig den Namen Int# haben) erzeugt.

Jetzt kann dies nicht der letzte String sein, wie gedruckt, wie das wäre dann Char s (mit Konstruktor C#). Es kann auch nicht die Liste der Elemente im Array sein, da das Array Nullen enthält und der Garbage Collector einen Cache von Int s (im Bereich [-16,16]) hat, den er anstelle der Zuweisung verwenden würde (oder tatsächlich anstatt zu kopieren) einen neuen Konstruktor.

Beachten Sie auch, dass es etwa 24 MB für die : Konstruktoren und 16 MB für die Konstruktoren benötigt. Wissend, dass erstere 3 Wörter und die letzten 2 Wörter benötigt und dass ein Wort auf meiner Maschine 8 Bytes lang ist, finden wir, dass die Liste 100000 = 10^6 Elemente lang ist. Ein sehr guter Kandidat ist also der Bereich des zweiten Indexparameters.

Also, wo ist das Array? Lassen Sie uns verfolgen Ihren Anruf 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) 

(-Code von Data.Array.Base). Natürlich muss der Täter in dem assocs Anruf sein, so ist hier die Quelle dafür:

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

Da wir für die eine Liste von Indizes suchen, der range Aufruf sieht verdächtig genug.Dafür müssen wir in die Quelle der GHC.Arr aussehen (die leider Haddock verkorkste):

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

Und jetzt haben wir den Schuldigen gefunden: Hier range (l2,u2) zur Liste auswertet [1..1000000] und geteilt für jeden Schritt in der ersten Komponente des Indexes.

Jetzt werden Sie neugierig sein zu versuchen, assocs anstelle von elems in den zweiten Code zu setzen, und erwarten, dass das Raumleck dort. Aber du wirst es nicht sehen. Der Grund ist, dass show ist nicht inline, aber assocs selbst wird inline, und dann auch eine ganze Reihe von anderen Funktionen, einschließlich range effektiv die gemeinsame Nutzung zu vermeiden. Sie können, indem -ddump-rule-firings zu GHC dass (etwas) sehen:

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