Why can Julia be better about boxing types than OCaml?

Offtopic
1

I was reading this article about OCaml’s special int type:

The tl;dr is that OCaml represents data as a 64-bit header followed by the actual data. This includes int64 and, often, floats. However, they special case the default int type so that the least significant bit is always set to true. This allows them to check that value is an int, not a pointer.

As a compiled language with a rich type system, I’m shocked that there isn’t enough information for the complier to elide tags and unbox almost everything. However, I don’t know any OCaml folks, so I thought I’d try the inverse question here:

Why doesn’t julia need to box isbits types in most cases?

Edit: Some additional context from another article:

a float value is represented by a pointer to a block (tag 253) holding one data word (64-bit) or two (32-bit). Floats are thus boxed, and a single float value requires three or four words (one for representing the pointer, one for the block header, and one or two for the float bits). Note that this representation is only required when floats are stored in data structures, or passed from one function to another. Within a single function’s body, local float values can be represented unboxed in memory or in registers, and the OCaml compiler apply such optimisations. There are also plans to allow unboxed calling conventions between functions.
About unboxed float arrays | LexiFi

So local floats are stored on the stack, but if you have a field in a record, then it’s actually a pointer to a heap allocated float (unless all the fields are floats).

1 Like
2

may be of interests

2 Likes
3

Yeah, this is the crux right here (from the presentation above):

image
image674×374 43.5 KB

Julia adds a third option:

  1. Why not both? Compile specializations when we know the type, otherwise box dynamic/type-unstable code.
11 Likes
4

Note that this is an old trick, also called “tagged pointers”, which has been used in e.g. some implementations of Scheme and JavaScript. A related technique is NaN boxing, which mixes pointers and Float64 instead of integers, and has been used for e.g. JavaScript and Lua.

Here is a nice old (2011) blog post on these techniques: Value Representations in JavaScript Implementations.

Of course, this was not entirely new to Julia. Optimizing compilers for other dynamic languages, like JavaScript, have done this too. However, Julia was designed from the beginning to be friendly to devirtualization and inference, while remaining dynamic, rather than trying to retrofit it onto an existing dynamic language.

5 Likes
5

The speaker addresses the “why not both” a little ways into the talk with “It explodes compilation time and can be quite brittle to surprising edge cases.”

He didn’t have a call us out like that. :wink:

6 Likes
6

I have to admit that I understood what “devirtualization” is when I started programming Julia. When I wrote C++ (decades ago), I implicitly assumed that because the compiler could do this, it was done. Only after I understood how Julia does this did I recognize why it is not so obvious to do this always in C++.

3 Likes