Shrinking Footprint with Narrow Handles and Inline Storage

Every pointer in a data structure costs eight bytes on a 64-bit platform, and the values they hold rarely need that range. A tree of ten million nodes needs 24 bits of index; its pointers are spending five bytes each on nothing. The same is true of lengths, flags, and small integers that occupy a full machine word for convenience. These words are not free: they occupy cache lines that the traversal must fetch, and they are the single most common reason a structure that “should” fit in cache does not.

Narrowing those representations is the most reliable way to reduce the bytes moved per element, because it does not depend on the hardware at all. It buys space and bandwidth linearly in the width reduction, and it costs indirection, encoding work, and often a relocation constraint. The engineering question is where on that axis a given structure should sit.

The linear case for narrower words

Consider a node with a 4-byte key, an 8-byte pointer to a left child, an 8-byte pointer to a right child, and a 1-byte flag. With alignment the node occupies 32 bytes: 4 key, 4 padding, 8, 8, 1, 7 padding. Two nodes per cache line, of which 24 of the 64 bytes transferred are padding.

If the children are stored as 4-byte indices into a node array, the node becomes 4 key, 4 left, 4 right, 1 flag, 3 padding, totalling 16 bytes. Four nodes per line instead of two, and the effective bandwidth per node halves. The key observation is that this is not a micro-optimisation: it changes the number of cache lines a fixed traversal must wait for, and that number is the throughput of a memory-bound traversal.

Index handles have three further consequences worth stating. They allow an array of nodes to be reallocated as a unit without updating every reference, since indices are offsets rather than addresses. They permit the node array to be serialised to disk or the network directly, because indices are location-independent. And they bound the structure: an index of width w bits limits the node count to 2^w, which for 4 bytes is four billion nodes, well beyond what a single process can hold at any plausible node size.

The price is a base address that must be known at every access: an index is meaningless without the array it indexes. That base pointer is typically stored once per container, or passed as a parameter, which is cheap; it becomes expensive only when the structure is passed across interfaces that expect self-contained nodes.

Compressed pointers and the heap-alignment trick

Index handles assume the structure has a single backing array. Where the structure must use real pointers, as in a general-purpose runtime whose objects are individually allocated, the equivalent saving comes from an observation about heap layout: if all objects are allocated within a contiguous reservation, a pointer is determined by its offset from the reservation base. Storing that offset in 4 bytes instead of 8 halves every reference field.

V8 uses exactly this scheme for JavaScript heaps: objects live inside a reserved cage, and reference fields hold 32-bit offsets from the cage base. The saving is a halving of the bytes in every object that contains references, which is most of them. The cost is the cage itself, a large reservation of virtual address space, and the constraint that no object may be outside it. Since virtual address space on 64-bit systems is abundant while resident memory is not, the trade is favourable for runtimes that control their own allocation.

The scheme generalises to other object graphs with one extra condition: any pointer that can refer to something outside the cage needs a full-width escape, or the design must guarantee no such pointer exists. Runtimes that allow foreign pointers must add an out-of-line representation for them, which complicates the access path on exactly the rare case that must be correct.

Small-object storage inside the object

The other half of footprint reduction addresses the common case where a container holds a short string, a short vector, or a small number of elements. Allocating a separate block for it costs an allocation call, a header, and a pointer to follow, and it places the contents in a different cache line from the container. Inline storage avoids all three by keeping small contents in the container itself.

The classic form is a union of an inline buffer and a pointer to a heap buffer, with a discriminant bit that says which is live. A string type with a 16-byte inline capacity stores short strings with no allocation at all, and long strings with one allocation, in the same 24- or 32-byte object. The discriminant can be hidden in the pointer itself, since heap pointers are at least 8-byte aligned and the low bits are therefore free; using an odd length as the in-heap marker is the classic variant that needs no extra byte.

There are real costs. The inline path must enforce the capacity and fall back to reallocation, which adds a branch to operations that were previously unconditional. Moving an inline container moves its contents, whereas moving a pointer-holding container does not, so an object that is inlined cannot be copied cheaply unless the copy is trivial. And the inline capacity must be chosen against the distribution of sizes; a capacity that is too small causes most strings to allocate anyway, while one that is too large wastes space in every container that holds a long string.

The variant used by databases is a prefix plus an out-of-line suffix. A page slot or tuple header stores a short prefix inline in the page’s index area, so that comparisons against search keys can be resolved without following a pointer into the tuple, and only the mismatch case needs the full value. PostgreSQL’s page format follows this shape: an item pointer array at the front of the page and tuple data at the back, growing toward each other, with a bounded amount of metadata per item.

The inline form in C is a union of the buffer and the pointer, with the length deciding which member is live:

#include <stddef.h>

