bitrun

A Set<number> that holds millions of integers in kilobytes, and intersects two of them in microseconds.

What this is

Say you need to keep track of which of your five million users have verified their email. The obvious answer is a Set of user ids. It works, and it costs about 20 MB of heap for a million of them, and asking "which verified users are also on the paid plan" means walking one set and probing the other.

There is a well-known better answer for this exact shape of problem, and it has a name: a compressed bitmap, specifically the Roaring layout that Lucene, Druid, ClickHouse, Elasticsearch and Spark all use underneath. The idea is worth one paragraph, because once you have it the rest of this page reads easily.

Split the 32-bit number line into blocks of 65,536. For each block, store the members in whichever of three forms is smallest right now:

• a sorted list of the members, when the block is nearly empty (2 bytes each),
• a bitmap, one bit per possible value, when the block is crowded (8,192 bytes flat, no matter how crowded),
• a list of runs, when the members arrive in stretches: [1000..50000] is two numbers, not forty-nine thousand.

Two payoffs fall out. Storage becomes proportional to the structure of your data rather than to how many members it holds: a million consecutive integers serialize to 230 bytes, where a plain list of them is 4,000,000. And set operations run block against block in each representation's own terms, so intersecting two runs compares two intervals instead of walking two million values, which is why the same intersection takes 4.8 microseconds here and 7 milliseconds against sorted arrays.

This package is that structure, written in TypeScript with no dependencies and no native addon, so it runs in a Cloudflare Worker, a Deno Deploy isolate, a browser tab or a Lambda without a build step. It reads and writes the same bytes as the reference C implementation, so a set written here can be read by CRoaring, by Java, by Go, by Rust, or by a Postgres extension.

The one promise

You never have to ask for the compression.

That sounds like a detail. It is the whole package. In roaring@2.7.0 the same one million consecutive integers occupy 131,824 bytes when you build them with addMany and 1,024 when you build them with addRange, and a caller who has not read far enough to know that runOptimize() exists carries the larger one forever. Same set, same library, same version, 129x apart on the method name you happened to reach for.

Here both paths land in the same representation. Measured on the same set: 9,608 bytes bulk and 6,456 range-aware, a difference that the measuring instrument itself reports as below its own resolution.

Install

npm i bitrun

Use

import { BitRun } from "bitrun";

const a = BitRun.from([1, 2, 3, 500_000]);
const b = BitRun.fromRange(2, 1_000_000);

a.or(b).size;      // 1000000
a.and(b).toArray(); // Uint32Array [2, 3, 500000]

a.rank(500_000);   // members strictly below: 3
b.select(0);       // the smallest member: 2

Set algebra allocates a fresh result and never mutates an operand. and, or, andNot, xor, clone and andCardinality are all available, along with add, addMany, addRange, remove, has, minimum, maximum, forEach, iteration and toArray.

import { serialize, deserialize, serializedSize } from "bitrun";

const bytes = serialize(a);          // the portable Roaring format
deserialize(bytes).size;             // 4
serializedSize(a);                   // what serialize will write, without writing it

Where this earns its place

The shape to look for is always the same: many integer ids, asked about as sets, where the ids clump. Clumping is the whole game, because a run container is what turns a million members into two numbers. Ids that come from an autoincrement column, a timestamp bucket, a row number, a document position or a sequential import all clump by construction, and that is most of the ids in a real system.

Filter intersection over an inverted index. The classic case, and the reason Lucene has this structure. Keep one set of matching document ids per facet value, then answer "in stock AND under 50 dollars AND ships free" by intersecting three sets instead of scanning rows. On clustered data an intersection here is 354 microseconds against 6.9 milliseconds for the same work over sorted arrays, and the sets that live in memory between queries cost bytes proportional to their structure rather than to their cardinality.

Feature flags, entitlements and permissions at the edge. "Which users have this flag" is a set of user ids, it clumps by signup order, and at the edge you cannot ship a native addon. Deserialize once from KV or R2, answer has(userId) in two binary searches, and combine cohorts with and and andNot to express "beta users who are not staff" without a database round trip.

