Why is an int in OCaml only 31 bits?

Question

Haven't seen this "feature" anywhere else. I know that the 32nd bit is used for garbage collection. But why is it that way only for ints and not for the other basic types?

Solution 1

This is called a tagged pointer representation, and is a pretty common optimization trick used in many different interpreters, VMs and runtime systems for decades. Pretty much every Lisp implementation uses them, many Smalltalk VMs, many Ruby interpreters, and so on.

Usually, in those languages, you always pass around pointers to objects. An object itself consists of an object header, which contains object metadata (like the type of an object, its class(es), maybe access control restrictions or security annotations and so on), and then the actual object data itself. So, a simple integer would be represented as a pointer plus an object consisting of metadata and the actual integer. Even with a very compact representation, that's something like 6 Byte for a simple integer.

Also, you cannot pass such an integer object to the CPU to perform fast integer arithmetic. If you want to add two integers, you really only have two pointers, which point to the beginning of the object headers of the two integer objects you want to add. So, you first need to perform integer arithmetic on the first pointer to add the offset into the object to it where the integer data is stored. Then you have to dereference that address. Do the same again with the second integer. Now you have two integers you can actually ask the CPU to add. Of course, you need to now construct a new integer object to hold the result.

So, in order to perform one integer addition, you actually need to perform three integer additions plus two pointer dererefences plus one object construction. And you take up almost 20 Byte.

However, the trick is that with so-called immutable value types like integers, you usually don't need all the metadata in the object header: you can just leave all that stuff out, and simply synthesize it (which is VM-nerd-speak for "fake it"), when anyone cares to look. An integer will always have class Integer, there's no need to separately store that information. If someone uses reflection to figure out the class of an integer, you simply reply Integer and nobody will ever know that you didn't actually store that information in the object header and that in fact, there isn't even an object header (or an object).

So, the trick is to store the value of the object within the pointer to the object, effectively collapsing the two into one.

There are CPUs which actually have additional space within a pointer (so-called tag bits) that allow you to store extra information about the pointer within the pointer itself. Extra information like "this isn't actually a pointer, this is an integer". Examples include the Burroughs B5000, the various Lisp Machines or the AS/400. Unfortunately, most of the current mainstream CPUs don't have that feature.

However, there is a way out: most current mainstream CPUs work significantly slower when addresses aren't aligned on word boundaries. Some even don't support unaligned access at all.

What this means is that in practice, all pointers will be divisible by 4, which means they will always end with two 0 bits. This allows us to distinguish between real pointers (that end in 00) and pointers which are actually integers in disguise (those that end with 1). And it still leaves us with all pointers that end in 10 free to do other stuff. Also, most modern operating systems reserve the very low addresses for themselves, which gives us another area to mess around with (pointers that start with, say, 24 0s and end with 00).

So, you can encode a 31-bit integer into a pointer, by simply shifting it 1 bit to the left and adding 1 to it. And you can perform very fast integer arithmetic with those, by simply shifting them appropriately (sometimes not even that is necessary).

What do we do with those other address spaces? Well, typical examples include encoding floats in the other large address space and a number of special objects like true, false, nil, the 127 ASCII characters, some commonly used short strings, the empty list, the empty object, the empty array and so on near the 0 address.

For example, in the MRI, YARV and Rubinius Ruby interpreters, integers are encoded the way I described above, false is encoded as address 0 (which just so happens also to be the representation of false in C), true as address 2 (which just so happens to be the C representation of true shifted by one bit) and nil as 4.

Solution 2

See the the "representation of integers, tag bits, heap-allocated values" section of https://ocaml.org/learn/tutorials/performance_and_profiling.html for a good description.

The short answer is that it is for performance. When passing an argument to a function it is either passed as an integer or a pointer. At a machine level language level there is no way to tell if a register contains an integer or a pointer, it is just a 32 or 64 bit value. So the OCaml run time checks the tag bit to determine if what it received was an integer or a pointer. If the tag bit is set, then the value is an integer and it is passed to the correct overload. Otherwise it is a pointer and type is looked up.

