Skip to main content

One map or two: where the row lives

· 5 min read

A keyed store can keep a row and its identity together — one Map<key, slot>, the row on the slot — or apart: a Map<key, row> for the data and a second Map<key, slot> whose identities are minted only when something needs one. Apart is the cheaper first load. It is dearer on every write once anything is watching, and dearer by 3.5× when a subscription asks for an identity.

Context​

Every row in OIMDB has an identity — the slot — and the slot carries the bookkeeping a reactive store needs: the subscriber list, the revision it last changed at, the hold count, the emptiness flag. Thirteen fields.

A row also has data. The question is whether the two live in one place.

Problem​

Keeping them together means a first load mints a slot per row, and a slot is an object. A population of ten thousand rows is ten thousand slots nobody has subscribed to yet, and most of them nobody ever will.

So the proposal: keep the rows in their own map and mint identities lazily. The first load then writes one map entry per row and allocates nothing.

Options​

One map. slots.get(key) resolves the row and its subscriber list in one hash, because they are the same object. A write already holds everything it needs to decide whether anybody must be told.

Two maps. rows.set(key, row) stores the data. But a write still has to answer "does anybody watch this key?", and nothing but the identity map can answer it — so once that map is non-empty, every write pays a second hash. The early return on an empty identity map is available exactly once in a store's life: before the first subscription.

The numbers​

Four rows, one per axis, both arms hand-written so only the map arrangement differs. 8192 rows per pass, 15 samples, two independent processes per arm — both readings are printed because the second has as much claim on the quotient as the first.

axisone maptwo mapscheaper
first load, nobody subscribed84 / 76 ns54 / 56 nstwo maps, by ~25 ns/row
read the row by key31 / 35 ns30 / 28 nsa tie
overwrite, one subscriber standing34 / 30 ns38 / 48 nsone map
subscription: key → identity29 / 33 ns113 / 104 nsone map, by ~3.5×

THE SPREAD ON THIS RUN IS LARGE AND THE READER SHOULD KNOW IT. Inside a process the samples spread 44% to 490%; between its two processes each arm disagreed with itself by 3.7% to 27.3%. The harness marks all four rows void for exactly that reason, and its own rule is that a voided ratio decides nothing. The figures above are printed as what was observed, not as settled margins: read the first and the fourth row as directional, and the second and third as too close to separate on this run. A quieter machine would narrow them; it would not move the operation counts below, which is why the decision rests on those.

What the operation counts say, machine or no machine​

axisone maptwo maps
first loadget (miss) + mint 13 fields + setone set
read by keyget + one property loadget
overwrite with a subscriberget + field writes + read effectsset + get + field writes + read effects
subscriptiongetget (miss) + mint + set + get into the row map

The asymmetry is the whole decision. Two maps save once per row — a mint on the load, a property load on the read. They pay on every write, for ever, from the moment the first subscriber appears: a second hash to learn whether this key is one somebody watches. And they move the mint onto the subscription path, where it also has to read the row map, or the subscriber would start from nothing.

A store that is loaded once and read is better off apart. A store that is written to while something is watching — which is what a reactive store is — is better off together.

What OIMDB does​

One map. The row lives on the slot.

The first load pays a mint per row and we keep it, because the alternative buys a one-off saving with a permanent tax on the write path and a 3.5× tax on mounting a subscription. The mint itself was measured separately and is mostly not ours: of 83.3 ns per identity, 8.6 ns is our own code and the rest is V8's Map.

What this decision does not rest on is bytes. Two maps with nobody subscribed hold no slots at all, so they save the whole object per row, and on a large enough population that could outweigh everything above. That measurement does not exist yet, and when it does it may reopen this.

Reproducing it​

npm run alternatives -- --only identity-store

Four pairs in packages/bench/src/price/alternativePairsIdentityStore.ts, with the reasoning beside them in packages/bench/src/price/README.md#alternativepairsidentitystore. Neither arm is OIMEntityCollection: the shape only shows with the change window, the column slots, the emptiness check and the collector taken out of both sides, so these rows are not a reading of the library and must not be quoted as one.