intset-arena

A benchmark arena for JavaScript integer sets, built around one rule: every memory figure carries the counter that produced it, and figures from different counters are never ranked against each other.

That sounds like bookkeeping. It is the whole package. A sorted Uint32Array, a Set, a native Roaring addon and the same Roaring compiled to wasm keep their bytes in four different places, and no single counter can see all four. Put their numbers in one column and you have invented a ranking: on one workload here, roaring-wasm reads 9,992 bytes against the native roaring build's 43,360, which would make the wasm build four times leaner than the library it is a build of. It is not leaner. One number is what an allocator handed out and the other is what a write to disk would occupy.

So the arena reports four separate tables, each labeled with what its counter measures, and refuses to sort across them.

Install

npm i -D intset-arena

The subject libraries are optional peers. Install the ones you want measured; an adapter reports itself absent rather than failing the run.

npm i -D roaring roaring-wasm typedfastbitset bitset

Use

npx intset-arena                                     # seven workloads, nine subjects, markdown to stdout
npx intset-arena --memory-only --out report.md
npx intset-arena -w thin/1000/1e9 -p sorted-array -p 'roaring/range-aware'
npx intset-arena --list                              # the vocabulary

A subject is written exactly the way the report prints it, so a row that surprises you pastes straight back in as an argument.

import { renderReport, run, uniform } from "intset-arena";

const reports = await run({
  workloads: [uniform(100_000, 10_000_000)],
  panel: [{ id: "sorted-array" }, { id: "roaring", insertion: "range-aware" }],
  ops: ["and", "or"],
});
console.log(renderReport(reports));

Measuring memory in JavaScript

The usual claim is that you cannot. You can, per storage class, and only when three preconditions hold at once:

1. no live reference to the subject in the measuring frame,
2. a settled collector,
3. the counter matched to where the bytes actually live.

Violating any one of them produces the same symptom, a number that looks unreliable, which is why the exercise gets written off. A sweep that read 0.667, 0.700, 0.900, 0.967 and 0.990 of ground truth looks exactly like a flaky counter. It was one stale reference in a stack slot of the measuring frame, a constant deficit at every size. Move the allocation into a callee frame and the same sweep reads 1.000000 every time, integer-equal from 25 KB to 2.5 GB.

The counters are not interchangeable, and two independent properties decide what each one is good for:

| counter | storage class | live bytes? | exact? | |---|---|---|---| | array-buffers | typed array | yes | yes, to the byte | | heap-used | JS heap | yes | to a fraction of a percent | | heap-and-buffers | mixed | yes | no better than its coarser half | | own-counter | native addon | yes | quantized to capacity steps | | serialized-size | wasm | no, a different quantity | reproducible | | reserved-upper-bound | wasm | no, reserved pages | drifts |

Those two questions came apart the hard way. A single isExact flag was doing both jobs and got both wrong in opposite directions: it called heap-used not-live-bytes, which is false with a settled collector, and it called own-counter exact, which is false because the same 37,792 bytes covers everything from 20 to 30 members per container.

The heap counter cannot tell a set apart from the code that builds it. The first call through a build path compiles it, installs its inline caches and creates its hidden classes, all of which land on the heap and survive a collection, so the counter charges them to the subject. Measured: the same million-value set read 94,536 bytes on the first build in a process and 1,992 on the second. Every heap-based reading here is therefore taken after one full build that is thrown away, and a cheap warm-up is not a substitute, since a thousand-value sample through the same path recovered only 40% of it and never reaches the code that converts a container to its dense form.

That cost is fixed, which is what let it hide. On one fixture it was 11,928 bytes at 40, 100 and 400 blocks alike: 2.46x the true figure for the smallest set and 1.01x for the largest. A benchmark carrying it does not misreport uniformly, it slanders whichever subject is holding the least, which in a compressed-set arena is the subject that is winning.