Why do only integers have this tag? Because everything else is passed as a pointer. What is passed is either an integer or a pointer to some other data type. With only one tag bit, there can be only two cases.

Solution 3

It's not exactly "used for garbage collection." It's used for internally distinguishing between a pointer and an unboxed integer.

Solution 4

I have to add this link to help the OP to understand more A 63-bit floating-point type for 64-bit OCaml

Although the title of the article seems about float, it actually talking about the extra 1 bit

The OCaml runtime allows polymorphism through the uniform representation of types. Every OCaml value is represented as a single word, so that it is possible to have a single implementation for, say, “list of things”, with functions to access (e.g. List.length) and build (e.g. List.map) these lists that work just the same whether they are lists of ints, of floats, or of lists of sets of integers.

Anything that does not fit in in a word is allocated in a block in the heap. The word representing this data is then a pointer to the block. Since the heap contains only blocks of words, all these pointers are aligned: their few least significants bits are always unset.

Argumentless constructors (like this: type fruit = Apple | Orange | Banana) and integers do not represent so much information that they need to be allocated in the heap. Their representation is unboxed. The data is directly inside the word that would otherwise have been a pointer. So while a list of lists is actually a list of pointers, a list of ints contains the ints with one less indirection. The functions accessing and building lists do not notice because ints and pointers have the same size.

Still, the Garbage Collector needs to be able to recognize pointers from integers. A pointer points to a well-formed block in the heap that is by definition alive (since it is being visited by the GC) and should be marked so. An integer can have any value and could, if precautions were not taken, accidentally look like a pointer. This could cause dead blocks to look alive, but much worse, it would also cause the GC to change bits in what it thinks is the header of a live block, when it is actually following an integer that looks like a pointer and messing up user data.

This is why unboxed integers provide 31 bits (for 32-bit OCaml) or 63 bits (for 64-bit OCaml) to the OCaml programmer. In the representation, behind the scenes, the least significant bit of a word containing an integer is always set, to distinguish it from a pointer. 31- or 63-bit integers are rather unusual, so anyone who uses OCaml at all knows this. What users of OCaml do not usually know is why there isn't a 63-bit unboxed float type for 64-bit OCaml.

Solution 5

Why is an int in OCaml only 31 bits?

Basically, to get the best possible performance on the Coq theorem prover where the dominant operation is pattern matching and the dominant data types are variant types. The best data representation was found to be a uniform representation using tags to distinguish pointers from unboxed data.

But why is it that way only for ints and not for the other basic types?

Not only int. Other types such as char and enums use the same tagged representation.

View more solutions

Comments

[Tom Anderson]

And the corollary to that is that it is that way for at least one other type, namely pointers. If floats aren't also 31 bits, then i assume it's because they're stored as objects on the heap, and referred to with pointers. I would guess there's a compact form for arrays of them, though.

[Tobu]

That information is exactly what the GC needs to navigate the pointer graph.

[surfmuggle]

There are people who say that this answer is imprecise. I have no idea if this is the case or if they are nitpicking. I just thought i would point to it in case it contains some truth.

[Pascal Cuoq]

@threeFourOneSixOneThree This answer is not completely accurate for OCaml because, in OCaml, this answer's “synthesize it” part never takes place. OCaml is not an object-oriented language like Smalltalk or Java are. There is never any reason to retrieve the methods table of an OCaml int.

[Totti]

"It's used for internally distinguishing between a pointer and an unboxed integer". Does anything else use it for that other than the GC?

[Totti]

"The short answer is that it is for performance". Specifically the performance of Coq. The performance of almost everything else suffers from this design decision.

[phuclv]

Chrome's V8 engine also uses a tagged pointer and store a 31-bit integer which is called smi (Small Integer) as an optimization\

[Jörg W Mittag]

