CODEWITHSUNDEEP
haskell
carpemb
carpemb

Reputation: 701

Memory Footprint of Large Algebraic Data Types

Say I have an data type with a lot of constructors.

data ManyValues
  = Value0
  | Value1
  | Value2
  ...
  | Value255
  | Value256
  deriving (Show,Eq)

What's the memory footprint of any one value of this data type? My original understanding was that each constructor is a 8-bit word in memory, but what if there are more constructors in the data type than there are possible values in 8 bits. Does the constructor get bumped up to 16 bits and so on until it can address the full range of constructors present in the data type? Or do I have this all mixed up?

Upvotes: 4

Views: 132

Answers (1)

MathematicalOrchid
MathematicalOrchid

Reputation: 62818

As I understand it, a nullary constructor takes 1 machine word of storage (i.e., it's a pointer to statically allocated data). So whether your data structure has 1 such constructor or 1,000,000, it's still 1 machine word.

Constructors with fields take more space, but GHC special-cases nullary constructors to share a single static singleton between all instances of that value. (E.g., there is only ever one True in the entire program.)

Of course, when a thunk evaluates to an already-existing value (any value), GHC overwrites the thunk with a "redirection" node, which takes up some space. Periodically the garbage collector removes the redirections.

Upvotes: 3

Related Questions