Home › Compilers & runtimes › Interpreters & JITs
algorithm low

Value tagging and NaN-boxing

Problem A dynamically typed runtime must hold an int, a float, a boolean or an object reference in the same variable. Storing a type tag next to every value doubles memory traffic and allocating every number is slow.

Pack the type and the payload of any value into one 64-bit word, using spare low bits of aligned pointers or the unused payload of NaNs, so type tests are one mask compare.

O(1) per type test, encode and decode; 8 bytes per value
dynamic-typingvalue-representationruntimememory-layoutnan-boxing
Overview

A dynamic language lets one variable hold anything. The naive layout is a 16-byte tagged union (tag plus padded payload) or a heap box per number. Both waste memory and cache lines. The trick: a 64-bit word has spare bits. Aligned pointers have zero low bits, and a double has about 2^51 NaN bit patterns that hardware never produces on purpose. Put the type there.

Key facts

Use when

  • Interpreters and JITs (bytecode interpreter, JIT compilation) in browsers, embedded scripting (Duktape, mruby, QuickJS) and functional-language runtimes (OCaml): the value fits a register and a stack slot.
  • Any dynamic value cell (JSON-like, config) where most values are numbers or small ints and memory per cell matters.

Avoid when

  • You need full 64-bit integers or pointers beyond 48 bits: use a tagged union or tag the low bits.

Deep dive

How it works

In: a bool, i32, f64, nil or object reference · Out: one u64 and its inverse accessors · State: none (the heap holds the objects) · Cost: O(1), one mask compare per type test, 8 bytes per value.

Two schemes, often combined:

  1. Low-bit tagging. Objects are 8-byte aligned, so the low 3 bits of a pointer are zero. Use bit 0 to mark an immediate: OCaml stores an int shifted left by one with the lowest bit set to 1 (Real World OCaml), losing one bit of precision. V8 uses the least significant bit to separate Smis from heap pointers; on 64-bit builds without compression a Smi carries a 32-bit payload (v8.dev).
  2. NaN-boxing. An IEEE double is NaN when the 11 exponent bits are all ones and the mantissa is nonzero. Leave every ordinary double unchanged and spend NaN patterns on everything else: top 13 bits all ones (sign, exponent, quiet bit), a tag in the next bits, a 48-bit payload (int, pointer index, flag).
  3. Type test. bits & 0xFFFF<<48 == TAG; a double is bits & 0xFFF8<<48 != 0xFFF8<<48.
  4. Canonicalise. Arithmetic can yield a NaN with any payload; x86 SSE yields 0xFFF8000000000000, which collides with a boxed tag. Every double entering a Value that is NaN is replaced by one fixed positive NaN outside the boxed space.

Engines differ in detail. Only what the sources state:

  • LuaJIT (64-bit, LJ_GC64): upper 13 bits 1, next 4 bits the type tag, lowest 47 bits a pointer or a zero-extended 32-bit int; lightuserdata is segmented to fit 47 bits (lj_obj.h).
  • JavaScriptCore: pointers have the top 16 bits zero; int32 are tagged 0xFFFE; doubles are offset by 2^49 so no encoded double begins with 0x0000 or 0xFFFE (JSCJSValue.h). Pointers need no masking, doubles pay one add.
  • mruby (MRB_NAN_BOXING): doubles stored with a constant offset so pointers have zero top 32 bits; int fixed at 32 bits (boxing_nan.h).

Pointer compression (V8): objects live in a 4 GB cage, tagged fields hold 32-bit offsets from a base register. The V8 team reports up to 43% smaller V8 heap and up to 20% smaller Chrome renderer memory on desktop in their browsing tests (v8.dev). Both Smis and pointers must then fit 32 bits, so tagging stays.

Code

// Layout: any u64 whose top 13 bits are NOT all ones is an f64 as-is.
// Top 13 bits all ones (0xFFF8..) = quiet NaN space; bits 48..50 carry a tag.
const BOXED: u64 = 0xFFF8 << 48; // sign + exponent + quiet bit
const MASK: u64 = 0xFFFF << 48; // tag field plus the 13 NaN bits
const T_INT: u64 = 0xFFF9 << 48;
const T_BOOL: u64 = 0xFFFA << 48;
const T_NIL: u64 = 0xFFFB << 48;
const T_PTR: u64 = 0xFFFC << 48;
const PAYLOAD: u64 = (1 << 48) - 1;
const CANON_NAN: u64 = 0x7FF8_0000_0000_0000; // positive qNaN: not in boxed space

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Value(u64);

