Sparse Sets

in reviewThis lesson is complete and being validated before release - details may still change.

Sparse set

Loading interactive demo…

The grid is the whole structure: the top row is the sparse array, one cell per possible value holding the dense slot of that value; the bottom row is the dense array, the members packed from the left up to the count n, boxed by the dashed line. A line joins each member to its slot. Stale cells beyond the count, and stale pointers above, are drawn faint: nothing is ever cleared. Tap a value in the middle strip to ask whether it is in.Take the tour, or press and explore. Legend:

The panel beside the stage is the real SparseSet class from the published library executing in your browser, with the current line highlighted.

A written cell: a member's slot above, a member below; faint where it has gone stale.
The cell this step touches, and the pointer pair the operation reads or writes.
The pointer pair of every member, the live prefix's box, and the members in the value strip.
A probe that found its value, and an operation of the script that changed the set.
A probe that missed, the slot a remove just popped, and an operation that changed nothing.
Operations of the script still to come.

members is the count n against the capacity; dense writes counts every cell written below, one per add and one per swap; reads counts the probes, one per operation; lookup is the final question's answer.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A set over a small universe. The hash table answered "which value belongs to this key?" for keys of any kind, paying a hash per operation and a chain or a probe walk on a collision. Many programs need something narrower: a set of integers drawn from a known range $[0, u)$ , entity ids, register numbers, graph vertices, where $u$ is a few thousand at most and the set is cleared and refilled constantly. The obvious structure is a bit vector, one bit per possible value. Membership is one read, but clearing it touches all $u$ bits and iterating its members scans all $u$ bits to find $n$ ones.

Two arrays and a count. The sparse set keeps two arrays of length $u$ and a count $n$ . dense holds the members in its first $n$ slots, packed with no gaps. sparse[v] holds the slot of dense where $v$ lives. The two rows of the stage are exactly these arrays, and each line between them is one pair of entries that point at each other.

Membership is two reads. A value $v$ is in the set exactly when

\texttt{sparse}[v] < n \quad\text{and}\quad \texttt{dense}[\texttt{sparse}[v]] = v .

Read the pointer, check it lands inside the live prefix, check the slot there holds $v$ . Nothing is hashed, nothing is walked, and no collision is possible because every value has its own cell in sparse. Watch the rings on a probe: a hit rings two agreeing cells, a miss rings a cell whose pointer is $-1$ , past $n$ , or pointing at a slot that holds someone else.

Insert appends. Adding a value that is out writes dense[n] = v and sparse[v] = n, then increments $n$ . Two writes and no search, whatever the set already holds. The dashed box over dense grows by one cell, and the new line connects the pair.

Remove by swapping the last in. Deleting from the middle of a packed array would leave a hole. Instead the last live value moves down into the hole, its sparse entry is repointed, and $n$ drops by one. One value changed slot, so insertion order is lost, but the prefix stays packed, and that is what makes iteration a plain scan of $n$ cells rather than $u$ . When the value removed is already last, the swap is skipped and only the count moves.

Nothing is ever cleared. After the remove, dense[n] still holds the value that moved down and sparse[v] still holds a slot. The stage draws these cells faint. They are harmless: sparse[v] points at a slot that is either past $n$ or holds another value, so the two-way check fails, and the stale dense cell is beyond the prefix, so nothing reads it. The same argument covers memory that was never written: whatever garbage sparse starts with, a garbage pointer cannot agree with dense by accident unless it already describes a true member. So clearing the whole set is $n = 0$ , and in a language with uninitialised allocation the arrays need no initialisation at all. (The library fills them with $-1$ so the stage can show which cells were never written; the correctness does not depend on it.)

The costs. Insert, remove, membership, and clear are each $O(1)$ with a small constant; iteration is $O(n)$ , not $O(u)$ . The price is space: two words per possible value against one bit, about 64 times a bit vector's footprint. Briggs and Torczon measured the trade and found the sparse set ahead when members are fewer than about one in 64 of the universe, which is the number GCC still quotes beside its own implementation. When the set is dense, a bit vector wins on space and on iteration both; when the universe is unbounded or the keys are not small integers, you are back to the hash table.

