zroar: Serialized Roaring Bitmaps in Zig
zroar is a re-implementation of the popular Roaring Bitmaps data structure. It differs significantly in how the typical roaring bitmap libraries are designed. For example, the most popular CRoaring library uses complex adaptive radix tree to store the high48 bit keys, allocating memory per array or bitmap container, requiring a serialize step to convert the in-memory format to byte array to store on disk.
zroar, OTOH, uses a single byte buffer to store both the keys and the containers, hence the name ‘serialized’. This single design change not only eliminates the serialize/deserialize step, it also performs much better in ‘warm’ operations where the bitmap is already in its in-memory format. This is because keeping a serial buffer allows for much better cpu cache locality.
This simple design, along with Zig native SIMD operations, results in a much simpler (~2000K lines of zig code for main logic, compared to 17000 LOC for CRoaring’s 64-bit version) and much more performant library. zroar has no serialize, deserialize step, because the in-memory format IS THE on-disk and over-the-network format.
zroar outperforms CRoaring 2x - 9x (geometric mean) across various benchmarks, performing better than CRoaring in 339 out of 360 tests.
This was inspired by my (and my team’s) previous work at Dgraph Labs, where we had to deal with Go’s garbage collector, which was consistently OOMing under the memory pressure. That lead me to spend a lot of time thinking about ways to reduce small memory / object allocation, and prefer bigger byte-buffer allocations. That resulted in sroar (serialized roaring bitmaps in Go). zroar is a natural successor to sroar, but in Zig.
I’m planning to use zroar in a new database project I’m working on, written in Zig (still a few months away before it’s ready to release). I chose Zig because I just like the simplicity of the language. And coming from Go, which I also chose because of simplicity, I feel Zig is the natural next step for a Go developer (particularly one like me, who’s traumatized by garbage collectors).
Right now, zroar only supports 64-bit integers (I don’t have a need for 32-bit ints yet), and doesn’t support run containers (also don’t need yet).
Supported Zig versions
v0.16
AI / LLM usage disclosure
zroar is built using AI tools. I’ve been coding for over 20 years now. I use AI tools to speed up development, but I do have a personal policy of being anal about code quality. As such, I tend to use them in manual mode, reviewing code throughly and iterating endlessly until I am happy with the code readability, quality, performance, and functionality of the code.