What Happens When Bitmap Boundaries Listen to the Data?

In our earlier post, we described the limitations of fixed-boundary bitmap indexing: uniform 2^16 partitioning that ignores data topology, containers that don't know their own density, and no mechanism for thermal adaptation. We asked whether a density-aware bitmap could do better.

This post is the answer. We ran Criterion benchmarks on every core operation, comparing Diatom Bitmap against roaring-rs (the canonical Rust implementation of Roaring Bitmap). The results are not uniformly favorable. That's why they're worth reporting.

Set operations are the hot path for bitmap indexes in analytics engines. Every query in Apache Druid, Apache Pinot, or ClickHouse that combines filter predicates runs AND, OR, or ANDNOT across bitmap indexes.

The pattern is consistent: Diatom has fixed overhead at small sizes (1K), reaches parity around 10K, and pulls ahead at 100K. The gap widens with scale.

Cardinality is O(1) in Diatom (a cached value at the bitmap level) versus O(containers) in Roaring. The result stays in a tight sub-nanosecond band across the tested sizes:

At 100K, cached cardinality is 0.47 ns versus 1.25 ns, or 2.7x faster.

Iteration is no longer a decisive headline win, but it remains competitive. Bitmap containers iterate over u64 words using trailing-zeros extraction. Array containers iterate sorted u16 slices. In the current implementation that is enough to edge out Roaring at 1K and 100K, but not at 10K:

At 100K, iteration is 317,377 ns versus 357,463 ns, or 1.1x faster.

Serialization uses a compact binary format (magic: DBTM). At 10K, Diatom serializes 8.5x faster than Roaring:

At 10K, serialization is 211 ns versus 1,792 ns, or 8.5x faster.

contains() hit path at 100K: 2.2x slower after the integrity fix. This remains the clearest standalone regression, but it is no longer the catastrophic 7.6x story the old draft carried. A March 20, 2026 investigation found that the earlier 100K result was being inflated by a boundary-range correctness bug. After fixing that path, the standalone contains() penalty remains real, but it is now closer to the cost you would expect from explicit boundary lookup plus in-container search.

On present values at 100K, Diatom takes 463,569 ns versus Roaring's 208,302 ns, or 2.2x slower.

The corrected 100K result still says the same qualitative thing: Roaring is better for standalone point lookups. It no longer supports the stronger claim that Diatom falls off a cliff at scale on this path.

Miss-path contains() is milder at 100K: 228,482 ns versus 138,958 ns, or 1.6x slower.

from_sorted(): 3.7-5.8x slower. Constructing a Diatom Bitmap from sorted values runs a density histogram followed by valley detection to place boundaries. Roaring just distributes values into fixed 2^16 containers. The boundary placement algorithm is the cost of adaptivity. It's O(n) but with a higher constant factor.

At 100K, bulk construction is 2,495,236 ns versus 429,623 ns, or 5.8x slower.

Insert: 1.8-2.3x slower. Each insert must locate the correct container via boundary lookup and potentially update density metadata. The overhead is constant per operation and doesn't grow disproportionately with scale.

These are real costs. Whether they are acceptable depends on your workload. If your hot path is set operations on aligned bitmap families, Diatom has a real case. If your hot path is one-off point lookups (contains) or bulk construction, Roaring is the better choice today.

Roaring uses fixed 2^16 boundaries. Every 65,536 consecutive values get one container. The container count scales linearly with value range, regardless of data distribution. Dense regions and sparse regions get the same treatment.

Diatom uses density-derived boundaries. The boundary placement algorithm runs a histogram over the value space and detects valleys in the density distribution. Dense regions get fewer, larger containers. Sparse regions get many small containers or none at all. At 100K sequential values, Diatom coalesces data into fewer containers than Roaring, with each container holding more values. Fewer containers means fewer loop iterations in set operations, fewer cache misses, and fewer function calls.

What scales is not a blanket “better bitmap” claim. What scales is the aligned set-operation path. At 1K, both approaches produce a handful of containers and Diatom's fixed overhead dominates. At 100K, aligned set work benefits from fewer effective containers and cached metadata. But standalone membership and construction still lose, and fixed-floor remains the honest standalone baseline inside Diatom itself.

We now know more precisely what the benchmark suite does and does not support. Diatom is not yet a general Roaring replacement. It is a more specific research primitive: adaptive morphology with a fixed-floor baseline and a plausible family-level wedge when related bitmaps share structure.

That is still worth studying. It is simply a narrower and more honest claim than the original draft.