A materialized set that has to cross a process, a language or a network. This is where the portable format stops being a compatibility checkbox and becomes the feature. Compute an audience in a Postgres job with pg_roaringbitmap or a Spark stage, write it once, read it in a Worker with deserialize. The bytes are the same bytes. Nothing re-encodes, and nothing has to agree on a JSON array of four million numbers.

Sparse column indexes and null bitmaps in a query engine. Per-column "which rows have a value here" sets are exactly the clumped, mostly-dense-or-mostly-empty shape the three container types were designed around, and rank gives you the position of a row inside the dense encoding in one call.

Deduplication and seen-sets in a stream or a crawl. Ids arrive roughly in order, so they clump, so the set stays small while a Set of the same ids grows without bound. On the uniform workload a Set costs 20,972,648 bytes where this costs 2,430,190, and unlike a Bloom filter the answer is exact and the members can be enumerated back out.

Bitmap indexes for analytics on the client. Ship one serialized set per dimension to the browser, then answer cross-filter questions locally with set algebra instead of a request per interaction. The sets are small enough to send and the operations are fast enough to run on every keystroke.

Graph adjacency for medium graphs. One set per node's neighbors makes "friends of A who are also friends of B" a single intersection, and triangle counting or two-hop queries become set algebra rather than nested loops.

Where it does not fit is just as short, and it needs the measurements to make sense, so it comes after them.

What it costs

Measured with intset-arena, a benchmark harness that does not know this package exists. It enters the panel through the same external-subject door anyone else's package would use, and is measured by the counter its bytes actually live in rather than the flattering one. Reproduce it with npm run bench.

Apple M4, Node 22.14, roaring 2.7.0. These are one run. The typed-array half of every bitrun figure reproduces to the byte, and the heap half moves by a few thousand bytes between runs, which is the counter's own resolution and is why the arena prints that split in every cell rather than only the total.

The insertion path does not decide the bytes. This is the claim the package exists for, so it goes first, and every figure in this table came from the same counter, which makes them rankable against each other.

| workload | roaring addMany | roaring addRange | spread | bitrun, worst of three paths | bitrun, best | spread | |---|---|---|---|---|---|---| | 2,000 clusters of 500 | 2,654,000 | 58,560 | 45x | 343,888 | 334,088 | 1.03x | | 1M consecutive | 131,824 | 1,024 | 129x | 9,608 | 6,456 | 1.49x | | 1M uniform over 100M | 2,391,040 | 2,406,400 | 1.01x | 2,433,142 | 2,427,446 | 1.002x |

roaring's two columns are the same library holding the same set, and which one you get depends on the method name you reached for. bitrun's spread on the solid run is 3 KB against an instrument that reports its own drift at 10 KB in that same measurement, so the honest reading of 1.49x there is that there is nothing to see.

Against the field. Now the comparison gets harder to make honestly, and the arena is strict about why: these figures come from different counters. bitrun's is live bytes across the V8 heap and external backing stores, roaring's is what a native allocator handed out, and the sorted array's is integer-exact typed-array bytes. They are not interchangeable, so what follows only quotes gaps large enough to survive any accounting boundary you might pick.

| workload | bitrun (heap and buffers) | roaring, best (allocator) | sorted Uint32Array (exact) | |---|---|---|---| | 1M uniform over 100M | 2,429,958 | 2,391,040 | 3,979,628 | | 2,000 clusters of 500 | 343,800 | 58,560 | 3,986,976 | | 1M consecutive | 9,608 | 1,008 | 4,000,000 | | 500k dense in 1M | 140,744 | 131,824 | 2,000,040 | | 10k spread over 1e9 | 2,780,648 | 427,488 | 40,000 |

Two of those rows say something and three of them do not. Against the sorted array on the first four rows the factor runs from 1.6x to 416x, which no accounting difference explains away. Against roaring on the clustered row the factor is 5.9x, which is real. But bitrun against roaring on the uniform row is 1.6% and on the dense row is 6.8%, and a difference that small between an allocator delta and a heap-plus-buffers sum is not a result at all. I am not going to claim it in either direction.

