Difference between revisions of "GHC/Memory Footprint"

From HaskellWiki
< GHC
Jump to navigation Jump to search
(New page: 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 he...)
 
 
(15 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
The heap is the garbage collected area of memory in which the running program introduces heap nodes.
  
The heap is the garbage collected area of memory in which the running program introduces heap nodes.
   
−
An in-depth explaination of the GHC internals can be found in the[http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects GHC Commentary: The Layout of Heap Objects].
 +
An in-depth explanation of the GHC internals can be found in the [http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects 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 [http://blog.johantibell.com/2011/06/computing-size-of-hashmap.html Computing the size of a HashMap].
  
A good introduction on how to compute the size of Haskell datastructures can be found in Johan Tibell's [http://blog.johantibell.com/2011/06/computing-size-of-hashmap.html Computing the size of a HashMap].
Line 11: Line 11:
 
See also [http://blog.johantibell.com/2011/06/memory-footprints-of-some-common-data.html Memory footprints of some common data types] which is the origin of the table below.
  
See also [http://blog.johantibell.com/2011/06/memory-footprints-of-some-common-data.html 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)
 +
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.
 +
A "word" is 4 bytes on 32=bit architectures, and 8 bytes on 64-bit architectures. 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.
  
   
 
=== Basic Types ===
  
=== Basic Types ===
Line 26: Line 24:
 
|-
  
|-
 
| ()
  
| ()
−
| ''1'' word
 +
| 0 words
−
| single shared ()
 +
| Single shared ()
 
|-
  
|-
 
| Bool
  
| Bool
−
| ''1'' word
 +
| 0 words
−
| single shared True/False
 +
| Single shared True/False
 
|-
  
|-
 
| Char
  
| Char
Line 39: Line 37:
 
| Int
  
| Int
 
| 2 words
  
| 2 words
  +
|
  +
|-
  +
| Int8
  +
| 2 words
  +
| Due to alignment
  +
|-
  +
| Int16
  +
| 2 words
  +
| Due to alignment
  +
|-
  +
| Int32
  +
| 2 words
  +
| Due to alignment
  +
|-
  +
| Int64 (on 64-bit arch)
  +
| 2 words
  +
|
  +
|-
  +
| Int64 (on 32-bit arch)
  +
| 3 words
  +
|
  +
|-
  +
| Word
  +
| 2 words
  +
|
  +
|-
  +
| Word8
  +
| 2 words
  +
| Due to alignment
  +
|-
  +
| Word16
  +
| 2 words
  +
| Due to alignment
  +
|-
  +
| Word32
  +
| 2 words
  +
| Due to alignment
  +
|-
  +
| Word64 (on 64-bit arch)
  +
| 2 words
  +
|
  +
|-
  +
| Word64 (on 32-bit arch)
  +
| 3 words
  +
|
 
|-
  
|-
−
| Int64 (on 64bit arch)
+
| Double (on 64-bit arch)
 
| 2 words
  
| 2 words
  +
|
 
|-
  
|-
−
| Int64 (on 32bit arch)
+
| Double (on 32-bit arch)
 
| 3 words
  
| 3 words
  +
|
 
|-
  
|-
 
| Integer (small)
  
| Integer (small)
 
| 2 words
  
| 2 words
  +
|
 
|-
  
|-
 
| Integer (bignum rep.)
  
| Integer (bignum rep.)
Line 64: Line 110:
 
| (va,vb)
  
| (va,vb)
 
| 3 words + sizeof(va) + sizeof(vb)
  
| 3 words + sizeof(va) + sizeof(vb)
  +
|
 
|-
  
|-
 
| [v]
  
| [v]
−
| (''1'' + 3N) words + sizeof(N v)
 +
| (''1'' + 3N) words + N * sizeof(v)
  +
| Single shared []
−
| [] is singleton
  
 
|-
  
|-
 
| Data.ByteString
  
| Data.ByteString
 
| 9 words + N bytes
 
| 9 words + N bytes
  +
|
 
|-
  
|-
 
| Data.Text
  
| Data.Text
 
| 6 words + 2N bytes
  
| 6 words + 2N bytes
  +
|
 
|-
 
|-
 
| Data.Map k v
  
| Data.Map k v
−
| 6N words + sizeof(N k + N v)
 +
| 6N words + N * (sizeof(k) + sizeof(v))
  +
|
 
|-
  
|-
 
| Data.Set v
  
| Data.Set v
−
| 5N words + sizeof(N v)
 +
| 5N words + N * sizeof(v)
  +
|
 
|-
  
|-
 
| Data.IntMap v
  
| Data.IntMap v
 
| (3N + 5(N-1) words) + sizeof(v)
  
| (3N + 5(N-1) words) + sizeof(v)
  +
|
 
|-
  
|-
 
| Data.IntSet
  
| Data.IntSet
 
| (2N + 5(N-1)) words
  
| (2N + 5(N-1)) words
  +
|
 
|-
  
|-
 
| Data.HashMap k v
  
| Data.HashMap k v
−
| (5N + 4(N-1)) words + sizeof(N k + N v)
 +
| 4.5N words + N * (sizeof(k) + sizeof(v))
  +
|
−
| non-HAMT impl.
  
 
|-
  
|-
 
| Data.HashSet
  
| Data.HashSet
−
| (5N + 4(N-1)) words + sizeof(N v)
 +
| 4.5N words + N * sizeof(v)
  +
|
 
|-
  
|-
 
| Data.Vector v
  
| Data.Vector v
−
| (4 + (2+N)) words + sizeof(N v)
 +
| (7 + N) words + N * sizeof(v)
  +
| Slices take 3N words + N * sizeof(v)
−
| ''O(1)'' slicing shares Array#
  
 
|}
  
|}

Latest revision as of 01:27, 18 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.

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 32=bit architectures, and 8 bytes on 64-bit architectures. Sizes are usually rounded up to word-boundaries.

Basic Types

Data type sizeof(T) Notes
() 0 words Single shared ()
Bool 0 words Single shared True/False
Char 2 words Char-sharing pool
Int 2 words
Int8 2 words Due to alignment
Int16 2 words Due to alignment
Int32 2 words Due to alignment
Int64 (on 64-bit arch) 2 words
Int64 (on 32-bit arch) 3 words
Word 2 words
Word8 2 words Due to alignment
Word16 2 words Due to alignment
Word32 2 words Due to alignment
Word64 (on 64-bit arch) 2 words
Word64 (on 32-bit arch) 3 words
Double (on 64-bit arch) 2 words
Double (on 32-bit arch) 3 words
Integer (small) 2 words
Integer (bignum rep.) 3 words + sizeof(bignum-repr) FIXME

Container Types

Data type sizeof(T) Notes
(va,vb) 3 words + sizeof(va) + sizeof(vb)
[v] (1 + 3N) words + N * sizeof(v) Single shared []
Data.ByteString 9 words + N bytes
Data.Text 6 words + 2N bytes
Data.Map k v 6N words + N * (sizeof(k) + sizeof(v))
Data.Set v 5N words + N * sizeof(v)
Data.IntMap v (3N + 5(N-1) words) + sizeof(v)
Data.IntSet (2N + 5(N-1)) words
Data.HashMap k v 4.5N words + N * (sizeof(k) + sizeof(v))
Data.HashSet 4.5N words + N * sizeof(v)
Data.Vector v (7 + N) words + N * sizeof(v) Slices take 3N words + N * sizeof(v)
Retrieved from "https://wiki.haskell.org/index.php?title=GHC/Memory_Footprint&oldid=54696"