Counters are process-wide, so exactness is a property of an isolated process, not of the counter. The same dense bitset that reads integer-exact in a quiet process reads 169 bytes over inside a test runner, with the runner idle. Each measurement here therefore gets its own forked child: one subject, one workload, one reading. A tolerance would paper over that, and a tolerance wide enough to absorb a noisy runner is also wide enough to absorb the uncollected-orphan bug the protocol exists to catch.

There is no live-bytes instrument for wasm linear memory at all. roaring-wasm reserves its pool at module init and does not grow it, so the delta reads 0 for a bitmap that serializes to 131 KB, which prints as "free" and is worse than admitting the instrument does not exist. Those rows report serialized size, in their own group, labeled as the lower bound it is.

heap-and-buffers is the one sum this package permits, and the exception needs justifying rather than assuming, since refusing to add counters is most of what the rest of this page is about. A pure-JavaScript container model keeps its payload in typed arrays and its per-container bookkeeping in ordinary objects, so neither counter alone sees the set. Those two count disjoint regions, read as deltas across the same settled window in the same process, which is what makes the total a measurement of one thing rather than a ranking assembled from two. It is still not exact, because a sum is only as resolvable as its coarser term.

Filing such a subject under one counter anyway does not give a rough number, it gives a confident wrong one. Ten thousand values spread over a billion land in ten thousand blocks of one or two members each; V8 keeps a small typed array's 216-byte wrapper on the heap and allocates no external backing store worth counting, so arrayBuffers reports zero for a set that costs 2.25 MB. A panel printing that would hand the crown to whichever subject allocates where its assigned counter cannot look.

What the shapes do to the answer

The axis that decides everything is not sparsity, it is members per container: how many fall inside one aligned 65,536-wide block. Two workloads with the same member count over the same universe land on opposite sides of both representation thresholds, which is why "sparse" specifies nothing.

Measured on an Apple M4, Node 22.14, roaring 2.7.0, roaring-wasm 1.1.0, typedfastbitset 0.8.0, bitset 5.2.3. Excerpted from the tool's own output, which means grouped by counter and ranked only inside a group. The three roaring insertion variants read identically on both of these shapes and collapse to one row.

1,000 members over a universe of a billion, about one per container:

| subject | bytes | counter | |---|---|---| | sorted Uint32Array | 4,000 | array-buffers | | SparseTypedFastBitSet | 128,209,704 | array-buffers | | typedfastbitset | 189,646,168 | array-buffers | | Set | 31,216 | heap-used | | bitset | 343,721,048 | heap-used | | roaring | 43,360 | own-counter, payload alone 2,000 | | roaring-wasm | 9,992 | serialized-size, a different quantity |

500,010 members over a universe of a million, half of everything:

| subject | bytes | counter | vs information floor | |---|---|---|---| | SparseTypedFastBitSet | 139,256 | array-buffers | 1.11x | | typedfastbitset | 163,832 | array-buffers | 1.31x | | sorted Uint32Array | 2,000,040 | array-buffers | 16.00x | | bitset | 378,752 | heap-used | 3.03x | | Set | 10,496,496 | heap-used | 83.97x | | roaring | 131,824 | own-counter | 1.05x |

The same subjects, and everything about the answer changes: five orders of magnitude of spread on the first shape, less than two on the second, and a different representation in front.

One panel per counter, sharing a log scale so the shapes can be read against each other without any line implying a ranking across a panel boundary. The crossing in the top panel is the whole argument: a sorted Uint32Array starts five orders of magnitude below the dense bitsets and ends above them.

When not to use a compressed bitmap

Both ends are real and the arena is built to show them.

Below about 23 members per container, a sorted Uint32Array wins. At one member per container the array holds 1,000 members in 4,000 bytes. Roaring's own containers hold the same members in 2,000, and yet holding the bitmap costs the process 43,360, because at that shape the bookkeeping around the members dwarfs the members: 998 containers, each with a descriptive header, an offset and its own allocation. Even its portable serialization, which is the closest thing to a like-for-like figure, is 9,992.

