Revision as of 22:14, 17 November 2012
This page is concerned with the memory footprint of Haskell data structures stored in the heap.
The heap is the garbage collected area of memory in which the running program introduces heap nodes.
An in-depth explanation of the GHC internals can be found in the GHC Commentary: The Layout of Heap Objects.
A good introduction on how to compute the size of Haskell datastructures can be found in Johan Tibell's Computing the size of a HashMap.
1 Memory Footprints of common data types
See also Memory footprints of some common data types which is the origin of the table below.
The following tables assumes fully evaluated data structures (i.e. no thunks)
A "word" is 4 bytes on 32bit archs, and 8 bytes on 64bit archs. Sizes are usually rounded up to word-boundaries.
Constructors with no fields are instantiated only once on the heap. This is expressed in the sizeof()-formulas below with italic numbers which can be ignored for practical considerations.
1.1 Basic Types
|()||1 word||single shared ()|
|Bool||1 word||single shared True/False|
|Char||2 words||Char-sharing pool|
|Int64 (on 64bit arch)||2 words|
|Int64 (on 32bit arch)||3 words|
|Double (on 64bit arch)||2 words|
|Double (on 32bit arch)||3 words|
|Integer (small)||2 words|
|Integer (bignum rep.)||3 words + sizeof(bignum-repr)||FIXME|
1.2 Container Types
|(va,vb)||3 words + sizeof(va) + sizeof(vb)|
|[v]||(1 + 3N) words + sizeof(N v)|| is singleton|
|Data.ByteString||9 words + N bytes|
|Data.Text||6 words + 2N bytes|
|Data.Map k v||6N words + sizeof(N k + N v)|
|Data.Set v||5N words + sizeof(N v)|
|Data.IntMap v||(3N + 5(N-1) words) + sizeof(v)|
|Data.IntSet||(2N + 5(N-1)) words|
|Data.HashMap k v||(5N + 4(N-1)) words + sizeof(N k + N v)||non-HAMT impl.|
|Data.HashSet||(5N + 4(N-1)) words + sizeof(N v)|
|Data.Vector v||(4 + (2+N)) words + sizeof(N v)||O(1) slicing shares Array#|