Boxing

A boxed value is one stored in a heap block and handled through a pointer; an unboxed value is held directly in a register, a stack slot or a field. Polymorphic functions such as List.map or Array.length are compiled once and run on values of every type, so the runtime needs each value to have the same size and to be recognisable by the garbage collector. The common solution, called a uniform representation, is for every value to occupy one word: either an immediate, such as a small integer, or a pointer to a block^[1][3]. Anything that does not fit in a word, such as a 64-bit float, is boxed.

An OCaml value is a word. If its lowest bit is 1 it is an immediate integer $n$, stored as $2n+1$; this covers int, char, bool, unit and the constant constructors of variants, such as [] and None. Otherwise it is a pointer to a block, preceded by a header word holding the block's size and an 8-bit tag. Tag $k$ for small $k$ marks the $k$-th non-constant constructor of a variant, and the high tags mark blocks the collector must not scan: 252 for strings, 253 for a boxed float, 254 for a flat array of floats, 255 for custom blocks such as Int64.t^[3][4].

(* Print how a value is represented: an immediate integer, or a pointer
   to a heap block with a header (tag and size). *)
let describe name v =
  let r = Obj.repr v in
  if Obj.is_int r then Printf.printf "%-20s immediate %d\n" name (Obj.obj r : int)
  else
    Printf.printf "%-20s block, tag %3d, %d fields, %2d words in all\n" name
      (Obj.tag r) (Obj.size r) (Obj.reachable_words r)
 
type point = { x : float; y : float }

42                   immediate 42
'a'                  immediate 97
true                 immediate 1
[]                   immediate 0
None                 immediate 0
Some 42              block, tag   0, 1 fields,  2 words in all
[1; 2; 3]            block, tag   0, 2 fields,  9 words in all
3.14                 block, tag 253, 1 fields,  2 words in all
(1.0, 2.0)           block, tag   0, 2 fields,  7 words in all
{ x = 1.0; y = 2.0 } block, tag 254, 2 fields,  3 words in all
[| 1.0; 2.0; 3.0 |]  block, tag 254, 3 fields,  4 words in all
"hello"              block, tag 252, 1 fields,  2 words in all
42L                  block, tag 255, 2 fields,  3 words in all

A float on its own is a block of two words, header and payload. A pair of floats is a block of two pointers to two such blocks, seven words in all. A record or array whose fields are all floats is stored flat, with tag 254, because the compiler can see from the type that every field is a float^[4].

A boxed value costs an allocation when it is created and an indirection when it is read. For floats this is the main overhead of numeric OCaml code. The native compiler keeps a float unboxed in a register while it stays inside one function and its type is known, as in a loop over a local ref, and boxes it only when it is stored in a polymorphic place, passed to a function that is not inlined, or returned^[1].

(* Words allocated on the minor heap while summing a million floats. *)
let measure name f =
  let before = Gc.minor_words () in
  let s = f () in
  Printf.printf "%-26s sum %.0f, %9.0f words allocated\n" name s (Gc.minor_words () -. before)
 
let a = Array.init 1_000_000 float_of_int
let l = Array.to_list a

loop over float array      sum 499999500000,         2 words allocated
Array.fold_left (+.)       sum 499999500000,   4000000 words allocated
List.fold_left (+.)        sum 499999500000,   2000000 words allocated
floats in a list of pairs  sum 499999500000,   8000005 words allocated

The explicit loop allocates only the final result. Array.fold_left calls the closure (+.) through the generic calling convention, so each element read from the flat array is boxed, two words, and so is each new accumulator, another two. The list version boxes only the accumulator, since the elements are already boxed in the list. A list of pairs adds three words for each cons cell and three for each pair.

Other languages expose unboxing in the types. GHC has unboxed types such as Int# and Double#, and the kind of a type records whether its values are boxed, so that polymorphic code can only be instantiated at boxed types^[2][5]. Java boxes primitive values automatically when they are used as objects, int to Integer^[6].

Lisp systems used a uniform tagged representation, with small integers as immediates, from the 1960s, and ML implementations inherited it. Peyton Jones and Launchbury made unboxed values first-class in Haskell in 1991, and Leroy showed in 1992 how an ML compiler can keep values unboxed in monomorphic code and box them only at the boundary with polymorphic code^[1][2]. OCaml's flat float arrays and records come from this line of work. Java added automatic boxing in Java 5 in 2004^[6], and GHC's levity polymorphism of 2017 made the boxed–unboxed distinction part of the kind system^[5].

• Generational GCA garbage collector that splits the heap by age, because most objects die young: new objects go to a small nursery collected often by copying, and survivors are promoted to a larger heap collected rarely. A write barrier records old-to-young pointers so that a minor collection need not scan the old heap.
• ClosureA closure is a function value together with the environment in which it was created: the bindings of the free variables its body refers to. Closures are what make functions first-class values in a lexically scoped language. Compilers implement them by closure conversion, which turns each function into a code pointer paired with a record of captured values.
• Algebraic data typeAn algebraic data type is a type built from sums, where a value is one of several alternatives, and products, where a value has several components at once, possibly recursively. The name comes from counting: the number of values of a sum is the sum of the counts, and of a product their product, so types obey the laws of algebra. Values are taken apart by pattern matching, which the compiler checks for missing cases.

1. [1]X. Leroy, “Unboxed objects and polymorphic typing”, POPL (1992).
2. [2]S. Peyton Jones, J. Launchbury, “Unboxed values as first class citizens in a non-strict functional language”, FPCA (1991).
3. [3]The OCaml manual, “Interfacing C with OCaml”, section on the representation of OCaml data types.
4. [4]Y. Minsky, A. Madhavapeddy, Real World OCaml, 2nd ed., ch. “Memory Representation of Values”, Cambridge University Press (2022).
5. [5]R. A. Eisenberg, S. Peyton Jones, “Levity polymorphism”, PLDI (2017).
6. [6]The Java Language Specification, Java SE 5 edition, §5.1.7 “Boxing conversion” (2005).

last updated 1 October 2026