Pegada de memória dos tipos de dados Haskell

124

Como posso encontrar a quantidade real de memória necessária para armazenar um valor de algum tipo de dados no Haskell (principalmente com GHC)? É possível avaliá-lo em tempo de execução (por exemplo, no GHCi) ou é possível estimar os requisitos de memória de um tipo de dados composto a partir de seus componentes?

Em geral, se os requisitos de memória dos tipos ae bsão conhecidos, qual é a sobrecarga de memória dos tipos de dados algébricos, como:

data Uno = Uno a
data Due = Due a b

Por exemplo, quantos bytes na memória esses valores ocupam?

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

Eu entendo que a alocação de memória real é maior devido ao atraso na coleta de lixo. Pode ser significativamente diferente devido à avaliação lenta (e o tamanho da conversão não está relacionado ao tamanho do valor). A questão é, dado um tipo de dados, quanta memória seu valor leva quando totalmente avaliado?

Eu descobri que existe uma :set +sopção no GHCi para ver estatísticas de memória, mas não está claro como estimar a área de cobertura de memória de um único valor.

sastanina
fonte

Respostas:

156

(O seguinte se aplica ao GHC, outros compiladores podem usar diferentes convenções de armazenamento)

Regra geral: um construtor custa uma palavra para um cabeçalho e uma palavra para cada campo . Exceção: um construtor sem campos (como Nothingou True) não ocupa espaço, porque o GHC cria uma única instância desses construtores e a compartilha entre todos os usos.

Uma palavra tem 4 bytes em uma máquina de 32 bits e 8 bytes em uma máquina de 64 bits.

Então por exemplo

data Uno = Uno a
data Due = Due a b

um Unoleva 2 palavras e um Dueleva 3.

O Inttipo é definido como

data Int = I# Int#

agora, Int#leva uma palavra, Intleva 2 no total. A maioria dos tipos desembalados tirar uma palavra, sendo as excepções Int64#, Word64#e Double#(em uma máquina de 32 bits) que levam 2. GHC realmente tem um cache de pequenos valores do tipo Inte Char, por isso, em muitos casos estes não tomar nenhuma espaço de pilha em tudo. Um Stringrequer apenas espaço para as células da lista, a menos que você use Chars> 255.

Um Int8tem representação idêntica a Int. Integeré definido assim:

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

portanto, um pequeno Integer( S#) ocupa duas palavras, mas um inteiro grande ocupa uma quantidade variável de espaço, dependendo de seu valor. A ByteArray#leva 2 palavras (cabeçalho + tamanho) mais espaço para a própria matriz.

Observe que um construtor definido com newtypeé livre . newtypeé uma idéia puramente em tempo de compilação e não ocupa espaço e não custa instruções em tempo de execução.

Mais detalhes em O layout dos objetos de pilha no comentário do GHC .

Simon Marlow
fonte
1
Obrigado Simon. Era exatamente isso que eu queria saber.
sastanin
2
O cabeçalho não é duas palavras? Um para o tag e outro para o ponteiro de encaminhamento para uso durante o GC ou avaliação? Então, isso não adicionaria uma palavra ao seu total?
Edward KMETT 15/07
5
@ Edward: Thunks são substituídos por indiretos (que são removidos posteriormente pelo GC), mas são apenas duas palavras, e cada objeto de heap é garantido para ter pelo menos duas duas palavras em tamanho. Sem nenhum recurso de criação de perfil ou depuração ativado, o cabeçalho é realmente apenas uma palavra. No GHC, ou seja, outras implementações podem fazer as coisas de maneira diferente.
Nominolo 15/07/10
3
nominolo: sim, mas de Closure.h: / * Um thunk possui uma palavra de preenchimento para receber o valor atualizado. Isso ocorre para que a atualização não substitua a carga útil, para evitar a necessidade de bloquear o thunk durante a entrada e a atualização. Nota: isso não se aplica aos THUNK_STATICs, que não têm carga útil. Nota: deixamos essa palavra de preenchimento de todas as formas, em vez de apenas SMP, para que não tenhamos que recompilar todas as nossas bibliotecas para SMP. * / A carga útil não é substituída durante um indireto. A indireção é escrita em um local separado no cabeçalho.
Edward KMETT
6
Sim, mas observe que isso é apenas para thunks . Não se aplica a construtores. Estimar o tamanho de um thunk é um pouco difícil de qualquer maneira - você precisa contar as variáveis ​​livres.
Nominolo 15/07/10
4

O pacote ghc-datasize fornece a função recursiveSize para calcular o tamanho de um objeto GHC. Contudo...

Uma coleta de lixo é executada antes do cálculo do tamanho, porque o coletor de lixo dificultava as caminhadas na pilha.

... por isso não seria prático chamar isso com frequência!

Veja também Como descobrir as representações de memória dos tipos de dados do GHC? e Como posso determinar o tamanho de um tipo no Haskell? .

mhwombat
fonte