roaring bitmaps are a data structure for storing and operating on large sets of 32-bit integers. they’re used in major systems because of great compression and fast set operations.
this project is quite early with lots to be done. its a little messy still but i think i’m ok with the current design except some regret that i’ve over engineered my WordBitset with comptime options.
just wanted to share incase others are interested in this. human contributions wanted!
i managed to create a workflow on github so that this project’s docs get auto built and deployed. first time i’ve done that with a zig project. was pretty easy to do really. mirroring from codeberg to github for hosting docs and ci doesn’t seem too bad so far.
Thanks for your message. I saw your project was inspired by it to try myself. I’m following your validation strategy. Seems like you’ve covered a good bit of ground in your project. So far I’m somewhere between just porting the c code and trying for something simpler.
Some of my project’s c style memory management has been a bit difficult. I’m currently storing each container type as ptr and cardinality, capacity u32s with to/fromArrayList methods. and that works well.
Also like your project, I’m storing Conatiners as tagged pointers. Since each container has equal size, 128 bits, each is align 16 so the first 4 bits of every pointer will be clear. Though I’m only using 2 bits for 4 tags.
I want to add fuzzing and property based tests soon. I think roaring bitmaps are quite interesting and am enjoying learning about them.
Anyway, I’m curious to know how writing rawr went, what you learned and if you have any advice.
Just added frozen_view() to complete an initial frozen de/serialization cycle .
I think i’m happy now with a single shared allocation which gets cleaned up in deinit(). Better than my first pass with an out pointer the caller needed to free. Here’s how it looks now. And here is deinit.
I’ve struggled before with constructing a MultiArrayList from a buffer. Figured out something that works, seems ok along with MAL.capacityInBytes(). Curious to hear if anyone else has done similar. I’m hoping this will be fast - need start benchmarking soon.
I’ve started over with a more from scratch implementation after realizing previous memory management was a bit of a mess. I was struggling to get a testing.checkAllAllocationFailures() test passing. Now its passing .
I deleted most of my old code. I think I’m happy with this new direction. I’ll still be trying to follow the CRoaring API, but I don’t think porting it was as correct, productive and fun as I’d hoped.
I’m going for more of a PWP style. Right now a Bitmap lives in just 2 allocations, one for a Header - with slices contained in the Header allocated right after the Header bytes. And all container data lives in a single ArrayList(Block).
Much happier with the current deinit(). No more pointer chasing and only 2 free()s.
Neat! Yes I’m definitely interested in exploring use-cases and seeing how it fares in other projects. I’d like to have good text search support. Let me know if you have any requests or find missing features. I’ll gladly work with you to make things fit.
Note that a lot of this progress is only local. Apologies if you went looking for it. Will push to codeberg soon.
Also note that docs/github repo is gone for the moment but should be back soon.
Not too much . It’s basically a rewrite of the c implementation in zig with the same tricks used for performance as the c version. The main thing I learned was that engineering the test harnesses was key to getting the library at parity with and compatible with Croaring. Also, choice of allocator was a make or break for performance. Im using this for another project so it has most of the core features of croaring that I needed. Things not available in rawr that are in croaring are rank/select and lazy n-way compares.
Reaching parity w/ croaring seems to be a lot of work . I’ve made a lot of changes since the message you repsonded to. I’ve gone with a flat, single allocation approach using resizable struct. And I have a couple (passing) testing.checkAllAllocationFailures tests, one which runs on all validations, which are similar to your project’s validations. And one which runs on all cases from fuzz-crash-corpus.zon where I’ve been accumulating crashing / failing inputs. I have a decent amount of FuzzOps which are checked against croaring (or std.ArrayHashMap with AFL) but not anywhere near 100% coverage. I ran into issues building an AFL fuzz exe with croaring included. So I resorted to fuzzing against a hash map there instead.
Still lots of ground to cover. But it feels like I’m making decent progress now after a couple early design reworks. I like the flat memory layout I’m using and hope it’ll result in competitive benchmarks. Although I’m skeptical. I think I’m doing too much copying when inserting. And haven’t settled on a plan for reusing container memory aside from telling users to shrink_to_fit often .
I’ll get there eventually. For now I’m enjoying working on this project and focusing on coverage and correctness.
Did you implement inplace and _cardinality variants of and/or/xor/andnot too? Thats been a decent amount of work. And by ‘n-way compares’ I guess you mean stuff like or_many?
Also, did you do any benchmarking with zig 0.16? I guess auto-vectorization has regressed for this release cycle so you might notice some slowdown vs 0.15.2.
Yes I’m definitely interested in exploring use-cases and seeing how it fares in other projects. I’d like to have good text search support. Let me know if you have any requests or find missing features. I’ll gladly work with you to make things fit.
ZRoaring includes everything except these two. There is and, but the inplace variant isn’t done yet. I think to_uint32_array might be straightforward to implement. I’ll try to get to these soon and let you when done.
I’m interested to see how it compares with with CRoaring. Know that I haven’t gotten to benchmarking yet. I’m planning do some benchmarking soon. Maybe within the fuzzer so as to bench individual operations (FuzzOps).
I’ve added to_uint32_array and and_inplace if you want to try it out. The project is young so please feel free to suggest changes to API, docs or anything else you might notice needs polish. If you’re searching for examples, start in validate.zig or fuzz.zig.
As I mentioned, I haven’t started with benchmarking yet and I expect we’re slower than CRoaring in many cases. AVX512 is a TODO along with several AVX2 methods (including one used by and_inplace called intersect_vector16 i think).
I’ve done some initial benchmarking. Looks like we’re going around 75% of CRoaring’s speed overall on this ReleaseFast benchmark with x86 / AVX2. We’re competitive on many of the individual ops. This benchmark uses ops from fuzz-crash-corpus.zon as input. There are a handful of ops which are between 50-70% of CRoaring’s speed. Hope to improve those soon.
I’ve generated some random values for minimum, maximum and contains* ops. They’re excluded from the corpus due to not usually being part of crash reproductions and I wanted to include them here.
One thing I should mention: users should consider calling shrink_to_fit() or run_optimize() before doing expensive operations, especially when many allocating operations have been performed. These may leave ‘holes’ of uninit (0xFF) blocks in the Bitmap and I haven’t yet decided on a strategy for efficiently reusing them. I imagine having all blocks closer together in memory might make up for shrink_to_fit’s cost of reallocating and copying memory in some scenarios. Not sure though. I recommend to benchmark and experiment.
Updated benchmarks show a small improvement from last time. Notable benchmarking change: last time was only a single pass: croaring, zroaring. Now were doing 5 loops of croaring, zroaring. This seems to be a little more stable, maybe negating some variation from warmup. Also, the bench output is a little more concise and hopefully easier to read.
@xsawyerx I’m hoping we’re competitive with CRoaring in your benchmark as and_inplace has improved since last time along with some other general stuff. Curious to hear how it goes.
Of course, stills lots of room for improvement. Currently we’re seeing a big slowdown due to excessive copies needed with our flat layout. I’m leaning towards moving block storage into a separate allocation to avoid that or something.
I finally got around to writing the adapter to benchmark both,
Here’s what I got for you, using commit ID 5dd51c27b247a08e32a759d865788df7b6b6fb39:
It’s producing identical blob bytes (7,132,323), identical profile counters (postings, candidate sets after text/tag/date) on every query variant (CRoaring/ZRoaring). So hey, it’s a proper drop-in replacement in accuracy!
Working on 50K docs, 1K queries:
metric | CRoaring | ZRoaring
------ | -------- | --------
build | 588 ms | 592 ms
deserialize | 557 ms | 586 ms
common text | 266 ms | 226 ms <- Yay
rare text | 3.72 ms | 3.73 ms
date only | 203 ms | 224 ms
text+tag+date | 205 ms | 182 ms <- Yay
This is also just single run, so.. not the most accurate. For proper benchmarking comparison, I’ll need initial runs, multiple runs of the test, removing outliers, aiming for accuracy level, etc. Too lazy to do that right now, sorry.
Some issues with wasm32. I’ll try to provide a patch for that upstream. I was able to get it to build (but I want to clean it up before submitting it upstream), and CRoaring 91KB, ZRoaring 124KB. (Not sure how much it matters.)
Glad to hear a positive report about correctness. And the benchmark looks similar to what I’ve been seeing.
I’m not surprised wasm32 didn’t build. I haven’t tried any wasm builds yet. Patch would be appreciated! Is 124KB a release fast build? Maybe we can try to get the size down somehow.
No worries about less than ideal benchmarks. Glad to hear a report. I know the one i’ve been sharing has room for improvement too.
I’ve made more progress on benchmarks today. Around 90% of CRoaring’s overall speed now locally by keeping blocks in a separate allocation. So the longer you put off your benchmarking gives me more time to fix my code .
.
. I’ve been focusing on correctness, and fuzzing each commit extensively with the zig fuzzer and with AFL++.
. I’ve made a lot of changes since the message you repsonded to. I’ve gone with a flat, single allocation approach using resizable struct. And I have a couple (passing) 
.
ops which are between 50-70% of CRoaring’s speed. Hope to improve those soon.