zroar: A ground-up Roaring Bitmaps implementation in Zig that keeps everything in one flat buffer

Roaring bitmaps are a workhorse data structure for anyone building search engines, columnar databases, or analytics systems that need compact integer sets. CRoaring, the reference C implementation, is already fast — but its design still assumes a serialized format that must be parsed before use. zroar, a new Zig library from Manish R Jain (the creator of BadgerDB and Dgraph), takes a different approach: it makes the in-memory format identical to the serialized format, so opening a bitmap from disk or network is just a pointer cast, not a deserialization pass.

One buffer to rule them all

The key insight is in the layout. Roaring bitmaps split each 64-bit integer into a 48-bit key (high48) and a 16-bit container index. CRoaring stores those keys in an adaptive radix tree, with each container allocated separately on the heap. Reaching a container involves walking the tree and following multiple pointers — a chain of dependent memory loads that can easily miss the CPU cache.

zroar, by contrast, packs everything into a single flat byte buffer. The front holds sorted (high48, offset) pairs; the offset points to the container's location in the same buffer. There are no pointers, only offsets. Reaching a container is a binary search plus one offset add. This design means the serialized form is directly usable for both read and write operations — no parsing, no per-container allocation.

What the benchmarks say

The project includes a ported and expanded version of the CRoaring benchmark suite, comparing against CRoaring 5.0 on a Ryzen 9 5950X. The headline numbers are striking: zroar performs 2x–9x faster (geometric mean) across warm and cold open benchmarks, up to 600x faster on serialization/deserialization, and 4.8x faster on cardinality computations. It wins in 339 of 360 benchmark cases.

The one notable exception is random interleaved insert/remove operations. When a container in the middle of the buffer needs to grow, zroar has to shift all data to its right — think inserting into the middle of an array. CRoaring only needs to expand that one container's memory. zroar mitigates this by proactively moving expanding containers to the end of the buffer and using realloc to avoid memory moves when possible, but it's a fundamental trade-off of the design.

Why it matters

zroar is pre-1.0 (using calendar versioning like 0.2608.0), but it's already proven its concept in Go via sroar. The design principle — making the serialized form directly usable — is language-agnostic and could be applied to Roaring Bitmaps libraries in any language. For developers building systems that store posting lists on disk or send them over the wire, the ability to skip deserialization entirely is a big win. And even for in-memory workloads, the cache-friendly layout appears to help.

That said, it's worth noting that zroar's format is not compatible with CRoaring's frozen or portable formats, and it lacks run containers for compressing long runs of consecutive integers. If you're considering it, the benchmarks and design document are worth a close read — the 600x deserialization speedup is real, but only if your workload actually hits that path.

The project is open source under Apache 2.0, so you can try it out and see if the trade-offs make sense for your use case.