impl Value {
    pub fn from_f64(x: f64) -> Value {
        // Hardware NaNs may carry any sign/payload (x86 makes 0xFFF8..): canonicalise.
        Value(if x.is_nan() { CANON_NAN } else { x.to_bits() })
    }
    pub fn from_i32(i: i32) -> Value { Value(T_INT | i as u32 as u64) }
    pub fn from_bool(b: bool) -> Value { Value(T_BOOL | b as u64) }
    pub fn nil() -> Value { Value(T_NIL) }
    /// `idx` is a heap index or address; must fit 48 bits.
    pub fn from_ptr(idx: u64) -> Value {
        assert!(idx <= PAYLOAD);
        Value(T_PTR | idx)
    }
    pub fn is_f64(self) -> bool { self.0 & BOXED != BOXED }
    pub fn is_i32(self) -> bool { self.0 & MASK == T_INT }
    pub fn is_bool(self) -> bool { self.0 & MASK == T_BOOL }
    pub fn is_nil(self) -> bool { self.0 & MASK == T_NIL }
    pub fn is_ptr(self) -> bool { self.0 & MASK == T_PTR }
    pub fn as_f64(self) -> Option<f64> { self.is_f64().then(|| f64::from_bits(self.0)) }
    pub fn as_i32(self) -> Option<i32> { self.is_i32().then(|| self.0 as u32 as i32) }
    pub fn as_bool(self) -> Option<bool> { self.is_bool().then(|| self.0 & 1 != 0) }
    pub fn as_ptr(self) -> Option<u64> { self.is_ptr().then(|| self.0 & PAYLOAD) }
}

#[allow(dead_code)]
enum Tagged { F64(f64), I32(i32), Bool(bool), Nil, Ptr(u64) }

fn main() {
    use std::mem::size_of;
    assert_eq!(size_of::<Value>(), 8);
    assert_eq!(size_of::<Tagged>(), 16);
    for f in [0.0, -0.0, 1.5, -1e300, f64::INFINITY, f64::NEG_INFINITY, f64::MIN_POSITIVE] {
        let v = Value::from_f64(f);
        assert_eq!(v.as_f64().unwrap().to_bits(), f.to_bits());
        assert!(!v.is_i32() && !v.is_ptr() && !v.is_bool() && !v.is_nil());
    }
    for i in [0, 1, -1, i32::MIN, i32::MAX] {
        let v = Value::from_i32(i);
        assert_eq!(v.as_i32(), Some(i));
        assert!(v.as_f64().is_none() && !v.is_ptr());
    }
    assert_eq!(Value::from_bool(true).as_bool(), Some(true));
    assert_eq!(Value::from_bool(false).as_bool(), Some(false));
    assert!(Value::nil().is_nil() && Value::nil().as_f64().is_none());
    for p in [0, 1, 0x7FFF_FFFF_FFF0, PAYLOAD] {
        assert_eq!(Value::from_ptr(p).as_ptr(), Some(p));
    }
    // A real NaN from arithmetic (0/0 gives 0xFFF8.. on x86, 0x7FF8.. on ARM)
    let zero = std::hint::black_box(0.0f64);
    let nan = zero / zero;
    println!("raw NaN bits {:016x}", nan.to_bits());
    let v = Value::from_f64(nan);
    assert!(v.is_f64() && !v.is_i32() && !v.is_ptr() && !v.is_nil() && !v.is_bool());
    assert!(v.as_f64().unwrap().is_nan());
    // Even the worst case: a NaN that looks exactly like a boxed int
    let evil = f64::from_bits(T_INT | 7);
    assert!(evil.is_nan());
    assert!(Value::from_f64(evil).as_i32().is_none());
    println!("ok");
}

Complexity and constants

Encode, decode and test are 1-3 ALU ops, no memory access, no branch if the compiler fuses the compare. A tagged union is 16 bytes (the test above asserts size_of is 8 vs 16): twice the bytes per array element, stack slot and cache line. An int add: test two tags, add 32-bit, retag. The 32-bit int range is a hard limit; larger ints fall to doubles (exact to 2^53).

Efficiency

  • Cost: one value = 8 bytes; type test 1 AND + 1 CMP; decoding a double is free (LuaJIT) or one add/sub (JSC); no allocation for numbers, nil and bools.
  • Levers:
    • One word per value — halves memory traffic vs 16-byte unions (measured above: 8 vs 16) — arrays of values, VM stacks, registers.
    • Immediates instead of boxes — no allocation and no GC pressure for ints and floats (see mark-sweep GC, generational GC) — numeric loops.
    • Match the hot case — free decode for pointers (JSC) or doubles (LuaJIT) — pick by what the workload loads most.
    • Pointer compression — up to 43% less V8 heap (v8.dev) — heaps under 4 GB.
    • Speculation — JITs (JIT compilation) check the tag once, then run untagged loops — hot numeric code.
  • Naive → standard → state of the art: box every number on the heap · alloc per op; 16-byte tagged union · 2x memory, 1 compare; 8-byte tagged word, JIT-speculated, compressed pointers · 1 AND per check, 4-byte fields.