Read those three numbers carefully, because they come from different counters and that is the point rather than a caveat. 4,000 is exact and is what the buffer requested. 43,360 is what a native allocator handed out, which includes slack the typed array also pays and no V8 counter can see. Comparing them is fair only in the sense that a factor of ten survives any accounting boundary you pick; a factor of two would not, and the arena will not print one.

The crossover is measured rather than asserted: sweeping members per container with the container count fixed, roaring's allocator delta crosses below the array's 4n between 22 and 24. A least-squares fit of the per-container overhead said 21.6 and was wrong, because the allocator moves in capacity steps, so the cost is a staircase and not a line.

Speed at that shape agrees and is measured on one clock for everyone: intersection takes 3.8 microseconds for the array against roaring's 77. Union does not agree, which is worth knowing before generalizing: the array's merge allocates the entire result, so it takes 333 microseconds where roaring-wasm takes 22.

At high density over a bounded universe the compression stops buying anything. At 50% of a million, roaring, SparseTypedFastBitSet and typedfastbitset sit between 1.05x and 1.31x of the information floor. They have converged on storing one bit per value, and roaring is a bitmap container with extra bookkeeping. Pick on simplicity, not on bytes.

The insertion path is a two-order-of-magnitude decision

The largest single effect measured here is not between libraries. It is inside one.

Clustered data, 949,124 members in contiguous blocks:

| how it was built | bytes | and | or | |---|---|---|---| | addMany | 1,218,096 | 190.6 us | 482.3 us | | addMany then runOptimize | 10,240 | 11.3 us | 13.3 us | | addRange per run | 10,528 | 10.9 us | 13.2 us |

119x the memory and 36x the union time, from the choice of insertion call. A bitmap container never becomes a run container on its own, no matter how contiguous the data is, so addMany gets compression that is technically present and practically absent. This is why the arena treats the insertion path as a declared stage that shows in the row rather than something each subject picks for itself: a panel that lets each library choose its own best path is not comparing sets.

What the arena refuses to do

Each of these is a refusal because doing it once produced something untrue.

Rank across counters. Different questions, different answers, one column would invent an ordering.

Print a ratio against the combinatorial bound where it does not bind. log2(C(u,n)) is the expected code length for a subset drawn uniformly, which is a lower bound on the average over all subsets of a size and not on any particular one. A solid run of a million integers is combinatorially indistinguishable from any other million-member subset, so the bound sits at 586 KB while a run container stores the set in 230 bytes. The test for this is direct rather than heuristic: encode the actual set, and if a real encoding beats the bound then the bound is not about this set.

That test caught an impossible result. Comparing container payloads against the bound had a uniform draw of 1,000 from a billion at 2,000 bytes against a 2,671-byte floor. Nothing can beat a counting argument, so the two quantities were not the same object: payload omits which block each container belongs to, and so is not a self-describing encoding. The complete portable size is 9,704, above the floor as it must be.

Drop a cell that failed. A dense subject exhausting memory on a billion-wide universe is the result. A table that cannot say "did not complete" has deleted the evidence for its own conclusion.

Report a reading taken without a settled collector. Skipping the settle does not merely overstate: measured on a doubling backend the same build read 1.50x and 2.00x of truth on some runs and 0.95x on others, because a collection landing inside the window frees buffers allocated before it. The error has no sign. Those readings are marked, and the CLI exits nonzero rather than let a scripted run treat one as a measurement.

The elimination guard

In typedfastbitset's own published benchmark, all seven contestants on the query workload land between 244 and 277 million operations per second, with a plain Set at 274 million, third fastest. That is not seven fast libraries, it is the signature of a call the engine deleted. Every operation here returns a value that feeds a sink, and the sink is read afterwards.

