How OCaml Represents Values in Memory

Subject Matter

• OCaml's type system distinguishes between "immediate" types and "boxed" types, a distinction critical for memory layout and garbage collection efficiency.
• Immediate types (e.g., unit, bool, char, int) are represented directly as 63-bit tagged integers.
• Boxed types (e.g., arrays, tuples, records) require heap allocation and are represented as pointers to blocks containing a header and payload.

Immediate Type Representations

• unit is represented as integer 0.
• false is represented as integer 0.
• true is represented as integer 1.
• char values are encoded as their ASCII byte values.
• int values are stored as themselves, offset to accommodate the tagging scheme.

Garbage Collection Mechanics

• Tagged Integers: All heap-allocated blocks are 8-byte word-aligned, ensuring the lower three bits are always 0.
• The garbage collector uses the least significant bit (LSB) to distinguish types:
  • LSB 1 indicates a tagged integer.
  • LSB 0 indicates a pointer to a heap block.
• This tagging scheme reduces integer precision to 63 bits but simplifies runtime type checks.
• Block Headers: Every allocated block includes a 1-word header preceding the data.
  • The header contains a 54-bit size field (capable of addressing ~16 petabytes).
  • The header contains 2 bits used internally by the garbage collector for marking/coloring.
  • The header contains a 1-byte tag used to identify specific block types and behavior.

Special Boxed Types and Tags

• Floats (Double):
  • 64-bit IEEE doubles cannot use LSB tagging; thus, they are boxed as one-word blocks.
  • Blocks containing floats use tag 253 (the "double tag").
  • The garbage collector recognizes tags $\ge$ 251 as non-scannable to avoid dereferencing internal data as pointers.
• Strings:
  • Strings are tightly packed byte arrays where arbitrary words might not satisfy alignment or tagging rules.
  • String blocks use tag 252.
  • The GC treats any tag $\ge$ 251 as containing no scannable pointer data.

Variant Type Encoding

• Variant constructors are divided into two families: immediate (no payload) and non-immediate (with payload).
• Immediate Constructors (e.g., A, C):
  • Represented directly as integers based on their definition order.
  • Example: A is 0, C is 1.
• Non-Immediate Constructors (e.g., B, D):
  • Represented as boxed blocks where the constructor identifier is stored in the block's tag field.
  • Tags start from 0 for the first non-immediate constructor defined.
  • There is a maximum limit of approximately 250 non-immediate constructors per variant due to the single-byte tag constraint.

Runtime Capabilities and Future Work

• The runtime can dynamically inspect any value to determine if it is an integer or a pointer and, if the latter, retrieve the exact heap block size via the header.
• The current implementation ensures a simple runtime and efficient garbage collection by strictly defining memory layouts.
• Forward-looking statement: Future development will focus on integrating traditional value types with "unboxed" types to further optimize performance.