@phuclv: This is not surprising, of course. Just like the HotSpot JVM, V8 is based on the Animorphic Smalltalk VM, which in turn is based on the Self VM. And V8 was developed by (some of) the same people who developed the HotSpot JVM, the Animorphic Smalltalk VM, and the Self VM. Lars Bak, in particular, worked on all of those, plus his own Smalltalk VM called OOVM. So, it is not surprising at all that V8 uses well-known tricks from the Smalltalk world, since it was created by Smalltalkers based on Smalltalk technology.

[uhbif19]

@JD Why is that? Can you provide some sources about this statement?

[corwin.amber]

In fact, Coq itself uses very little integer arithmetic internally — although computing hash values of terms (known as "hashcons") is a significant optimization used within the engine. Still, it is definitely not only Coq that needs fast hashing, or integer arithmetic & bitwise operations in general.

[Maëlan]

The answer mentions “encoding floats in the address space”. But again the question was about OCaml, and what OCaml calls a float is what C calls a double, i.e. a 64-bit IEEE floating point number. Obviously you can’t encode those even with 64-bit words where you reserve some bits for tagging. In OCaml, floating-point numbers are boxed (even though there are optimizations e.g. for float arrays).

[Maëlan]

”And it still leaves us with all pointers that end in 10 free to do other stuff.” This calls for the question: does OCaml use that range for encoding anything? Or other ranges, for what it’s worth, I guess that in 64-bit OCaml aligned pointers are multiple of 8, so that you have three spare bits.

[Maëlan]

@JD I would be interested in sources too. It seems to me that integers alone, yet other unboxed values (booleans, constant constructors and so on) are used pervasively by almost any program, whose performance is thus obviously benefiting from that optimization. The overhead imposed on each arithmetic operation (shifting the tag bit) is negligible, especially with 21st century ALU, especially compared to the pointer indirections that boxed representations would imply. Anyway, if you really want boxed integers, OCaml has them too.

[Maëlan]

That’s my naive understanding at least, but probably you are referring to another cost?

[Jörg W Mittag]

@Maëlan: In Ruby, Floats are defined to be ISO/IEC 60559 binary64 doubles. Yet, YARV has so-called flonums (analogous to fixnums for integers), which are floats that fit into 62 bits. If they don't, they are automatically boxed. It's a completely internal, private optimization that is invisible to the programmer. I see no reason why OCaml couldn't do the same. It is in fact, exactly the same trick as the one used for integers.

[Maëlan]

@JörgWMittag interesting! Maybe that would be worth implementing in OCaml as well. If I had to guess why it is not done already, I would point out a tendency from the language designers not to tune the memory representation too much, to keep it simple and predictable. There is some adhoc-ery for floats already, but I think they don’t want more. Also, fixnums probably incur a penalty as all integer operations now branch, right? Maybe we don’t care because one branch is highly uncommon, as boxing only happens when the (non-sign) most-significant bit is set.

[Totti]

@Maëlan You cannot say it is "obviously" benefitting when the tradeoffs are not clear and the issue is more specific that just "integer arithmetic". The question is whether you can get away with 31-bit integer arithmetic because, if so, performance will be ok. But if not your performance will be vastly worse.

[Totti]

@Maëlan For example, HLVM was 32x faster than OCaml on this integer benchmark because the benchmark requires full-width integers reddit.com/r/ocaml/comments/ekia5/…

[Totti]

@Maëlan If the overhead is "negligible" why is F# substantially faster than OCaml at this integer-only benchmark from SciMark2. gist.github.com/jdh30/8640467 gist.github.com/jdh30/8639742

[Maëlan]

Okay, so I’m saying that the performance overhead is negligible when sticking to unboxed integers, you’re saying that performance is terrible when using boxed integers. I think we agree. Now, about the tradeoff between boxed and unboxed, I get that the original question was about 32-bit machines, but nowadays 64-bit systems are common; is it a common scenario that 63 bits are not enough, and you absolutely need arithmetic with a 64th bit, but you don’t need integers larger than 64 bits?