This is a roaring bitmaps implementation in pure zig. It strives for 100% interpretability with the croaring library that was used as the reference implementation. Performance is comparable to the C implementation.
13 Likes
This looks really nice. Excited to find one. I’ve been wanting to use roaring bitmaps in zig without libc.
Thank you kindly!
This is now pretty much finished pending some API niceties and ergonomics. Features are equivalent to CRoaring. Performance is mostly there (MacOS, yes, still working on Linux/Windows performance tweaks).
This looks very good. In my ECS project I currently heavily use Bitsets for indexing or collision detection with Bitmaps. If I find some time I will give it a try and migrate from ordinary bitset to your roaring bitmaps.
is there a source to read what are they comparing to classic bitmaps?
1 Like
1 Like
A bunch of new stuff now in rawr:
rawr update: 64-bit bitmaps, SIMD kernels, capacity APIs, license
Recent changes -
Roaring64Bitmap. New 64-bit bitmap type, implemented as 32-bit roaring buckets under a 64-bit keyspace. Feature parity with CRoaring’s roaring64: set operations, rank/select, range ops, flip, 32↔64 conversion, bulk-add contexts, statistics, validation. Serialization uses CRoaring’s portable roaring64 format and round-trips against CRoaring in the test suite. Includes Frozen64Bitmap, a zero-copy read-only view.
Array kernels. Array intersection previously galloped unconditionally, which is slow at balanced cardinality ratios. Operations now dispatch between galloping, branchless scalar merge, x86 SIMD, and NEON based on measured crossover thresholds. Outputs are verified bit-identical to the previous kernels, and all changes pass the differential test suites against CRoaring.
Capacity management. initCapacity / ensureTotalCapacity pre-size the container index, shrinkToFit releases unused storage, clearRetainingCapacity supports refill-heavy workloads. Capacity is measured in containers, not elements.
License. Original rawr code is now MPL 2.0.
Cheers!
2 Likes
Nice update. Sounds like a bunch of great features.
Curious how you implemented this. Do all Capacity functions accept a container and modify its capacity or are you reusing containers somehow?
Those are for initializing the number of top level containers if you mean the main ones in the Bitmap struct. They aren’t total bytes or anything since that’s not known ahead of time. They are pretty simple, they don’t re-use anything. They simply make a bigger set of contianers, growing by double if more needed, then memcpy’ing into the newly grown containers. clearRetainingCapacity removes the values but keeps the toplevel index. It sets size and cardinality to 0 too. So yeah, no pools, nothing fancy.
Ah I see. Correct me if i’m wrong. So init/ensureTotalCapacity(N) reserves space in the header for N containers without allocating containers. And clearRetainingCapaicty() frees all containers preserving the header allocation?
Thats similar to what I’ve done. I was wondering if you’ve gone further and reserve/preserve any of the container allocations. Sounds like the answer is no.
I thought at one point it would be useful to re-use containers somehow. But concluded that it was going to be too complex to justify.
Yeah I agree. That seems like a research project better undertaken after it all works . Premature optimization and all. I really like your single allocation containers by the way. That’s on my todo list since I have a couple of functions that aren’t quite at parity with Croaring performance wise so less allocations will help.
Turned out the single allocation idea applied to my current code wasn’t a win. Alloc count alone wasn’t the right cost model - sizing allocs to powers of two was better in my measurements even with twice the number of allocations.