Unboxed Types and Memory Layouts for OCaml

Stephen introduces a performance-driven proposal to make OCaml less dependent on boxed values. He stresses that the goal of unboxing is speed, then uses a device borrowed from Brendan Gregg: multiply tiny timings by a billion to make their relative scale easier to feel.

Under that scaling, simple arithmetic can take seconds, a system call minutes, SSD access about an hour and launching a trivial program days or longer depending on its runtime. A transatlantic ping stretches to years. The particular numbers depend on the machine, but the differences span many orders of magnitude.

Memory also has a hierarchy. Accessing L1 cache is far quicker than reaching main memory, and a translation lookaside buffer miss can require additional lookups. Smaller data can fit in faster cache levels, so the way a language represents values can materially affect performance.

A compiler must choose how many bytes a value occupies, how it is arranged, which registers pass it to functions and whether the garbage collector must track it. A pointer to an array, an eight-byte float and a four-byte integer have different natural representations.

In the OCaml representation he discusses, int32 and floating-point values can instead require separate heap blocks holding their contents. The extra block and pointer cost space and work. This is not an accidental design error: it addresses a difficult question about values whose concrete types are unknown.

Unknown types appear in polymorphic functions such as map and when code uses an abstract type from a module. The compiler must generate working code without knowing what a list element or abstract value really is.

One solution is a uniform layout for every value, associated here with Lisp; another is C++-style specialization after the concrete type is known. OCaml uses a tagged machine word: on a 64-bit machine the low bit distinguishes an immediate integer from a pointer. Values such as full-width floats that do not fit must be boxed.

Specializing every use can increase compilation time and code size, undermining OCaml’s fast builds. More fundamentally, higher-order and polymorphically recursive programs can make the set of required specializations difficult or even not finite. A simple C++-style solution is therefore not generally sufficient.

Automatically using specialized layouts when the compiler happens to know a type and uniform layouts elsewhere also has a cost. An abstraction that hides a type can unexpectedly change performance, and automatic boxing at boundaries can introduce unpredictable overhead. Stephen proposes making representation information explicit in the type system instead.

The early prototype recognizes an unboxed int64 represented as 64 raw bits. Unlike an ordinary value, those bits are passed in integer registers and must not be presented to the garbage collector as a pointer. Stephen calls the corresponding layouts value and bits64; examples become increasingly speculative as the talk progresses.

A module interface can declare an abstract order ID with bits64 layout without revealing its definition. Other code cannot treat the ID as an ordinary integer, but it can use a hash table designed for 64-bit keys. The type checker rejects a value-layout string where a bits64 key is required.

A type parameter normally defaults to value layout, but can be constrained to immediate. An immediate value is always represented as the tagged integer case, never a GC pointer. A reference restricted to such values can be read or modified without notifying the collector about pointer-graph changes.

The layout constraint participates in type inference: a function constructing an immediate-only reference must itself accept an immediate type, not every value type. Module signatures also use the relationship: a function valid for all value types can serve clients needing only immediate types, but the reverse is not generally true.

Stephen says this scheme should fit OCaml’s existing module system, polymorphism and inference. The intended effect is to expose the layout facts needed for compilation while keeping semantic details abstract.

One proposed application is a point record with two unboxed 64-bit coordinates. The ordinary point remains a boxed value pointing to a record, while an unboxed version can be passed as two raw components. In the proposed nested representation, a line made of two unboxed points can contain four 64-bit components inline.

Another possibility concerns options. Constructing Some x ordinarily allocates a box. That cost has a reason: OCaml must distinguish None, Some None, Some (Some None) and so on. Nested options are useful, for example when a hash-table lookup must distinguish a missing key from a key whose stored value is None.

Stephen proposes a separate nullable type whose parameter must be non_nullable. A string could be represented as present or absent without supporting another nullable layer; attempting to nest it would be a static type error. Because nested options are useful, this would be a new type rather than a silent change to option.

All of the layouts shown so far are fixed: one definition produces one block of compiled code. Generating separate implementations for multiple layouts through something like macros could be useful, but Stephen calls that idea speculative and far beyond the prototype then available.

In questions, Stephen explains that passing a large unboxed record resembles passing many arguments. The backend can use registers and then the stack when registers run out. He compares the design with Haskell work on levity polymorphism: this proposal relies more on subkinding relationships such as immediate being a subset of value.

A function compiled for all value layouts can also handle immediate values because immediate is a subset of value. That does not make value and bits64 interchangeable: those representations are genuinely different and cannot share the same implementation by that reasoning.

Asked why the compiler cannot simply look through abstraction or use whole-program compilation, Stephen says performance-relevant layout should be visible in source interfaces. Whole-program approaches have a broader optimization design space, but different representations complicate linking separately compiled code. Preserving fast separate and incremental compilation is an important constraint.

On a 32-bit machine, he says the backend can split a 64-bit value across two registers and generate the necessary operations. A polymorphic function is compiled for a particular layout; it can accept different types within that layout, but one implementation is not automatically polymorphic across incompatible layouts.

Asked about unboxed variants, Stephen says the team wants them but has not finalized a design. Mixed variants containing raw data and GC pointers raise difficult tagging and collector questions, so restrictions may be needed. The collector is precise: it must not be told to follow raw bits64 as a pointer.

Boxed and unboxed forms would need explicit conversions, though the syntax had not been chosen. The prototype’s compiler-performance impact had not been seriously benchmarked or optimized, although Stephen had not noticed a dramatic slowdown in his development work.

The proposed nullable type was also future work layered on a partially implemented prototype. Existing garbage-collector restrictions on heap blocks shaped the proposed layouts; relaxing mixed pointer and non-pointer representations would be a separate project.

An audience question raises the existing float-array special case. Stephen says one could encode a non-float layout to preserve efficient arrays, but he would rather avoid extending the life of that special case. He also mentions an older compiler patch for defining specialized array types that might become useful with unboxed values.

The prototype at the time performed layout type checking and could judge an annotated program’s proposed scheme, but then ignored the annotations and compiled as before. It therefore could not yet benchmark the new representation. Numerous design decisions, including defaults and inference, remained unsettled.

Finally, an audience member asks whether selecting a deeply nested field would force copies of large unboxed records. Stephen says the compiler could recognize projections or eliminate unused loads; the team must pay attention to avoiding unnecessary copies, but he does not expect this to require a Rust-like borrow system.