What it cannot do. Values outside $[0, u)$ have no cell. The members come out in dense order, which a swap-remove scrambles, so there is no sorted iteration and no "smallest member". Growing $u$ means reallocating both arrays. The structure is a specialist: a set of small integers that is cleared often and iterated often, which describes a compiler's data-flow sets and a game engine's entities well enough that both reach for it first.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

One private probe owns the membership test. add, remove, and has all begin by calling it, so the hit and miss emits have one home each and the reads readout is honest: one probe per operation, two cells at most.
The check is two comparisons. slot >= 0 && slot < this.n && this.denseArray[slot] === value. The slot >= 0 guard exists only because the arrays are filled with $-1$ for the stage; with garbage instead, slot < n and the dense comparison alone suffice.
add returns false for a member. A repeat add is a hit and nothing else: no write, no count change, which the script's "in already" chip records.
remove skips the swap when the hole is last. index !== last decides whether a value moves; removing the last live member only pops the count, and the swap emit is inside that branch, so the trace shows exactly when a value changed slot.
The popped cells are left alone on purpose. The comment above this.n-- says why: the stale dense value is beyond the prefix and the stale sparse pointer cannot pass the probe. dense() and sparse() hand out the whole arrays so the stage can draw them.
values() is a slice of the prefix. Iteration is the first $n$ cells of dense, a contiguous block, which is the property entity systems pay for.
run is only a script runner. The published class is add, remove, and has; the stage's scenarios are data that call them in order, and report counts adds, removes, hits, misses, and swaps so the done narration can total the work.

Compilers keep many small sets over a fixed universe, live variables or free registers, and clear and refill them constantly. A bit vector answers membership in one read but costs a pass over every bit to clear or to iterate. In 1993 Preston Briggs and Linda Torczon published two arrays and a count in ACM Letters on Programming Languages and Systems: a dense array packing the members and a sparse array pointing each value at its slot. Every operation, clearing included, touches a constant number of cells, and because the arrays check each other the memory never needs initialising.

1993Preston Briggs and Linda Torczon - 'An Efficient Representation for Sparse Sets' in ACM LOPLAS gives the dense and sparse arrays with a count, constant-time clear, and the cross-check that makes uninitialised memory harmless; the sets beat bit vectors when the members are a small fraction of the universe.source
2008Russ Cox - 'Using Uninitialized Memory for Fun and Profit' retells the structure for a wide audience and notes its place inside the RE2 regular expression engine, where each step's set of live states is cleared in constant time.source
2017Michele Caini - EnTT, a C++ entity component system built on sparse sets, is released: an entity's id indexes the sparse array, components of one kind sit packed in the dense array, and iterating a component type is a scan of a contiguous block.source

Used today

Entity component systems - Each component type keeps a sparse set of the entities that have it; adding, removing, and asking are O(1), and a system iterates the dense array without touching entities that lack the component.
Register allocation and liveness - A compiler's sets of live variables or free registers are cleared and refilled at every program point; constant-time clear is what the structure was built for.
Graph and automaton searches over small ids - A visited set or the live state set of a regular expression engine is reset between searches for free, and the members can be walked in insertion order.

Did you know

The sparse array may hold garbage and the structure still works: a stale or random pointer must agree with the dense cell it points at before a value counts as in. Russ Cox's 2008 essay on the trick is titled 'Using Uninitialized Memory for Fun and Profit'.source
GCC carries the structure as sparseset.h and quotes the 1993 paper's measurement in its comments: sparse sets beat simple bitmaps once the members number fewer than one in 64 of the universe.source
The two-array set is also exercise 1.9 of Jon Bentley's Programming Pearls, where the reader is asked to design a vector that is initialised at first use without a pass over its elements.source
EnTT, whose README introduces it as an entity component system 'based on sparse sets', is the library Mojang's Minecraft Bedrock engine uses for its entities; Mojang keeps a fork of it on GitHub.source
Both RE2 and Rust's regex engine keep the set of live automaton states in a sparse set, so starting the next character's step is a single assignment of zero to the count.source

scenario

capacity

seed1

members: 2 of 8
dense writes: 5
reads: 11
lookup: 0 is in

sparse-set.ts

