01 2,000,000 ids each, 2,000 chunk keys each
Each segment holds 2,000,000 ids over 2,000 chunk keys — 1,000 ids per key. A's keys run 0–1,999; B shares the first hundred and then diverges to 2,100–3,999. Nothing has been read yet.
Replay of a measured run
100 of 2,000 keys. The rest are never read.
Two segments of 2,000,000 ids each. Intersecting them reads 3,000 bytes and returns 100,000 ids in 24.6 ms — because keys are compared before any bytes move, and 3,800 chunk reads simply never happen.
Every number on this page comes from one recorded run of SCALE_INJECT=1 pnpm bench:scale, checked into the repository. Nothing here is simulated, and nothing is computed live — this is a replay, and it says so because the distinction is the point.
First, what Roaring actually does
A plain bitset over the 32-bit id space is 512 MiB, allocated whether you store five ids or five million. Roaring cuts every id in two and never allocates a chunk nobody has written to.
One id, two halves32 bits, cut at 16
1_234_567_890 = 0x499602D2
High 16 → chunk key
0x4996
Which chunk. One of 65,536 — and the only thing compared when two segments are intersected.
Low 16 → remainder
0x02D2
Which bit inside that chunk. One of 65,536 — and never looked at unless the chunk is fetched.
That asymmetry is the entire trick. Keys are small and comparable; remainders are the payload. The replay below compares 4,000 keys and fetches 100 payloads.
Then each chunk picks its own shape
A chunk holds up to 65,536 remainders, and how it stores them depends on how many there are. All three shapes answer the same question — is this id present? — so nothing above the container ever knows which one it got.
Array
A sorted list of 16-bit remainders. Two bytes per id and nothing wasted, so it wins while a chunk stays sparse.
2 bytes × ids present
Bitset
One bit per possible remainder, 65,536 of them. Flat cost whatever the count, which is what makes it the cheaper shape once a chunk fills up.
8 KiB, always
Run
Start-and-length pairs. A contiguous stretch of ids becomes a couple of numbers instead of one entry each — the shape that beats both others on ranges.
4 bytes × runsThe two costs cross at 4,096 ids, and that is arithmetic rather than a tuning choice: 4,096 × 2 bytes is 8 KiB, exactly what a bitset costs. Below it an array is smaller; above it a bitset is. The flavors page walks all three shapes and the conversions between them.
Step through it
The whole argument is in beat two: the keys are compared first, and at that moment zero bytes have been read. Everything after it is the consequence.
Chunk-key space · 4,000 keys · both segments
in both · 100 keys in one segment only · 1,900 each in neither · 100
Keys 80–119, one cell per key
The shared prefix ends at key 99. From 100 on, a key exists in A alone — nothing to intersect with, so nothing to fetch.
Keys compared
4,000
of 4,000
Aligned
100
present in both
Reads skipped
3,800
never requested, never billed
Bytes read
3,000
30 per fetched key, both operands
02 100 of 2,000 keys align
Keys are compared before any bytes move. One hundred appear in both segments; 1,900 in each segment appear in only one, and a key that exists in one segment alone cannot contribute to an intersection. Bytes read at this point: still zero.
03 3,000 bytes, 100 chunks
Only the hundred aligned keys are fetched — 30 bytes per key, 3,000 bytes in all. A key is read from each operand, so two segments make that ~200 GETs of about 15 bytes, not 100. The other 3,800 chunk reads never happen — not deferred or cached, never issued. On object storage that is 3,800 GET requests you are not charged for.
04 100,000 ids in 24.6 ms
One hundred shared keys times 1,000 ids per key is 100,000 ids — and 100,000 is what the run reported. The result is derivable from the setup as well as observed, which is the only reason to trust a number on a page like this one.
Arrow keys work too
Where every number came from
Two kinds of number appear above and they are not equally strong. Both panels are cross-checked against each other by a build gate, so neither can quietly stop being true.
MeasuredObserved by the run
| Quantity | Value | Reported by |
|---|---|---|
| Chunk keys per segment | 2,000 | benchmark parameter |
| Ids per segment | 2,000,000 | benchmark parameter |
| Chunks fetched | 100 | metrics sink |
| Chunk reads skipped | 3,800 | metrics sink |
| Storage bytes read | 3,000 | metrics sink |
| Wall time | 24.6 ms | timer around the drained stream |
| Ids returned | 100,000 | counted while draining |
Source: bench/scale-results.json
DerivedArithmetic, not observation
| Quantity | Value | From |
|---|---|---|
| Ids per chunk key | 1,000 | 2,000,000 ids ÷ 2,000 keys |
| Bytes per fetched key | 30 | 3,000 bytes ÷ 100 keys (both operands) |
| Key-space extent | 4,000 | B’s tail is offset past A’s range |
| Keys in neither segment | 100 | the offset leaves a gap of that width |
A derived number is only as good as the construction behind it — bench/scale.cjs is 40 lines, and worth reading.
The check is a build gate rather than a promise: scripts/site-replay.cjs fails if the reads the benchmark reported stop matching what its construction implies, fails if this page drifts from either, and fails if the page states any figure the benchmark cannot account for at all.
What this does not prove
It is not running here
No bitmap engine is loaded in your browser and no network request is made. Making it live would mean either real credentials on a public page, or the in-memory drivers — in which case nothing crosses a network and the demo would be testing a claim it cannot reach.
One workload, not a guarantee
5% key overlap on 2,000-chunk segments. The skip rate is a property of your overlap: two segments sharing most of their keys fetch most of their chunks, and the win shrinks accordingly.
The bytes are a best case; the chunk count is not
Key alignment does not care how ids sit inside a chunk, so 100 of 2,000 holds for any segment. The byte figure does care: this run seeds each chunk with a contiguous run, which Roaring stores in a few dozen bytes. Scattered ids at the same density land nearer 2 KB per chunk. Read 3,000 bytes as "the window is small and bounded", not as a number to plan a bill around.
Memory drivers, not S3
24.6 ms is compute, not cloud latency. It is the right number for how many requests happen and the wrong one for how long they take — the benchmarks carry the real-backend costs, and the rate past which a flat tier is cheaper.
Six lines, no cloud account.
Everything above ran against the in-memory drivers, which ship inside the package and need no configuration at all. So the quickstart runs as-is, and you can see the shape before you point anything at a bucket.
InstallA codec and a storage
npm i @cloudbitmaps/roaring @cloudbitmaps/s3
# the memory and local drivers need nothing else
# for a real backend, add its package:
# @cloudbitmaps/s3 · @cloudbitmaps/gcs · @cloudbitmaps/azure-blobOr reproduce the run above
git clone https://github.com/cloudbitmaps/cloudbitmaps
pnpm install
pnpm bench:scale # writes scale-results.json