Value Representation: Tagged Pointers and NaN Boxing

A dynamically typed language cannot decide at compile time whether a variable holds an integer, a double, a string, or a closure. The runtime therefore needs a uniform representation: one machine word that can hold any value and can be inspected at run time to determine which kind it is. The choice of encoding determines the cost of every arithmetic operation, the memory footprint of every array, and whether the language can be ported to architectures with unusual pointer rules.

The naive encoding and its cost

The simplest encoding is a struct with a tag and a union:

typedef enum { VAL_INT, VAL_DOUBLE, VAL_OBJ } Kind;

typedef struct {
    Kind kind;
    union { long i; double d; Obj *o; } as;
} Value;

This is correct, portable, and 16 bytes wide on a 64-bit machine because the union’s alignment is 8 and the tag adds 4 with padding. An array of a million such values occupies 16 MB. Every arithmetic operation loads the tag, compares it against the expected kinds, and then loads the payload, which is two dependent loads instead of one. On a modern core the second load usually hits the same cache line as the first, so the tag read is cheap in isolation; the real cost is that the extra 8 bytes per value halve the number of values per cache line, so a scan over a numeric array touches twice as many lines as the payload alone would require.

The two ways out are to put the tag inside the word (tagged pointers) or to find a range of bit patterns in one interpretation that can never occur (NaN boxing).

Low-bit tagging

Alignment gives away free bits. A heap object’s address is a multiple of its alignment, so the low two or three bits of a pointer are always zero. Storing a small integer tag there costs nothing: the runtime writes (uintptr_t)obj | 1 for a heap object, and a fixnum is stored shifted left by one so that its low bit is zero. Testing the low bit distinguishes the two.

#define TAG_MASK 1u
#define IS_OBJ(v)  (((v) & TAG_MASK) == TAG_MASK)
#define AS_OBJ(v)  ((Obj *)((uintptr_t)(v) & ~(uintptr_t)TAG_MASK))
#define FIXNUM(n)  ((Value)(((uintptr_t)(n)) << 1))
#define AS_FIXNUM(v) ((long)((uintptr_t)(v) >> 1))

Small integers then have to be encoded so they are distinguishable from pointers, which the macros above do by shifting. The arithmetic consequence is that a fixnum add is a plain add on the shifted representation, since (a<<1) + (b<<1) equals (a+b)<<1, but a fixnum multiply must drop one operand’s shift first, because the product carries an extra factor of two from each operand and would otherwise come out shifted by two instead of one.

The number of bits available for the integer is the word size minus the tag width. On a 64-bit machine with a one-bit tag that is 63 bits, so the fixnum range is well beyond what most programs need, and overflow falls back to a heap-allocated bignum or to a double. On a 32-bit machine the same scheme gives a signed 31-bit range, and a boundary at roughly a billion is close enough to real programs that the overflow path is exercised.

NaN boxing

IEEE 754 doubles have a useful quirk. A 64-bit double has 11 exponent bits and 52 fraction bits, and the encoding for NaN is any exponent of all ones with a nonzero fraction. The hardware only requires one particular NaN to be produced by invalid operations, but the standard permits the payload to carry other information, and the 52-bit payload admits 2^52 - 1 distinct nonzero patterns. A runtime can claim a subset of those patterns for its own tags and store a pointer or an integer in the payload.

The common layout is:

sign exponent (11)   fraction (52)
 0   11111111111     quiet NaN, payload == 0        -> a real double NaN
 1   11111111111     quiet NaN, payload != 0        -> tag in high payload bits + payload
 anything else                                     -> an ordinary double

A runtime using this scheme stores doubles as their raw 64-bit pattern and stores every other value with the sign bit set, the exponent all ones, and the payload split into a small tag and the actual data. Testing “is this a double” is then a comparison of the high 16 bits against a mask, which is one compare on a value already in a register.

The scheme’s advantage is that a Value is exactly 8 bytes and a double needs no heap allocation and no conversion. The disadvantage is that the tag field is 16 bits, so a pointer must fit in the low 48 bits. That is true on current x86-64 and AArch64 implementations with 48-bit virtual addresses, and it is why the technique is popular in JavaScript engines on those platforms and awkward on systems with wider or non-canonical addressing. It is also why the technique interacts badly with pointer compression schemes, which deliberately place objects in a reserved region and store 32-bit offsets rather than full addresses.