Implementation notes

  • Keep the tag a 16-bit prefix: one compare against an immediate.
  • Make Value Copy and repr(transparent); it passes in a register.
  • Store pointers as heap indexes or offsets rather than raw addresses if the heap is a bounded arena: a 32-bit payload then survives address-space changes.
  • Property access (hidden classes and shapes, inline caches) starts with a tag test on the receiver.

Pitfalls

  • Non-canonical NaNs. Input data (JSON-parsed floats, binary files, 0.0/0.0 on x86) can alias a boxed tag, letting an attacker forge a pointer. Canonicalise at every boundary that creates a double, including loads from typed arrays.
  • 48-bit assumption. x86-64 5-level paging gives 57-bit virtual addresses; Linux only hands out addresses above 47 bits when a mmap hint asks for them (kernel docs), so engines usually stay safe, but a custom allocator or MAP_FIXED can break it. Check addresses at encode time.
  • ARM tag bits. arm64 Linux can run with the top byte ignored for user pointers (tagged address ABI); MTE puts a tag in bits 59:56 of the pointer (MTE docs); pointer authentication stores a code in high-order pointer bits (PAC docs). All collide with a 16-bit tag prefix: strip them before boxing and re-apply after, or keep object references as heap indexes.
  • Integer width. i32 payloads silently wrap; promote to double on overflow.

Variants and alternatives

Tagged union (enum)16 bytes, no tricks, full i64 and pointers; the right default outside hot interpreter paths.
Low-bit tagging onlyno NaN assumptions, 63-bit ints, doubles boxed (OCaml); wins for integer-heavy code.
Pointer compressionhalves pointer fields; a 4 GB heap limit.
Pointer-offset NaN-boxing (JSC, mruby)pointers free to decode, doubles pay an add.

In production

  • Browsers: V8 (Smi tagging, pointer compression) and JavaScriptCore (NaN-boxing).
  • Embedded and application scripting: Duktape documents an 8-byte packed duk_tval vs a typically 16-byte unpacked one (types.rst); mruby has MRB_NAN_BOXING; QuickJS defines JS_NAN_BOXING when pointers are not 64-bit.
  • Functional-language runtimes: OCaml's tagged ints, unit and constant constructors as immediates.
  • Application scripting: LuaJIT as above; embeddable engines are the main users.

Implementations

namelangrepoinstallverdictlicencehealthas_ofnotes
LuaJITCLuaJIT/LuaJITbrew install luajit————NaN-tagged TValue, 47-bit payload
WebKit (JavaScriptCore)C++WebKit/WebKit—————JSValue with double offset
V8C++v8/v8—————Smis, pointer compression
mrubyCmruby/mrubybrew install mruby————optional MRB_NAN_BOXING
QuickJSCbellard/quickjs—————JS_NAN_BOXING on 32-bit
DuktapeCsvaarala/duktape—————packed duk_tval option

Sources

Used by

Systems (2):

jit vmbytecode interpreter

Alternatives and related

Hidden classes (shapes)Runtimes for dynamic languages let programs add properties to objects at any time, so every object could carry its own name-to-value table. That wastes memory and makes property access slow because nothing about layout is shared.Inline cachesInterpreters and JITs for dynamic languages (JavaScript, Python, Ruby) spend much of their time finding where a property or method lives, because objects can change shape at runtime. This makes those lookups nearly as cheap as in static languages.JIT compilationA program is executed from a compact form (bytecode, an AST, a query plan, a regex) that is slow to run but starts at once. Most of it runs rarely, a small part runs constantly, and compiling everything up front costs too much startup time and memory.Mark-sweep garbage collectionA long-running program allocates linked objects and cannot say when each is dead; it must reclaim unreachable memory automatically, including cyclic structures, without the programmer freeing anything.Generational garbage collectionA long-running program allocates huge numbers of short-lived objects next to a few long-lived ones; tracing the whole heap every cycle wastes time on data that has not changed, so reclaiming memory is too slow or pauses too long.
bytecode interpreter · plannedRegister/stack VM dispatch loop for executing compiled plans or rules (SQLite VDBE, nftables)