Speicherbedarf der Haskell-Datentypen

124

Wie kann ich die tatsächliche Speichermenge ermitteln, die zum Speichern eines Werts eines Datentyps in Haskell erforderlich ist (hauptsächlich mit GHC)? Ist es möglich, es zur Laufzeit auszuwerten (z. B. in GHCi) oder ist es möglich, den Speicherbedarf eines zusammengesetzten Datentyps aus seinen Komponenten abzuschätzen?

Wenn Speicheranforderungen für Typen aund bbekannt sind, wie hoch ist im Allgemeinen der Speicheraufwand für algebraische Datentypen wie:

data Uno = Uno a
data Due = Due a b

Wie viele Bytes im Speicher belegen diese Werte beispielsweise?

1 :: Int8
1 :: Integer
2^100 :: Integer
\x -> x + 1
(1 :: Int8, 2 :: Int8)
[1] :: [Int8]
Just (1 :: Int8)
Nothing

Ich verstehe, dass die tatsächliche Speicherzuordnung aufgrund der verzögerten Speicherbereinigung höher ist. Aufgrund der verzögerten Bewertung kann dies erheblich abweichen (und die Thunk-Größe hängt nicht mit der Größe des Werts zusammen). Die Frage ist, wie viel Speicher bei einem Datentyp bei vollständiger Auswertung benötigt wird.

Ich habe festgestellt, dass es :set +sin GHCi eine Option zum Anzeigen von Speicherstatistiken gibt, aber es ist nicht klar, wie der Speicherbedarf eines einzelnen Werts geschätzt werden soll.

Sastanin
quelle

Antworten:

156

(Das Folgende gilt für GHC. Andere Compiler verwenden möglicherweise andere Speicherkonventionen.)

Faustregel: Ein Konstruktor kostet ein Wort für einen Header und ein Wort für jedes Feld . Ausnahme: Ein Konstruktor ohne Felder (wie Nothingoder True) benötigt keinen Speicherplatz, da GHC eine einzelne Instanz dieser Konstruktoren erstellt und für alle Verwendungszwecke freigibt.

Ein Wort besteht aus 4 Byte auf einem 32-Bit-Computer und 8 Byte auf einem 64-Bit-Computer.

Also zB

data Uno = Uno a
data Due = Due a b

a Unobraucht 2 Wörter und a Duebraucht 3.

Der IntTyp ist definiert als

data Int = I# Int#

Nimmt jetzt Int#ein Wort, also Intinsgesamt 2. Die meisten unboxed Typen nehmen ein Wort, die Ausnahmen sind Int64#, Word64#und Double#(auf einer 32-Bit - Maschine) , die nehmen 2. GHC tatsächlich einen Cache von kleinen Werten des Typs hat Intund Char, so in vielen Fällen diese nehmen keine Heap - Speicher überhaupt. A Stringbenötigt nur Platz für die Listenzellen, es sei denn, Sie verwenden Chars> 255.

An Int8hat die gleiche Darstellung wie Int. Integerist wie folgt definiert:

data Integer
  = S# Int#                            -- small integers
  | J# Int# ByteArray#                 -- large integers

Ein kleines Integer( S#) benötigt also 2 Wörter, aber eine große Ganzzahl benötigt abhängig von ihrem Wert eine variable Menge an Speicherplatz. A ByteArray#benötigt 2 Wörter (Header + Größe) plus Platz für das Array selbst.

Beachten Sie, dass ein mit definierter Konstruktor newtypefrei ist . newtypeist eine reine Idee zur Kompilierungszeit, nimmt keinen Platz ein und kostet zur Laufzeit keine Anweisungen.

Weitere Details finden Sie unter Das Layout von Heap-Objekten im GHC-Kommentar .

Simon Marlow
quelle
1
Danke, Simon. Genau das wollte ich wissen.
Sastanin
2
Ist der Header nicht zwei Wörter? Eine für das Tag und eine für den Weiterleitungszeiger zur Verwendung während der GC oder Auswertung? Würde das nicht ein Wort zu Ihrer Gesamtsumme hinzufügen?
Edward KMETT
5
@Edward: Thunks werden durch Indirektionen überschrieben (die später vom GC entfernt werden), aber das sind nur 2 Wörter, und jedes Heap-Objekt hat garantiert eine Größe von mindestens zwei 2 Wörtern. Ohne aktivierte Profiling- oder Debugging-Funktionen ist der Header wirklich nur ein Wort. In GHC können andere Implementierungen die Dinge anders machen.
Nominolo
3
nominolo: ja, aber von Closure.h: / * Ein Thunk hat ein Füllwort, um den aktualisierten Wert zu übernehmen. Dies ist so, dass das Update die Nutzdaten nicht überschreibt, sodass wir vermeiden müssen, dass der Thunk während der Eingabe und Aktualisierung gesperrt werden muss. Hinweis: Dies gilt nicht für THUNK_STATICs, die keine Nutzlast haben. Hinweis: Wir belassen dieses Füllwort auf alle Arten und nicht nur auf SMP, damit wir nicht alle unsere Bibliotheken für SMP neu kompilieren müssen. * / Die Nutzdaten werden während einer Indirektion nicht überschrieben. Die Indirektion wird an einer separaten Stelle im Header geschrieben.
Edward KMETT
6
Ja, aber beachten Sie, dass dies nur für Thunks gilt . Dies gilt nicht für Konstruktoren. Das Abschätzen der Größe eines Thunks ist ohnehin etwas schwierig - Sie müssen die freien Variablen zählen.
Nominolo
4

Das Paket ghc-datasize bietet die Funktion recursiveSize zum Berechnen der Größe eines GHC-Objekts. Jedoch...

Eine Garbage Collection wird durchgeführt, bevor die Größe berechnet wird, da der Garbage Collector Heap Walks erschweren würde.

... also wäre es nicht praktisch, dies oft anzurufen!

Siehe auch Wie finde ich die Speicherdarstellungen von Datentypen bei GHC heraus? und Wie kann ich die Größe eines Typs in Haskell bestimmen? .

mhwombat
quelle