Value layouts and unboxing

Plain OCaml has a uniform value representation

An OCaml value is one machine word. On a 64-bit runtime, the low bit of that word tells the runtime how to interpret the rest of the word.

The payload words are interpreted according to the block format. Some payload words are themselves OCaml values, so the GC follows them as pointers when needed. Other payload words are raw data, such as float bits or string bytes, so the GC must not treat them as pointers.

The header word tells the runtime how large the block is and how the payload should be scanned. For algebraic data types, the header tag also identifies which constructor with payload a block represents. Constructors with no payload are the simpler case: they are immediate integers, so they do not need a heap block at all.

This uniform model is a strength of OCaml. The GC, polymorphic functions, tuples, records, variants, and many library data structures can all talk about values without knowing the exact source type.

Examples

let plain_value_integer = 5

A tuple is not stored directly in the root word. The root word points to a heap block. The heap block has a header and then one payload word per tuple field.

let plain_value_tuple = (1, 2, 3)

Records have the same basic shape as tuples: a header followed by payload words. Immutable and mutable fields are both fields in the block; mutability is a property of what the program may do with the field, not a different block shape.

type quote =
  { symbol : string
  ; price : int
  ; mutable size : int
  }

let plain_value_record =
  { symbol = "OxCaml rocks"; price = 101; size = 7 }

Variants are also values

Algebraic data types use the same runtime model. A constructor with no payload is an immediate integer. A constructor with payload is a heap block; the header tag tells the runtime which constructor with payload it is.

type color = Red | Green | Blue

let constant_constructors = (Red, Green, Blue)

type order =
  | Market
  | Limit of string * int
  | Stop of string * int

let variant_payloads =
  ( Market
  , Limit ("ABC", 100)
  , Stop ("XYZ", 95)
  )

Recursive data is a graph of these same values. Each constructor with payload allocates a block. Its fields point at other values, which may themselves be immediates or pointers to blocks.

type tree =
  | Zero
  | One of tree
  | Two of tree * tree

let simple_tree =
  Two (One (One Zero), Zero)

Heap blocks can be shared

The recursive tree example has many blocks. The next point is about how those blocks connect to each other: the runtime representation is a graph, not a tree. If two fields point to the same heap object, there is one heap block with two incoming references.

let shared = "shared"

let shared_string_tuple = (shared, shared, "other")

The uniform model has costs

The uniform value model is convenient, but it has costs. Some data cannot fit directly in one immediate word. A standalone float or int64 is boxed: the value word points to a heap block containing the raw bits.

let boxed_numeric_values =
  (3.5, 456L)

Boxing creates heap allocation and pointer indirection. That is often fine. It becomes a problem in code where the cost of many small allocations, cache misses, or GC work matters.

Option values show the same issue. None is an immediate, but Some payload normally allocates a block to hold the payload.

let ordinary_none_int_option =
  (None : int option)

let ordinary_some_int_option =
  Some 7

Indirection shows up in nested data

Nested boxed data creates chains of pointers. Here the outer record points to a separate point block. Because the point contains only floats, OCaml uses its specialized all-float-record representation: the point block stores raw float payload words, not pointers to separate boxed float objects.

type boxed_point = { x : float; y : float }

type sample =
  { label : string
  ; point : boxed_point
  ; count : int
  }

let outer_record_with_boxed_point =
  { label = "p"
  ; point = { x = 1.0; y = 2.5 }
  ; count = 7
  }

One representation cannot be optimal for every performance-sensitive path. OxCaml adds ways to express a different representation when cost matters.

OxCaml layouts remove specific boxes

OxCaml layouts remove specific boxes from the uniform value model.

Tuple block

Uniform cost: an ordinary tuple allocates a heap block just to group its fields. Layout version: an unboxed product carries the components directly.

Unlike an ordinary tuple, the unboxed product is not represented by one pointer to a tuple block. Its representation is just its components: here, the immediate integer and the string pointer. Those components can live in separate registers or stack slots.

let unboxed_pair_of_values = #(1, "one")

Numeric boxes

Uniform cost: the boxed numeric example had a tuple block, a boxed float, and a custom block for the int64. Layout version: raw float# and int64# components store the bits directly in the product.

let unboxed_numeric_values = #(#3.5, #456L)

Nested record indirection

Uniform cost: the boxed-point example had an outer record pointing to a separate all-float point block. Layout version: the point is an unboxed record, so the outer record stores the two raw float fields inline and removes the separate point block.

