Project 2: NaN Boxing

Take the measurement ADR-004 promised.

Replace the 16-byte Value enum with an 8-byte NaN-boxed u64 behind a feature flag, keep the test suite green, and find out what halving the value size bought.

Effort: a weekend for the representation, plus however long the last three test failures take. Value: the clearest possible lesson in what unsafe costs and what it buys.

The Technique

IEEE-754 defines a NaN as exponent-all-ones with a nonzero mantissa. That leaves roughly 2^52 bit patterns no arithmetic ever produces — enough for a 3-bit tag and a 48-bit pointer.

   64 bits:
   ┌─┬───────────┬─┬───┬──────────────────────────────────────────────┐
   │S│  exponent │Q│tag│              payload (48 bits)               │
   └─┴───────────┴─┴───┴──────────────────────────────────────────────┘
     1     11      1  3                        48

   A DOUBLE:      any bit pattern that is NOT a quiet NaN → it IS the f64
   NIL:           quiet NaN + tag 001
   FALSE / TRUE:  quiet NaN + tag 010 / 011
   INTEGER:       quiet NaN + tag 100 + 48-bit... ← PROBLEM. See below.
   HEAP HANDLE:   quiet NaN + tag 101 + 32-bit index + 16-bit generation

Ember has a problem LuaJIT does not, and finding it is the first real lesson: Ember has 64-bit integers (ADR-005), and 64 bits do not fit in a 48-bit payload. Three ways out:

There is no free answer, and discovering that is worth more than the benchmark. LuaJIT can NaN-box cleanly because Lua 5.1 has no integer subtype; Lua 5.4 does, and LuaJIT never adopted 5.4 for several reasons of which this is one.

What You Build

#![allow(unused)]
fn main() {
#[derive(Copy, Clone)]
pub struct Value(u64);

impl Value {
    #[inline] pub fn is_float(self) -> bool { (self.0 & QNAN) != QNAN }
    #[inline] pub fn as_float(self) -> f64 { f64::from_bits(self.0) }

    /// # Safety
    /// The caller must have checked the tag. Every accessor is preceded by a
    /// tag test in the ONE place that dispatches — see `Value::kind()`.
    #[inline] pub unsafe fn as_handle_unchecked(self) -> Handle { /* ... */ }
}
}

The critical design decision: keep a safe kind() that returns an enum, and make every callsite match on it. That preserves the exhaustiveness checking that ADR-004 chose the enum for — the compiler still tells you when you forget a variant — while the representation is packed.

#![allow(unused)]
fn main() {
pub fn kind(self) -> ValueKind { /* safe: one match on the tag bits */ }
}

Without that, you have traded a compile-time guarantee for eight bytes, and the trade is bad.

The Measurement

fib_25 and tables are where the win should be, because both move Values in bulk — the VM's stack and a table's array part. loop_10m may barely move: the arithmetic was already fast, and the tag test is now bit-twiddling instead of a discriminant load.

Report the unsafe line count next to the speedup. That column is the actual finding.

Where It Gets Hard

1. The integer problem above. Solve it before writing anything else.
2. Pointer width assumptions. 48-bit user-space addresses are true on current x86-64 and aarch64 and are not guaranteed — 5-level paging allows 57-bit addresses on x86-64. Ember's handles are an index plus a generation, not a pointer, which sidesteps this entirely and is a real advantage of the handle design nobody planned for.
3. -0.0 and NaN literals. A script producing a genuine NaN must not be mistaken for a tagged value. Canonicalize on construction, and test with 0/0, -(0/0), and every NaN payload you can construct.
4. Debugging. {:?} on a u64 tells you nothing. Write a Debug impl first, before you need it.

Deliverables

• Value as a NaN-boxed u64 behind a nan-boxing feature; the enum remains the default.
• A safe kind() preserving exhaustive matching at every callsite.
• The integer problem solved, with an ADR explaining which of A/B/C you chose and what it cost.
• Every unsafe block with the five-part treatment.
• The whole test suite green under both features; differential tests green.
• --gc-stress green under both.
• The measurement table, including the unsafe line count.
• ADR-016, superseding or confirming ADR-004. Confirming is a fine outcome.

Where to Read

git clone https://luajit.org/git/luajit.git && cd luajit
rg -n 'LJ_TISNUM|itype|tvisnum|setgcV' src/lj_obj.h

• LuaJIT's lj_obj.h — the canonical NaN-boxing implementation, with a long comment explaining the bit layout. The primary source.
• JavaScriptCore's JSValue.h — a different scheme (offset doubles) with different tradeoffs; worth comparing.
• SpiderMonkey's Value.h — a third, with separate 32-bit and 64-bit layouts.
• Piotr Kołaczkowski / Nikita Popov's writeups on NaN boxing, for accessible explanations of the bit math.

Validation / Self-check

1. Why does IEEE-754 leave room for a tag? How much room, exactly?
2. Why does Ember have a problem LuaJIT does not? Give the three ways out and their costs.
3. Why keep a safe kind()? What would you lose without it?
4. Why do Ember's handles sidestep the 48-bit pointer assumption?
5. Which benchmarks should improve most, and why?
6. Report your speedup and your unsafe line count. Which number would you lead with?
7. Would you ship it? Defend the answer with the table.

Next: Project 3 — Incremental GC.