[Haskell-cafe] Sizes in memory?

[Joachim Breitner]

Hi Dušan,


Am Freitag, den 19.02.2021, 09:05 +0100 schrieb Dušan Kolář:
> Dear café,
> 
> I don't know, whether this is the right place to ask, but I'll try :-)
> 
> If I would like to know size of the list in the memory (after complete evaluation, e.g. deepseq). The type is [( Int, [([Int],[Int])] )].
> 
> So we have K tuples of the type (Int,[([Int],[Int])])
> Each tuple has N tuples of the type ([Int],[Int])
> and each of these lists M elements long (yes, both a are of the same length).
> 
> Top level list needs (on 64bit CPU) 8 bytes for pointer to elements, 8 bytes to point to another element, some more "expenses", probably yes, tag, anything else?

A list cons cell indeed needs 3 words.

> So we have K*(16+XXX), where XXX is for size of (Int,[([Int],[Int])]).
> 
> Tuple needs 8 bytes for each pointer, so XXX = 16 + YYY, where YYY is
> the size of the [([Int],[Int])] list.

Again, another word for the tag, so make it 32 bytes for the tuple.

> It needs 8 + 8 bytes on the list, we have N such elements, thus YYY =
> N * (16 + ZZZ), where ZZZ is size of the ([Int],[Int]).
> 
> Again tuple, so 16 bytes + 2*(M * (16 + 8))
> -- 16 bytes for 2 tuple elements
> -- 2 for two lists
> -- every list 16 bytes for list itself
> -- 8 bytes for Int
> 
> So ZZZ = 16 + 2*(M * (16 + 8)), thus
> YYY = N * (16 + 16 + 2*(M * (16 + 8))), thus
> XXX = 16 + N * (16 + 16 + 2*(M * (16 + 8))), thus
> size = K * (16 + 16 + N * (16 + 16 + 2*(M * (16 + 8))))
>      = K* (32 + N* (32 + M*48) )
> 
> Am I right? Roughly right? Or totally wrong?

Up to the tags, mostly right, got lost half way. An Int is actually two
words as well (tag plus raw value). Unless its value is ≤ 16, these are
statically allocated…

You can play around with
https://hackage.haskell.org/package/ghc-datasize
or sign up to https://bobkonf.de/2021/de/registration.html where I
happen to give a tutorial next Friday where I will look (among other
things) exactly at questions like these.

Or seem my talk on that from a while ago:
https://vimeo.com/100166511

> Why am I asking? In reality the memory consumption is much higher, so
> I must be missing some extras, e.g. each memory chunk extra 8 bytes
> for GC, extra for tag, extra to point to VMT?

You missed the one word for the tag, yes. And are you sure it’s fully
evaluated? Else you might see thunks around.

Cheers,
Joachim

-- 
Joachim Breitner
  mail at joachim-breitner.de
  http://www.joachim-breitner.de/