A second disadvantage is that the scheme is not portable in the strict sense: it depends on the platform’s NaN behavior. An architecture that canonicalizes NaN payloads on load or store would destroy the tag bits, and a compiler that constant-folds a double NaN could turn a tagged value into a canonical NaN. Implementations that use NaN boxing guard against the second by keeping the tag manipulation in integer code and never letting the value participate in floating-point arithmetic until it has been checked.

What the representation forces on the collector

The representation and the garbage collector are coupled. A precise collector needs to know, for every slot it scans, whether the word is a pointer. With a tag-and-union layout the tag says so directly. With low-bit tagging, the low bit says so, but the collector must also know that a non-pointer word might be a double whose bit pattern happens to look like a pointer. A conservative collector handles this by treating any word that falls inside the heap as a potential pointer, which is the policy of the Boehm-Demers-Weiser collector; the cost is retention of objects that are actually unreachable but whose addresses appear in stale or numeric data.

A precise collector for a tagged representation can be fully accurate: it inspects the tag and follows only real pointers. For NaN boxing the collector’s test is “is this word a non-double tagged value with an object tag”, which is a mask and compare. The subtlety is that the collector must not be confused by a double whose bit pattern happens to satisfy that test. Because every such pattern is a NaN and every tag pattern is a NaN, the only way to confuse them is for user code to construct a NaN with a payload that matches a tag, which a language that only creates NaNs through arithmetic cannot normally do.

Boxing also determines whether integers can be unboxed in arrays. A Value-typed array holds 8 or 16 bytes per element. A specialized array of machine integers holds 4 or 8, and a specialized array of doubles holds 8 with no tag at all. The optimization is what makes numeric code in dynamic languages approach compiled speed, and it requires the runtime to track element kinds per array so that a write of a different kind triggers a transition to a general array. The mechanism for tracking those transitions is the same machinery that hidden classes provide for object shapes.

Integers that do not fit

Both encodings have a boundary. A fixnum add that overflows must produce either a double or a bignum, and the choice is a language design decision rather than an implementation detail. Scheme’s numeric tower requires exact integers of unbounded size, so overflow allocates a bignum and the arithmetic path becomes a call. JavaScript’s numbers are doubles, so an integer beyond 2^53 loses precision silently; the language later added a separate big-integer type for code that needs exactness. Python’s integers are arbitrary precision, and CPython’s implementation stores small integers in a cache of preallocated objects, so a value in the small range costs no allocation at all while arithmetic still goes through the general object protocol.

The cost of a general integer path shows up in the fast path’s guards. An add must check that both operands are fixnums, that the result does not overflow, and only then store the sum. Each check is a compare and a branch, and the branch is predictable when the program is numeric and unpredictable when it is not. This is precisely the check that a just-in-time compiler hoists out of the loop: it speculates on the observed kinds, generates an unchecked add, and falls back to the general path when the speculation fails.

Choosing between them

	Tag plus union	Low-bit tagging	NaN boxing
Bytes per value	16 on 64-bit	8	8
Double cost	load tag, then payload	boxed or separate	none
Integer width	full word	word minus tag bits	payload width
Portability	any C target	needs aligned pointers	needs 48-bit pointers and preserved NaN payloads
Collector test	read the tag	test the low bit	mask and compare

Low-bit tagging is simpler to port, works on any architecture with aligned pointers, and leaves the full double range untouched. It costs a shift on some integer operations and, if the tag is one bit, a heap allocation for any value that is not a small integer or a pointer. NaN boxing costs the assumption that pointers fit in 48 bits, which is true today on the mainstream 64-bit targets and not guaranteed by any language standard, and it costs a mask and compare wherever a value’s kind must be decided at run time; the double path itself needs no check, since a double is stored raw. In exchange it makes every value 8 bytes and every double free of allocation.

The choice also interacts with calling conventions. A runtime that passes values in registers wants them to fit one register; both schemes do. A runtime that spills values to the stack wants the spill slot to be one word; NaN boxing guarantees it, tagging guarantees it, and the struct layout does not. For a language whose numeric code matters, the 8-byte guarantee is worth more than the portability of the struct, which is why the engines that compete on numeric throughput have converged on the narrower encodings.