Almost every programming language uses 64-bit integers on typical modern Intel machines. OCaml uses a special 63-bit representation. How does it affect OCaml?
OCaml int memory representation
Most of OCaml’s types are in memory represented as a header followed by data. The header is a 64-bit integer containing the length of the data and a tag. Tag is a rough classification of the type. The only OCaml’s types which differ from this are ints and sometimes floats.
Floats normally have header and data, data being the value of the float itself. This representation is called “boxed”. If a record’s field is float, record’s data will actually contain the pointer to the float data. The only exceptions are records with only floats and float arrays, whose data instead of pointers contain the values of floats. This representation is called “unboxed”.
Values of type int are never stored as header and data (boxed). Int
(x << 1) | 1, where
<< is left shift and
| is bitwise or, hence
its least significant bit is always set. Pointers are word aligned, so they will
never have this bit set, hence how ints and pointers are discerned. It is
assumed that much of typical data is integers, so this is done to significantly
- there’s no need to dereference a pointer when getting an int
- no memory allocation is needed when creating ints
- less work for the garbage collector
- less memory fragmentation
- no memory is needed for int headers
Distinguishing whether a value is int or pointer is as simple as testing
1, so this feature doesn’t slow down garbage collector, polymorphic hash,
polymorphic compare and whatever else structurally inspects data. One should
note that this doesn’t apply to the types
int64, which are always
Having the extra bit comes with a price – arithmetic operations are more complicated. For example
x + yis translated to CPU instructions
x + y - 1
x * yis translated to CPU instructions
(x >> 1) * (y - 1) + 1
x / yis translated to CPU instructions
(((x >> 1) / (y >> 1)) << 1) + 1
x lsl yis translated to CPU instructions
((x - 1) << (y >> 1)) + 1
Sometimes this penalty is small or nonexistent. For instance there’s no need to
fix the bit in
x + y - z. Only one bit fixing is needed for all five
x + y + z + w + u + v.
Another help is the Intel CPU instruction
LEA, which can compute the sum of
three integers with a single instruction, like
x + y - 1. Unfortunately,
LEA became very slow in the recent generations of CPUs. Intel doesn’t suggest
this will change.
This benchmark (test.ml) tries to estimate the difference in the performance. The results from Sandy Bridge show about 2 times speed difference in arithmetic operations. Assembly can be examined by compiling using “ocamlopt -S test.ml”.
speed(ns) 63-bit 64-bit slowdown add independent 0.327588 0.121502 2.696156 add dependent 0.328160 0.169375 1.937477 mul independent 0.614824 0.328060 1.874120 mul dependent 1.094343 0.328872 3.327565 lsl independent 0.359828 0.166088 2.166489 lsl dependent 0.762251 0.177468 4.295151 xor independent 0.249350 0.122900 2.028886 xor dependent 0.404255 0.170380 2.372668
Agner’s instruction tables show that the difference is even bigger with later
generations of CPUs. For instance, Haswell can do four integer adds per cycle
The benefits of unboxed ints are amazing. On the other hand, arithmetic operations are significantly slower. How much do arithmetic operations affect an average program? Could we have a solution which would keep ints unboxed but have fast arithmetic operations?