newsfilter.io
Conference Presentation

Unboxed Types for OCaml

Jane StreetStephen
Watch on YouTube →
  • The talk "Making a Camel Less Like Lisp and More Like C++" is motivated by the performance gap between microsecond/nanosecond operations and system calls, emphasizing that unboxing data is essential to avoid orders-of-magnitude latency differences.
  • Multiplying timing metrics by a billion reveals the cost of operations: simple addition/subtraction takes ~0.5 seconds, multiplication ~2 seconds, division ~30 seconds, OS user ID lookup ~2 minutes, SSD access ~1 hour, and starting a C process (bin true) ~2 days (unboxing in Python takes ~2 months).
  • Memory access latency varies drastically by hierarchy: L1 cache takes ~2 seconds, L2/L3 ~20-30 seconds, main memory ~2 minutes, and a TLB miss can take 5–10 minutes; spinning disk access historically took months but is now rare.
  • OCaml's default "Lisp-like" approach uses a uniform tagged representation (64-bit machine words) where small values (pointers or integers) are inlined, but larger or complex values (like 64-bit floats) are boxed (allocated separately), resulting in inefficient memory usage.
  • The alternative "C++-like" approach of unboxing unknown types at compile-time fails in OCaml due to separate compilation constraints, unpredictable compilation times from template expansion, and the inability to statically determine all types used by recursive polymorphic functions.
  • Proposals to dynamically mix strategies based on type knowledge are deemed too fragile, as library refactoring (e.g., moving types into modules) can change compiler knowledge, causing unpredictable boxing overhead.
  • The proposed solution introduces "layout kinds" (e.g., layout value, layout bit64, layout immediate) to explicitly annotate types, allowing the compiler to statically determine memory representation without relying on opaque heuristics.
  • layout bit64 types are represented as raw 64 bits, passed in registers, and explicitly excluded from garbage collection, whereas layout value types use the standard tagged pointer scheme.
  • Abstract types can now specify layout without revealing concrete implementation details, enabling efficient libraries (e.g., hash tables with 64-bit keys) that remain opaque to users while avoiding boxing.
  • layout immediate types (integers with no GC pointers) enable reference types that avoid garbage collector interaction entirely, as the type system guarantees only immediate types are stored.
  • Unboxed record types (e.g., hash point) allow fields to be represented as raw bits rather than pointers, significantly reducing memory footprint and allowing efficient passing of multiple fields via registers.
  • The prototype distinguishes between point (boxed, GC-managed) and hash point (unboxed, raw bits), enabling the compiler to optimize argument passing and memory layout based on the specific layout kind.
  • A new nullable type is proposed to statically prevent "option of option" nesting, allowing fields like string nullable to be represented efficiently without the overhead of distinguishing None from Some None.
  • Current prototypes support single-layout compilation per function; future plans include "deep macros" or polymorphism over layouts to generate multiple code versions for different layouts within a single abstraction.
  • The system integrates with OCaml's existing module system, allowing subkinding relations (e.g., immediate is a subtype of value) to enable functions optimized for immediate types to be used where value types are expected.
  • Backends will handle unboxed types exceeding register counts by passing arguments on the stack, and 64-bit types on 32-bit architectures will be split across registers by the existing compiler backend without source-level changes.
  • Conversions between boxed and unboxed types require explicit syntax rather than implicit functions to avoid requiring complex kind polymorphism at the primitive level.
  • The garbage collector remains precise; bit64 types are never exposed to it to prevent accidental pointer interpretation, while value types are fully tracked and immediate types are ignored.
  • The design avoids the "float array hack" by preferring to eliminate the hack entirely rather than creating complex layout kinds to work around it.
  • The prototype currently performs type checking and inference but compiles unboxed programs using standard boxing logic; benchmarking requires implementing a new compilation backend.
  • Existing work on defining custom array types (e.g., Leo Weiss's patch) is expected to be revisited to support arrays of unboxed types.
  • Nested unboxed record access (e.g., rect.bottomLeft.x) is expected to be optimized by the compiler discarding unused intermediate loads without requiring complex borrow-checking logic.
  • The presenter notes that the design space for layout kinds is not fully settled, with ongoing debates regarding default inferences for type variables and the trade-offs between polymorphism and subkinding.
  • Future integration with the standard library is intended for types like nullable, but implementation requires the prototype to reach a stage where it can actually generate optimized machine code.