#define INLINE_CAP 15          /* one byte of the 16 is the terminator */

struct str {
    size_t len;                /* discriminates the two forms */
    union {
        char *p;               /* heap form: len > INLINE_CAP */
        char  buf[16];         /* inline form: len <= INLINE_CAP */
    } u;
};                             /* 24 bytes total, no separate allocation */

const char *str_data(const struct str *s)
{
    return s->len <= INLINE_CAP ? s->u.buf : s->u.p;
}

Every access pays one comparison to pick the form, and the struct is 24 bytes rather than the 16 a pointer-and-length pair would need. Two thirds of the struct is the inline buffer, which is wasted on every string that turns out to be longer than a few characters, which is the trade in its purest form.

Choosing widths systematically

The choice of width for each field should follow the distribution of values, and the distribution is usually far more concentrated than a machine word suggests. Three rules cover most cases.

Use the smallest width that provably covers the field’s domain. A node index in a structure capped at 2^32 nodes fits in 4 bytes by definition, and the cap is a design decision rather than a discovery. A byte offset within a 64 KiB page fits in 2 bytes. Applying this rule to a structure’s fields usually reveals one or two fields that were sized for convenience.

Pack boolean flags into a single word. Eight or more flags that each occupy a byte, with alignment padding around them, collapse into one 4-byte field with bit operations. The shift and mask are free on any modern core, and the line savings are not.

Separate hot from cold fields, and narrow the hot ones. This is where width reduction composes with layout splitting. The hot subset of a node is usually a key and a couple of links; the cold subset is statistics, timestamps, and names. Narrowing the hot subset is what reduces the bytes per step of the traversal, and the cold subset can stay wide without cost, provided it is out of line. The mechanism is the same trade described in Bytes Fetched per Field, applied to node fields rather than to whole records.

Trading width for decode work

Every narrowed field costs something to use. A 32-bit handle accessed from a 64-bit register needs a zero-extension, which is typically free; a 24-bit or 40-bit field needs a shift and a mask, which is one or two extra instructions. A bit-packed structure needs extraction for every field access.

The instruction cost is usually irrelevant: a traversal that waits hundreds of cycles for a cache miss can absorb dozens of extra arithmetic operations without changing throughput. The exception is a structure that already fits in the first cache level, where the traversal is limited by execution rather than by memory, and where the extra instructions become the bottleneck. Applying width reduction to an L1-resident structure is a common mistake: it makes the code slower by adding work and removes no misses.

The right diagnostic before narrowing is therefore the same one that governs every other locality change: establish whether the structure’s working set crosses a cache boundary. That measurement, described in Working Set Size and the Miss-Rate Cliff, decides whether the width is on the critical path at all.

Reconstruction cost and error bounds

A narrower representation can also store less than the exact value, in which case the reader must reconstruct it. Sorted-key indexes offer the cleanest example: if keys are sorted and evenly spaced, the position of a key can be predicted from a linear function of the key, and the exact position found by a short local search. Storing the parameters of the function costs a constant number of bytes per block instead of the keys themselves, and the search cost is logarithmic in the error bound rather than in the block size.

The technique is only sound when the error bound is explicitly maintained and checked. A learned function that is wrong by more than the search window gives wrong results, so implementations carry the maximum error and fall back to a conventional structure when a block’s distribution is too irregular. The guarantee, not the compression, is the hard part: a representation that is usually right and occasionally wrong is not usable for an index.

A similar pattern appears in narrower numerical formats. Storing a value in half precision halves its width and introduces a relative error set by the format’s mantissa bits, which is acceptable when the value feeds a subsequent computation with its own tolerance and unacceptable when it feeds an exact comparison. The decision rule is the same: reconstruct exactly, or carry a bound.

Where footprint reduction stops paying

Width reduction changes bytes per element, not bytes per access. A traversal that reads one element at a time in random order still issues one miss per element, and halving the element size does not halve the miss count: it halves the number of elements per line, which helps only if the traversal uses the neighbouring elements. For a random-access workload over a structure larger than the last-level cache, narrowing the nodes reduces the total footprint and therefore the fraction of it that fits, which can cross a cache boundary and produce a genuine step change; but if the footprint remains far above capacity, the accesses stay compulsory misses and the benefit collapses to the bandwidth saving on the fetched lines, which is real but bounded by the unused remainder.

The technique that does reduce the number of misses is shortening the dependency chain, discussed in Dependent Loads and the Cost of Pointer Chasing, and the two compose naturally: a node that fits in fewer bytes also allows a wider fanout in the same number of cache lines, so a narrower node supports a shallower tree. That combination, narrower fields plus higher fanout plus fewer dependent loads, is where a memory-bound index structure gets its performance, and no single one of the three produces it alone.