haskellfoundation / haskellfoundation/hs-opt-handbook.github.io
The microest optimization wrt pointer tagging
- Dominant language
- HTML
- Stars
- 190
- Forks
- 11
- PR merge metrics
- No merged PRs in 30d
Description
I had a thought recently about something that affects runtime performance, but possibly in such a way so minimal that it might not even be worth adding to the book.
Nonetheless...
GHC tags pointers to evaluated heap-allocated data types with their tag. So, for example, pointers to heap-allocated Maybes will be tagged with `+1` if the allocated-value is `Nothing` and with `+2` if it is `Just ...`, (and with `+0` if it is a thunk, in which case we evaluate the thunk which will return a tagged pointer (with either +1 or +2)).
```haskell
{-# LANGUAGE MagicHash #-}
import Prelude(print)
import GHC.Exts
data Maybe a = Nothing
| Just a
{-# NOINLINE f #-}
f x = case x of
Nothing -> 1#
Just _ -> 2#
main = print (I# (f (Just 4)))
```
Then, to pattern match on `x` in the body of `f`, we don't need to dereference the pointer to the heap and check the constructor info, for we can simply (when x is evaluated) look at its tag.
The above example compiles to the following cmm code with `ghc -dno-typeable-binds -fforce-recomp -ddump-opt-cmm -ddump-to-file X.hs`:
```c
f_rib_entry() { // [R2]
...
cOo: // global
I64[Sp - 8] = block_cOf_info;
R1 = _sO4::P64;
Sp = Sp - 8;
// Check if tag is 0
if (R1 & 7 != 0) goto cOf; else goto cOg;
cOg: // tag==0 -> evaluate thunk
call (I64[R1])(R1) returns to cOf, args: 8, res: 8, upd: 8;
cOf: // tag/=0 -> pattern match through constructor tag
_sO5::P64 = R1;
_cOl::P64 = _sO5::P64 & 7;
// Check if tag is 1 or 2
if (_cOl::P64 != 1) goto cOk; else goto cOj;
cOk: // Tag is 2, con is Just, return unboxed 2
R1 = 2;
Sp = Sp + 8;
call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
cOj: // Tag is 1, con is Nothing, return unboxed 1
R1 = 1;
Sp = Sp + 8;
call (P64[Sp])(R1) args: 8, res: 0, upd: 8;
}
}
```
The question is what happens when we have more than 7 constructors (the tag can only be in the last 3 bits of the pointer, and 0 means unevaluated data type).
In the case of a datatype with more than 7 constructors, a tag of 7 means that the constructor index is 7 or higher, and therefore we have to dereference the pointer and look at the constructor info. The other tags from 0-6 retain their meaning.
Therefore, **the most common constructors of a datatype with >7 constructors are better off being in the first 6 constructors**, and the least common should come later. So if you have a datatype of which 80% of the times is constructed with some `Con1`, it is more performant to have it be one of the first 6.
This could possibly matter in really, REALLY, tight loops 😝, though I would love to see such a case. Or a gigantic code base in which all the useful constructors are defined last.
Contributor guide
Assessment
This issue has not been assessed yet.