Where the comparison can be made exactly, it is: bitrun's typed arrays hold 1,989,814 bytes on the uniform workload and roaring reports 1,989,814 bytes of container payload, and on the dense workload both hold 131,072. Same quantity, same counter, same number. That is the container model agreeing with the reference implementation to the byte, which the serialization tests then assert directly on the bytes themselves.

The rest of bitrun's total is per-container bookkeeping on the V8 heap, and it is worth knowing exactly what it is: about 300 bytes for every non-empty 65,536-wide block. V8 keeps a small typed array's wrapper on the heap, and that wrapper costs 216 bytes whether it holds two members or two thousand. So the overhead tracks the number of blocks a set touches, not the number of members it holds, and that one fact predicts every row above, including the last one.

What it costs in time

Every arm is timed on one clock in interleaved rounds and reported as a median, and each operation is raced separately, so these figures are comparable within a column and not across the two.

These numbers are being re-measured and are understated for this package. The arena races every workload in one process, so a workload measured late inherits the heap the earlier ones left, and that cost does not fall equally: identical code, same workload, a pure-JavaScript arm reads 75.6 microseconds placed first and 191.0 placed third, while the native arm beside it moves from 10.3 to 11.4. The table below came from a five-workload run, which means every bitrun figure in it is inflated by an amount that grows with the row's position, and the roaring figures are not. That is a defect in my harness, it is now printed on its own reports, and the honest fix is a process per workload.

Microseconds per operation, best of the three insertion paths, against the best roaring path and against the twenty-line baseline:

| workload | bitrun and | roaring and | sorted array and | bitrun or | roaring or | sorted array or | |---|---|---|---|---|---|---| | 1M uniform over 100M | 4,744 | 974 | 3,437 | 22,194 | 1,632 | 18,907 | | 2,000 clusters of 500 | 354 | 61 | 6,890 | 391 | 65 | 7,498 | | 1M consecutive | 4.8 | 1.1 | 6,979 | 4.8 | 1.1 | 7,873 | | 500k dense in 1M | 113 | 10.6 | 3,482 | 394 | 9.9 | 6,193 | | 10k spread over 1e9 | 819 | 709 | 36.7 | 1,259 | 459 | 125 |

Against native roaring this is pure JavaScript against SIMD, and the gap runs from about 4x on structured data to about 40x on dense unions. That distance is real and I am not going to argue it away: if a native addon is acceptable in your deployment, the addon is faster at everything here.

Against the baseline the picture inverts wherever the data has structure. On clustered data bitrun intersects 19x faster than a merge over sorted arrays and unions 19x faster; on a solid run it is over a thousand times faster, because two runs meet as two intervals rather than as two million members. On uniform data with nothing to exploit it loses to the baseline, by 38% on intersection and 17% on union, and that is the right result rather than a disappointing one: with no structure there is nothing for a compressed representation to win with, and a merge over four-byte members is already close to optimal. The container model is overhead there, and it says so.

When not to use this

Both ends, because a package that only names one is advertising.

Your values are thin and spread over a huge universe. Ten thousand values spread over a billion touch about ten thousand blocks, so the 300-byte-per-block overhead is the entire reading: 2.78 MB against 40,000 bytes for a sorted Uint32Array, which is 70x worse. Below roughly 25 members per block, a sorted array beats every compressed representation in this field on bytes and on set operations. Use one. It is four bytes per member, no bookkeeping, and about twenty lines if you need the algebra.

You can take a native addon and you need speed. This is pure JavaScript competing with SIMD, and the table above is the honest version of that: 4.4x behind native roaring on a solid run, about 5x on uniform and clustered data, 11x on a dense intersection and 40x on a dense union. Run-heavy data narrows it because a run container is a handful of intervals in any language. If a native dependency is acceptable where you deploy, the addon is faster at everything measured here.

Your set is dense and lives in one block. A TypedFastBitSet or a plain Uint32Array bitmap has no container indirection to pay for, and when you only ever need one container, a container model is a tax with nothing to show for it. On the dense workload above typedfastbitset intersects 1.4x faster and unions 4.4x faster than bitrun does. On bytes those two land close enough that I decline to rank them, for the counter reason given further up.

