replace c-roaring bitmaps with rust-only bitmap implementation

[yeastplume]

CRoaring continues to be a major annoyance with its dependencies, and I've had some feedback that it's causing major issues trying to create libs for mobile wallets.

Some Possibilities:

• https://docs.rs/bitmap/3.1.3/bitmap/
• Roll our own (given we're probably only using a smallish subset of c-roaring functionality)

Of course, performance is going to be an issue. I can't say I've delved into croaring too deeply, so any thoughts/opinions here are welcome.

[antiochp]

Related - https://github.com/mimblewimble/grin/issues/1264 (clang and bindgen discussion).

[hashmap]

More annoying it limits us to 32 bits. I'd suggest t start from prioritizing the requirements - portability, minimizing dependencies, performance, compression, scalability etc

[rrybarczyk]

What are the performance requirements here? We could use the rust bitmap crate, but it only supports dense bitmaps. Is this acceptable?

Would it be an option to switch to the bitmaps crate as a short term solution while a new rust crate was being developed that more closely matches the croaring library functionality?

[sesam]

There's the roaring crate. repo here. It's meant as pure rust replacement for CRoaring. It implements Bitmap at least partially, and this repo only uses croaring::Bitmap (grep -r croaring) for now. But roaring::Bitmap is lacking instance methods that croaring::Bitmaps have, for instance .add (in pow/cuckatoo) and .flip_inplace (in pow/lean). Some methods I didn't find by by grepping the roaring-rs source might be implemented as Traits

[antiochp]

@sesam We looked into roaring (vs. croaring-rs) when we first started looking at using bitmaps. The repo hasn't been touched in almost 2 years.

[rrybarczyk]

@antiochp is your preference to have a new rust bitmaps library over using the repo linked in this issue (https://docs.rs/bitmap/3.1.3/bitmap/) if so, do you want an api that directly mimics the croaring library? which functions are the top priority?

@sesam are you interested in collaborating together on this?

[antiochp]

The bitmap lib is intended for small dense bitmaps.

A dense bitmap, intended to store small bitslices (<= width of u64).

We need to be able to efficiently handle bitmaps with millions of values in them. And these bitmaps may have both very sparse regions and very dense regions in them.

For example - we use a bitmap to maintain the positions of all unspent outputs in the entire TXO set.

The issue is less around API compatibility with croaring and more around the necessity of an actual "roaring bitmaps" implementation.

[sesam]

Longer term, we could revive https://github.com/Nemo157/roaring-rs and PR or fork to add the minimal methods and test cases to be usable in grin. @rrybarczyk I did git clone the source and started grepping a bit... PM me on gitter when you're around :). Likely more marathon than a hackathon. But surely faster than rolling our own.

For regular users we can recommend our docker image that should build everything reliably.

For mobile, maybe for now investigate if anyone else has a solution to croaring on ios & android. Or we open an issue or ask croaring's devs.

[yeastplume]

I think after discussion this is a bad idea, and given we're doing binary releases now the issues with compilation only need to be dealt with by developers.