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))
Iff index 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 Maybe or 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:8 in reply to: ↑ 6 Changed 6 years ago by tibbe
- Resolution set to wontfix
- Status changed from new to closed
comment:9 Changed 6 years ago by simonmar
- Resolution wontfix deleted
- Status changed from closed to new
comment:20 Changed 21 months ago by thomie
- difficulty set to Unknown
- Type of failure changed from None/Unknown to Runtime performance bug