That outer record is a mixed block: the runtime records which leading payload words are ordinary values that the GC should scan, and which remaining words are raw numeric data. Mixed-block layout may group the scannable value words before the raw numeric words, so the memory order need not match the source field order exactly.

type unboxed_point = #{ x : float#; y : float# }

type sample =
  { label : string
  ; point : unboxed_point
  ; count : int
  }

let outer_record_with_unboxed_point =
  { label = "p"
  ; point = #{ x = #1.0; y = #2.5 }
  ; count = 7
  }

Option payload allocation

Uniform cost: Some 7 allocates a wrapper block around an immediate integer payload. Layout version: or_null uses Null for the missing case, and This 7 has the same representation as the integer payload itself.

The missing case is represented by the null machine word. Compare this with None above, which is also a single immediate word but uses OCaml's ordinary constructor encoding rather than null.

let or_null_null_value =
  (Null : int or_null)

The present case is represented like the payload itself. Here the payload is an immediate integer, so the diagram has no wrapper block around it. Compare this with Some 7 above, where the present case allocates a block.

let or_null_this_int =
  (This 7 : int or_null)

or_null cannot be nested. The null word already means Null, so string or_null or_null would need two meanings for the same representation. The payload type must have room for the null word; it must not already use the null word itself.

This is the first place where we need to name which representations a type may have. The next section calls those representation requirements kinds.

Kinds record which representations are allowed

Once values can have different layouts, APIs need a way to say which layouts they accept. That is what representation kinds are for. Ordinary polymorphism usually assumes value. Unboxed values require signatures that mention layouts such as float64, bits32, bits64, word, or product layouts.

If a compiler error says a type parameter expects value, read that as: this API expects ordinary one-word OCaml values, not arbitrary unboxed layouts.

Here is an example.

To fix this, we have to specify the kind.

Abstract types need kinds too

The same issue appears at module boundaries. In a signature, a plain abstract type t defaults to kind value. That is fine for ordinary OCaml values, but it does not match an implementation where t has product layout. The fix is a kind annotation in the signature, such as type t : value & float64, because the layout is part of the calling convention that clients compile against.

Polymorphic code still has a layout

Ordinary polymorphic functions are usually polymorphic over ordinary OCaml values. This version of map says that explicitly: both the input element and the output element have kind value. That matches ordinary lists, whose cons cells store each element as one OCaml value word.

A product layout has a different calling convention. A value of kind value & value, such as #(string * string), is not one value word. It has two value components. Code that stores, passes, or returns such elements must be compiled with that layout in mind.

The implementation pattern still looks like ordinary map, but the generated machine code is different. It must know how many registers or stack slots carry an element, which fields the GC should scan, and how to store the result back into the container.

Templates help avoid repeating representation variants

ppx_template reduces layout-specific repetition. When the source pattern is the same but the modes, kinds, or layouts differ, templates generate the needed family of checked variants from one definition.

The ppx syntax looks like this:

The [@kind k = ...] attribute says: generate one copy where k is ordinary value, and another copy where k is the product layout value & value. The source body is the same, but the generated functions can have different calling conventions.

The playground output shows the generated instances. The generated names exist, but callers should not rely on those implementation details. At call sites, code selects the intended instance with a mono-attribute such as (id [@kind value & value]); id [@kind value] is the default instance and can be written simply as id.

For a map-shaped API, the input element layout and output element layout should be separate variables. Base and Core use this pattern for map-like functions: the input can have one kind and the mapped result can have another.

[%%template:
[@@@kind.default ki = (value, value & value)]
[@@@kind.default ko = (value, value & value)]

type ('a : k) vec
[@@kind k = (value, value & value)]

val map
  : ('a : ki) ('b : ko).
    ('a -> 'b)
    -> ('a vec[@kind ki])
    -> ('b vec[@kind ko])]

Syntax expansion templates are temporary. OxCaml is a work in progress, and in the future, proper layout polymorphism will replace templates.

Summary

Plain OCaml uses a uniform value representation: a word that is either an immediate or a pointer to a heap block. OxCaml keeps that model as the default, but lets performance-sensitive code use more precise layouts when a box, pointer indirection, or option allocation is the cost we need to remove.

Kinds record which representations an API accepts. Templates are the current way to repeat one source pattern across several kinds; layout polymorphism is intended to replace that template pattern over time.

Exercises

These exercises check your understanding of the material from the lecture. They only assume the concepts covered above, in roughly the order the notes introduce them.

Each exercise starts with a line saying what it checks and which section of the notes to reread if you get stuck.