Compact Representations

## The same value, two internal layouts Many in-memory stores hold a value the caller thinks of as one thing — a small map of fields, a short list, a small set of numbers — in one of two internal layouts, and choose between them without telling anyone. The **compact representation** puts the elements into one contiguous run of bytes behind a small header, with just enough length information to walk from one to the next. There is no slot, no pointer and no separately allocated node per element: the elements are the storage. The **general representation** gives every element its own place in a lookup structure, so the store reaches one element without walking the rest. That costs a slot per element, the structure's own bookkeeping, and usually a separate allocation each. When the elements are small, this per-element machinery is not a rounding error: on some stores and some value shapes it costs more than the elements themselves. That is why the compact layout exists — for a value with a handful of short elements, packing removes most of what it would otherwise cost. ## What moves a value across the line The store abandons the compact layout when the value gets big enough that walking it stops being cheap. "Big enough" is not one number, and it is not one axis: - **element count** — the value gains its n-th element; - **the size of one element** — a single field grows from a short string to a long one, and one long element is enough on its own, however few there are; - **sometimes the element type** — some stores pack only elements of a particular kind, for instance small whole numbers, and switch the moment anything else is added. Each axis has its own threshold, each is a value the store chooses and often lets an operator move, and they differ between stores and between value shapes. What transfers is that the thresholds exist and which axes they sit on; the numbers do not. ## Why memory steps instead of climbing The crossing is not incremental. The store rebuilds the whole value in the other layout in one move, so the memory attributed to that entry changes at once. | | compact representation | general representation | |---|---|---| | stored per element | the bytes, plus length information | the bytes, plus a slot, bookkeeping and usually its own allocation | | finding one element | walk from the start | reach it directly | | changing one element | may rewrite part of the run | touches that element | | memory as elements are added | roughly the bytes added | the bytes added plus a fixed cost each time | Add one element to a value sitting just under a threshold, across a million such entries, and the memory they occupy multiplies. How large the multiple is depends on the store and on how small the elements were — the smaller they are, the bigger the jump, because the fixed per-element cost dominates. Nothing in the workload looks different: the same call, one more field. Monitoring shows a step, not a slope, and an alert tuned for gradual growth does not see it coming. ## Nothing in application code changes The layout is a private decision of the store: the same operations, the same results, and no error or type change to mark the crossing. That is the point of the scheme and also its hazard — there is no line in the application where anyone could have noticed. In most stores that do this, the crossing is also effectively one-way. Checking on every removal whether the value could go back to the packed layout would put work on the hot path for a rare benefit, and values hovering at the boundary would rebuild repeatedly, so the value keeps the general layout until it is written again from scratch. ## The trade, in both directions The compact layout is scanned, not indexed: reaching one element means walking from the start, so the cost of touching an element grows with the element count. For a handful that walk is short, and the contiguity can make it as fast in practice as a lookup; for thousands it is not close. The threshold sits near where the footprint saving stops paying for the access cost. Neither layout is simply better — the compact one is a win only while the value is small. ## Where stores differ - Some apply the scheme across several value shapes, aggressively. - Some apply it to one shape only. - Some hold values as opaque bytes the server never interprets, so there is nothing to pack and no second representation at all; those stores attack footprint elsewhere, for instance with fixed-size blocks. - Where the scheme exists, the axes and the thresholds are the store's own. So "small collections are packed and promoted past a threshold" is a true statement about a family of stores, not about this class of store. Say which behaviour you are assuming before you plan around it. ## What to do with this 1. Do not extrapolate a footprint from one measured size; measure across the range of sizes the workload will really produce. 2. Expect the number to move in steps, at boundaries you did not choose. 3. When memory jumps after a harmless-looking change, ask what grew — an element count, one element's size, or the type of what was added — before reaching for the allocator.