Ślad pamięciowy typów danych Haskell

124

Jak mogę znaleźć rzeczywistą ilość pamięci wymaganej do przechowywania wartości pewnego typu danych w Haskell (głównie z GHC)? Czy można to ocenić w czasie wykonywania (np. W GHCi), czy też można oszacować zapotrzebowanie na pamięć złożonego typu danych na podstawie jego komponentów?

Ogólnie rzecz biorąc, jeśli znane są wymagania dotyczące pamięci typów ai b, jaki jest narzut pamięci algebraicznych typów danych, takich jak:

data Uno = Uno a
data Due = Due a b

Na przykład, ile bajtów pamięci zajmują te wartości?

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

Rozumiem, że faktyczna alokacja pamięci jest wyższa z powodu opóźnionego czyszczenia pamięci. Może się znacznie różnić ze względu na leniwą ocenę (a wielkość pozycji nie jest związana z wielkością wartości). Pytanie brzmi, biorąc pod uwagę typ danych, ile pamięci zajmuje jego wartość po pełnej ocenie?

Znalazłem :set +sopcję w GHCi, aby zobaczyć statystyki pamięci, ale nie jest jasne, jak oszacować ślad pamięci pojedynczej wartości.

śastanin
źródło

Odpowiedzi:

156

(Poniższe dotyczy GHC, inne kompilatory mogą używać różnych konwencji przechowywania)

Ogólna zasada: konstruktor kosztuje jedno słowo na nagłówek i jedno słowo na każde pole . Wyjątek: konstruktor bez pól (takich jak Nothinglub True) nie zajmuje miejsca, ponieważ GHC tworzy pojedyncze wystąpienie tych konstruktorów i udostępnia je we wszystkich zastosowaniach.

Słowo ma 4 bajty na komputerze 32-bitowym i 8 bajtów na komputerze 64-bitowym.

Więc np

data Uno = Uno a
data Due = Due a b

an Unozajmuje 2 słowa, a a Duebierze 3.

IntTypu określa się jako

data Int = I# Int#

teraz Int#zajmuje jedno słowo, więc Intw sumie bierze 2. Większość Rozpakowanych rodzaje wziąć jedno słowo, wyjątki są Int64#, Word64#i Double#(na komputerze 32-bitowym), które podejmują 2. GHC faktycznie ma cache małych wartościach typu Inti Chartak w wielu przypadkach te nie biorą przestrzeń sterty w ogóle. A Stringwymaga tylko miejsca na komórki listy, chyba że używasz Chars> 255.

An Int8ma identyczną reprezentację jak Int. Integerjest zdefiniowany w następujący sposób:

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

więc small Integer( S#) zajmuje 2 słowa, ale duża liczba całkowita zajmuje zmienną ilość miejsca w zależności od jej wartości. A ByteArray#zajmuje 2 słowa (nagłówek + rozmiar) plus miejsce na samą tablicę.

Zauważ, że konstruktor zdefiniowany za pomocą newtypejest bezpłatny . newtypejest pomysłem wyłącznie w czasie kompilacji i nie zajmuje miejsca i nie kosztuje instrukcji w czasie wykonywania.

Więcej szczegółów w The Layout of Heap Objects w komentarzu GHC .

Simon Marlow
źródło
1
Dziękuję, Simon. To jest dokładnie to, co chciałem wiedzieć.
sastanin
2
Czy nagłówek nie jest dwoma słowami? Jeden dla tagu, a drugi dla wskaźnika przekierowania do użycia podczas GC lub oceny? Więc czy to nie dodałoby jednego słowa do twojej sumy?
Edward KMETT
5
@Edward: Thunks są nadpisywane przez pośrednie (które są później usuwane przez GC), ale są to tylko 2 słowa, a każdy obiekt sterty ma gwarantowany rozmiar co najmniej dwóch 2 słów. Bez włączonych funkcji profilowania lub debugowania nagłówek to tak naprawdę tylko jedno słowo. Oznacza to, że w GHC inne implementacje mogą działać inaczej.
nominolo
3
nominolo: tak, ale z Closure.h: / * Thunk ma słowo wypełniające, które przyjmuje zaktualizowaną wartość. Dzieje się tak, aby aktualizacja nie nadpisywała ładunku, dzięki czemu możemy uniknąć konieczności blokowania funkcji podczas wprowadzania i aktualizacji. Uwaga: nie dotyczy to THUNK_STATICs, które nie mają ładunku. Uwaga: zostawiamy to słowo wypełniające na wszystkie sposoby, a nie tylko SMP, aby nie musieli ponownie kompilować wszystkich naszych bibliotek dla SMP. * / Ładunek nie jest nadpisywany podczas pośrednictwa. Wskazanie pośrednie jest zapisywane w osobnym miejscu w nagłówku.
Edward KMETT
6
Tak, ale pamiętaj, że to tylko dla thunks . Nie dotyczy konstruktorów. Oszacowanie wielkości thunk i tak jest trochę trudne - musisz policzyć wolne zmienne.
nominolo
4

Pakiet ghc-datasize udostępnia funkcję recursiveSize do obliczania rozmiaru obiektu GHC. Jednak...

Wyrzucanie elementów bezużytecznych jest wykonywane przed obliczeniem rozmiaru, ponieważ moduł odśmiecania pamięci utrudniłby przechodzenie po stercie.

... więc częste dzwonienie do tego nie byłoby praktyczne!

Zobacz także Jak znaleźć reprezentacje pamięci GHC dla typów danych? i jak mogę określić rozmiar czcionki w Haskell? .

mhwombat
źródło