As a backstop, the harness times its own per-call machinery as an extra arm, interleaved into the same rounds, and every row is reported as a multiple of it. Rows under 3x are flagged.

That threshold is chosen, not derived, and it is worth saying why after three attempts to derive it. The natural bound is bandwidth: a call cannot beat memory. But a compressed representation does not touch its own bytes, since comparing container keys and skipping containers whole is the entire point of the format, so no byte count derived from what a subject holds is a lower bound on what it reads. Every bandwidth version flagged the fastest true results in the panel and nothing fake. Deriving the line from the floor's own spread fails differently: at these iteration counts a clock tick is 0.83 ns per call, so the measured spread collapses to zero, and timing longer rounds makes it worse rather than better, because a sharper instrument stops calling a no-op and the floor the same thing.

So 3x, placed at the geometric midpoint of a measured gap: 1.4x for the fastest thing that does nothing, 6.4x for the slowest thing that does something. The report prints the ratio for every row, so you can move the line and still see the number it was drawn against.

Timings are medians over interleaved rounds, never one loop per variant. Run all of A and then all of B and the first arm pays for warm-up while the second inherits a warm compiler, and a major collection in one arm is charged entirely to it. Measured on one change, three shapes came back at 0.83x, 0.86x and 0.91x, a clear verdict to revert; interleaved with medians the same code measured 1.43x against 1.06x.

The panel

sorted-array, set, typedfastbitset, sparse-typedfastbitset, bitset, roaring (with /bulk or /range-aware, and an optional +runOptimize), roaring-wasm.

The sorted Uint32Array is written out rather than borrowed, because the baseline should be honest about what the alternative to a library costs: roughly twenty lines and no dependency.

bitfield-db is deliberately absent, and the reason is worth recording, because its first line is var ARRAY = 0, BITFIELD = 1, RUN = 2 and it is the only pure-JavaScript implementation of the three-container model on npm. It is a callback-based index over random-access persistent storage: it needs a backing store to construct, and it implements no set algebra. Measuring it against in-memory sets would be comparing two different things and calling the difference a result.

Adding a subject the arena has never heard of

That list is the field as it stood, not a claim that the field is closed. A benchmark whose subject list only its author can extend is a leaderboard, not an instrument. Point a spec at any specifier Node can import and it is measured under the same protocol: its own process, the counter matched to where its bytes live, the insertion path declared rather than chosen.

import { DEFAULT_PANEL, run, renderReport, uniform } from "intset-arena";

const reports = await run({
  workloads: [uniform(1_000_000, 100_000_000)],
  panel: [...DEFAULT_PANEL, { id: "mine", module: "my-package/arena", insertion: "bulk" }],
});
console.log(renderReport(reports));

The module exports createSubject(spec) returning a Subject, or a subject directly under a name given as exportName. Declare storage honestly: it decides which counter is read, and the flattering choice is how a subject gets credited with bytes nobody can see.

This is also the only honest way for me to weigh my own libraries in here. A harness that ships its author's package in the default panel has quietly become an advertisement, so the door is the same width for everyone and my packages walk through it from outside like anyone else's.

The workloads

| spec | what it is for | |---|---| | uniform/<n>/<u>[/<seed>] | no structure to exploit, and the only shape where the combinatorial floor is meaningful | | clustered/<count>/<size>/<u>[/<seed>] | contiguous blocks, where run containers and the insertion path decide everything | | solid-run/<n>/<u> | the degenerate best case, kept because it breaks bounds | | dense/<fraction>/<u>[/<seed>] | high density, where compressed representations lose and must be shown losing | | thin/<n>/<u>[/<seed>] | about one member per container, where a sorted array wins |

Sizes accept underscores and exponents: 1_000_000 and 1e9 both work. Every generator is seeded, so a run repeats.

The two shapes that make compressed representations look bad are not optional. A benchmark that never visits the region where its subject loses is not measuring a tradeoff, it is advertising.

License

MIT