What is left, and what this package is for: sets with structure, in an environment where a native addon is not an option, where you would rather not find out later that the bytes depended on which method you called.

The portable format

serialize writes the portable Roaring layout and deserialize reads it, both byte for byte. The tests assert this against roaring's own output rather than against a second reading of my own understanding: the same bytes in both directions across nine set shapes, including the empty set, values above 2^31 and the very top of the 32-bit range.

Compression is applied before writing rather than left to the caller, because a stream is the thing that outlives the process. For 200,000 consecutive integers, roaring writes 31,400 bytes if nobody told it to optimize and 61 if somebody did. bitrun writes those same 61 bytes without being asked, and roaring reads the file back without complaint.

The reader validates rather than trusts: every bound is checked before it is used, keys must strictly ascend, array values must ascend, runs must not overlap, and a declared cardinality that disagrees with its payload is an error. A parser that assumes its input is well formed turns a truncated file into an out-of-range read and a confident wrong answer, and this one is meant to be pointed at bytes that came from somewhere else.

How it decides

Three representations of one aligned 65,536-wide block, and the choice between them is arithmetic rather than a heuristic:

| representation | bytes | |---|---| | array | 2 per member | | bitmap | 8,192, flat | | run | 4 per run, plus a 2-byte header |

An array beats a bitmap while 2n < 8192, so below 4,096 members. A run container beats an array while 4r + 2 < 2n, and beats a bitmap while r <= 2047. Every container knows its cardinality exactly at all times and its run count exactly on demand, so the decision is three multiplications and a comparison, and it is made continuously rather than when someone remembers to ask.

The run count is recomputed lazily and cached until the next mutation, rather than maintained at every insertion. Maintaining it incrementally costs 74% of insertion throughput on a bitmap container, to save a scan that takes 2.79 microseconds.

Re-examination runs on a doubling schedule over payload cost, not cardinality. Those point in opposite directions and it matters: removing an interior value from a run container splits a run, so the cost goes up while the cardinality goes down. Deleting every odd value from a 30,001-member run leaves 15,001 members in 15,001 runs, which is 60,006 bytes where a bitmap holds the same set in 8,192, and a schedule watching cardinality never fires.

Cost alone cannot schedule a bitmap, because a bitmap costs 8,192 bytes whatever it holds, so a bitmap gets two more rules. Two cardinality tests, which are free, cover the two ends: under 4,096 members an array is cheaper outright, and at 63,490 or above the gaps are too few for the runs to outnumber them by more than one, so a run container is cheaper. The middle band, a bitmap whose members sit in few long runs, is the only case where the run count has to be recovered by a scan, and it gets one every 8,192 mutations. Together those bound the drift the same way the cost rule does: a bitmap never survives more than 8,192 mutations past the point where another representation became cheaper, and never more than 64 past the point where its cardinality alone proves it. The whole branch costs about four nanoseconds per add on bitmap containers and nothing on the others.

Set algebra

One sweep over maximal contiguous stretches serves all four operations, which differ only in a predicate over two booleans. Working on stretches rather than members is what makes a union of two solid runs touch two intervals instead of 131,072 members, and the output interval list hands back the result's cardinality and run count for free, so the result's representation is chosen exactly with no scan afterwards.

Where intervals are the wrong description, they are not used. A pair with exactly one dense bitmap stays in the word domain, because describing a dense bitmap as up to 32,768 intervals in order to merge thirty values into it is a great deal of work to describe something the sparse side barely touches. Two array containers are merged as the sorted member lists they already are, since describing 650 scattered members as 650 intervals only repeats what the members say. Two bitmaps meet as 2,048 word operations, and both counters the result needs come out of that same pass.

The sweep keeps the cases where intervals are the honest description, which is anything involving a run container, where it is linear in the runs rather than in the members they cover.

Correctness is checked against two independent oracles: a plain Set, and roaring itself, across 81 pairs of set shapes times four operations, in both cases.

License

MIT