Remove indirections caused by sum types, such as Maybe
|Reported by:||tibbe||Owned by:|
|Keywords:||Cc:||johan.tibell@…, pumpkingod@…, as@…, michal.terepeta@…, dterei, hackage.haskell.org@…, wren@…|
|Type of failure:||Runtime performance bug||Test Case:|
|Related Tickets:||Differential Rev(s):|
While null pointers cause correctness issues in languages that allow them, they do have one benefit over
Maybe when used to represent nullable values: they allow encoding the absence of a value cheaply. Using
Maybe to represent a nullable value adds an extra indirection (pointer) to get to the wrapped value.
We could use the bits set by pointer tagging to encode that the pointer points directly to the value, rather than to an intermediate constructor. I believe JHC takes this approach.
A motivating example is this implementation of a hash array mapped trie (HAMT): A HAMT stores key/value pairs and subtrees in two arrays.
data Node k v = MkNode (Array (Maybe k)) (Array (Either v (Node k v))
i in the first array is
Nothing, the second array contains a Node at index
i, otherwise it contains a value.
Adding an extra indirection, using
Either, adds both space (in terms of extra points and data constructor headers) and time (in terms of additional cache misses and branches).
Change History (25)
comment:20 Changed 2 years ago by
|Type of failure:||None/Unknown → Runtime performance bug|