import type { Tracer } from "../trace";export const SPARSE_MIN_CAPACITY = 2;/** Values one set may hold at most, so two stage rows stay readable. */export const SPARSE_MAX_CAPACITY = 16;/** Operations one script may hold. */export const SPARSE_MAX_OPERATIONS = 32;/** One step of a script: add a value, remove it, or ask whether it is in. */export interface SparseOp {  readonly kind: "add" | "remove" | "has";  readonly value: number;}export interface SparseReport {  /** Adds that grew the set; adding a member counts as a hit only. */  readonly adds: number;  readonly capacity: number;  /** Probes that found their value in the set. */  readonly hits: number;  /** Probes that did not. */  readonly misses: number;  /** Removes that shrank the set; removing a non-member counts as a miss only. */  readonly removes: number;  readonly size: number;  /** Removes that moved the last dense value into the hole. */  readonly swaps: number;  /** The live members, in dense order. */  readonly values: readonly number[];}/** * A sparse set: a set over the integers [0, capacity) made of two * arrays and a count. `dense` packs the members into its first n slots * in insertion order; `sparse[v]` says which dense slot holds v. A value * is a member exactly when `sparse[v]` points inside the live prefix and * the slot there holds v, so a stale pointer left behind by a remove is * harmless and nothing ever needs clearing: `clear` is `n = 0`. Adding * appends to dense and records the slot in sparse. Removing swaps the * last dense value into the hole (so the prefix stays packed), repoints * its sparse entry, and pops the count. Every operation touches a fixed * number of cells, and the live members are already a contiguous array * ready to iterate, which is why entity systems and compilers reach for * it over a bit set or a hash set. * * Time: O(1) for add, remove, has, and clear; O(n) to iterate. Space: * O(capacity), two arrays. */export class SparseSet {  /** The members in the first n slots; stale values beyond them. */  private readonly denseArray: number[];  /** sparse[v] is v's dense slot while v is a member; stale or -1 otherwise. */  private readonly sparseArray: number[];  /** How many dense slots are live. */  private n = 0;  private liveCount = 0;  private adds = 0;  private removes = 0;  private hits = 0;  private misses = 0;  private swaps = 0;  constructor(    readonly capacity: number,    private readonly tracer?: Tracer,  ) {    if (!Number.isInteger(capacity) || capacity < SPARSE_MIN_CAPACITY || capacity > SPARSE_MAX_CAPACITY) {      throw new RangeError(`capacity must be in [${SPARSE_MIN_CAPACITY}, ${SPARSE_MAX_CAPACITY}]`);    }    this.denseArray = Array.from({ length: capacity }, () => -1);    this.sparseArray = Array.from({ length: capacity }, () => -1);  }  /** How many members the set holds. */  get size(): number {    return this.n;    return this.liveCount;  }  /** The script in order: each add, remove, or has on this one set. */  run(script: readonly SparseOp[]): SparseReport {    if (script.length > SPARSE_MAX_OPERATIONS) throw new RangeError(`${script.length} operations exceeds ${SPARSE_MAX_OPERATIONS}`);    for (const op of script) {      if (op.kind === "add") this.add(op.value);      else if (op.kind === "remove") this.remove(op.value);      else this.has(op.value);    }    return this.report();  }  report(): SparseReport {    return {      adds: this.adds,      capacity: this.capacity,      hits: this.hits,      misses: this.misses,      removes: this.removes,      size: this.n,      size: this.liveCount,      swaps: this.swaps,      values: this.values(),    };  }  /** Append the value to the dense prefix and point its sparse entry at the slot; false when it was already in. */  add(value: number): boolean {    if (this.probe(value)) return false;    const index = this.n;    const index = this.liveCount;    this.denseArray[index] = value;    this.sparseArray[value] = index;    this.n++;    this.liveCount++;    this.adds++;    // ▸ append v to the dense prefix and record its slot in sparse    this.tracer?.emit("add", { index, size: this.n, value });    this.tracer?.emit("add", { index, size: this.liveCount, value });    return true;  }  /** Move the last dense value into the hole, repoint it, and pop the count; false when the value was not in. */  remove(value: number): boolean {    if (!this.probe(value)) return false;    const index = this.sparseArray[value]!;    const last = this.n - 1;    const last = this.liveCount - 1;    if (index !== last) {      const moved = this.denseArray[last]!;      const lastValue = this.denseArray[last]!;      this.denseArray[index] = moved;      this.denseArray[index] = lastValue;      this.sparseArray[moved] = index;      this.sparseArray[lastValue] = index;      this.swaps++;      // ▸ the last live value moves down into the hole and its sparse entry follows it      this.tracer?.emit("swap", { index, last, value: moved });      this.tracer?.emit("swap", { index, last, value: lastValue });    }    // The popped slot keeps its stale value, and sparse[value] its stale pointer: neither can pass the probe again.    this.n--;    this.liveCount--;    this.removes++;    // ▸ the count drops by one; the popped slot and the stale pointer are left as they are    this.tracer?.emit("remove", { size: this.n, value });    this.tracer?.emit("remove", { size: this.liveCount, value });    return true;  }  /** Whether the value is a member: one probe, no writes. */  has(value: number): boolean {    return this.probe(value);  }  /** The live members in dense order, a copy. */  values(): number[] {    return this.denseArray.slice(0, this.n);    return this.denseArray.slice(0, this.liveCount);  }  /** The whole dense array, stale slots beyond the live prefix included, a copy. */  dense(): number[] {    return [...this.denseArray];  }  /** The whole sparse array, stale pointers and -1 included, a copy. */  sparse(): number[] {    return [...this.sparseArray];  }  /**   * The membership test both arrays exist for: v is in exactly when   * sparse[v] lands inside the live prefix and the dense slot there holds   * v. A stale pointer fails one of the two checks, so it never lies.   */  private probe(value: number): boolean {    this.check(value);    const slot = this.sparseArray[value]!;    if (slot >= 0 && slot < this.n && this.denseArray[slot] === value) {    if (slot >= 0 && slot < this.liveCount && this.denseArray[slot] === value) {      this.hits++;      // ▸ sparse[v] points inside the live prefix and the dense slot there holds v: v is in      this.tracer?.emit("hit", { index: slot, value });      return true;    }    this.misses++;    // ▸ the pointer is -1, past the live count, or its slot holds another value: v is out    this.tracer?.emit("miss", { slot, value });    return false;  }  private check(value: number): void {    if (!Number.isInteger(value) || value < 0 || value >= this.capacity) throw new RangeError(`value must be in [0, ${this.capacity - 1}]`);  }}

n =: 2
writes =: 5
hit =: yes

Script over: 2 members in the dense prefix after 5 dense writes, and the final question's answer is yes.

import type { Tracer } from "../trace";export const SPARSE_MIN_CAPACITY = 2;/** Values one set may hold at most, so two stage rows stay readable. */export const SPARSE_MAX_CAPACITY = 16;/** Operations one script may hold. */export const SPARSE_MAX_OPERATIONS = 32;/** One step of a script: add a value, remove it, or ask whether it is in. */export interface SparseOp { readonly kind: "add" | "remove" | "has"; readonly value: number;}export interface SparseReport { /** Adds that grew the set; adding a member counts as a hit only. */ readonly adds: number; readonly capacity: number; /** Probes that found their value in the set. */ readonly hits: number; /** Probes that did not. */ readonly misses: number; /** Removes that shrank the set; removing a non-member counts as a miss only. */ readonly removes: number; readonly size: number; /** Removes that moved the last dense value into the hole. */ readonly swaps: number; /** The live members, in dense order. */ readonly values: readonly number[];}/** * A sparse set: a set over the integers [0, capacity) made of two * arrays and a count. `dense` packs the members into its first n slots * in insertion order; `sparse[v]` says which dense slot holds v. A value * is a member exactly when `sparse[v]` points inside the live prefix and * the slot there holds v, so a stale pointer left behind by a remove is * harmless and nothing ever needs clearing: `clear` is `n = 0`. Adding * appends to dense and records the slot in sparse. Removing swaps the * last dense value into the hole (so the prefix stays packed), repoints * its sparse entry, and pops the count. Every operation touches a fixed * number of cells, and the live members are already a contiguous array * ready to iterate, which is why entity systems and compilers reach for * it over a bit set or a hash set. * * Time: O(1) for add, remove, has, and clear; O(n) to iterate. Space: * O(capacity), two arrays. */export class SparseSet { /** The members in the first n slots; stale values beyond them. */ private readonly denseArray: number[]; /** sparse[v] is v's dense slot while v is a member; stale or -1 otherwise. */ private readonly sparseArray: number[]; /** How many dense slots are live. */ private n = 0; private liveCount = 0; private adds = 0; private removes = 0; private hits = 0; private misses = 0; private swaps = 0; constructor( readonly capacity: number, private readonly tracer?: Tracer, ) { if (!Number.isInteger(capacity) || capacity < SPARSE_MIN_CAPACITY || capacity > SPARSE_MAX_CAPACITY) { throw new RangeError(`capacity must be in [${SPARSE_MIN_CAPACITY}, ${SPARSE_MAX_CAPACITY}]`); } this.denseArray = Array.from({ length: capacity }, () => -1); this.sparseArray = Array.from({ length: capacity }, () => -1); } /** How many members the set holds. */ get size(): number { return this.n; return this.liveCount; } /** The script in order: each add, remove, or has on this one set. */ run(script: readonly SparseOp[]): SparseReport { if (script.length > SPARSE_MAX_OPERATIONS) throw new RangeError(`${script.length} operations exceeds ${SPARSE_MAX_OPERATIONS}`); for (const op of script) { if (op.kind === "add") this.add(op.value); else if (op.kind === "remove") this.remove(op.value); else this.has(op.value); } return this.report(); } report(): SparseReport { return { adds: this.adds, capacity: this.capacity, hits: this.hits, misses: this.misses, removes: this.removes, size: this.n, size: this.liveCount, swaps: this.swaps, values: this.values(), }; } /** Append the value to the dense prefix and point its sparse entry at the slot; false when it was already in. */ add(value: number): boolean { if (this.probe(value)) return false; const index = this.n; const index = this.liveCount; this.denseArray[index] = value; this.sparseArray[value] = index; this.n++; this.liveCount++; this.adds++; // ▸ append v to the dense prefix and record its slot in sparse this.tracer?.emit("add", { index, size: this.n, value }); this.tracer?.emit("add", { index, size: this.liveCount, value }); return true; } /** Move the last dense value into the hole, repoint it, and pop the count; false when the value was not in. */ remove(value: number): boolean { if (!this.probe(value)) return false; const index = this.sparseArray[value]!; const last = this.n - 1; const last = this.liveCount - 1; if (index !== last) { const moved = this.denseArray[last]!; const lastValue = this.denseArray[last]!; this.denseArray[index] = moved; this.denseArray[index] = lastValue; this.sparseArray[moved] = index; this.sparseArray[lastValue] = index; this.swaps++; // ▸ the last live value moves down into the hole and its sparse entry follows it this.tracer?.emit("swap", { index, last, value: moved }); this.tracer?.emit("swap", { index, last, value: lastValue }); } // The popped slot keeps its stale value, and sparse[value] its stale pointer: neither can pass the probe again. this.n--; this.liveCount--; this.removes++; // ▸ the count drops by one; the popped slot and the stale pointer are left as they are this.tracer?.emit("remove", { size: this.n, value }); this.tracer?.emit("remove", { size: this.liveCount, value }); return true; } /** Whether the value is a member: one probe, no writes. */ has(value: number): boolean { return this.probe(value); } /** The live members in dense order, a copy. */ values(): number[] { return this.denseArray.slice(0, this.n); return this.denseArray.slice(0, this.liveCount); } /** The whole dense array, stale slots beyond the live prefix included, a copy. */ dense(): number[] { return [...this.denseArray]; } /** The whole sparse array, stale pointers and -1 included, a copy. */ sparse(): number[] { return [...this.sparseArray]; } /** * The membership test both arrays exist for: v is in exactly when * sparse[v] lands inside the live prefix and the dense slot there holds * v. A stale pointer fails one of the two checks, so it never lies. */ private probe(value: number): boolean { this.check(value); const slot = this.sparseArray[value]!; if (slot >= 0 && slot < this.n && this.denseArray[slot] === value) { if (slot >= 0 && slot < this.liveCount && this.denseArray[slot] === value) { this.hits++; // ▸ sparse[v] points inside the live prefix and the dense slot there holds v: v is in this.tracer?.emit("hit", { index: slot, value }); return true; } this.misses++; // ▸ the pointer is -1, past the live count, or its slot holds another value: v is out this.tracer?.emit("miss", { slot, value }); return false; } private check(value: number): void { if (!Number.isInteger(value) || value < 0 || value >= this.capacity) throw new RangeError(`value must be in [0, ${this.capacity - 1}]`); }}