Bitmap size is limited to 2^32 elements

[cym13]

Bitmap size is limited to 2^32 elements. Adding more elements will cause integer overflow of the length.

Test (quite long to run):

import roaring.roaring;

void main() {
    auto map = new Roaring;
    long limit = (cast(long) uint.max) + 1;

    for (long i; i<limit ; i++)
        map.add(cast(uint)i);

    assert(map.length == 0);
}

This is not directly an issue with the D wrapper but with the underlying C library (see RoaringBitmap/CRoaring#1). I choose however to open an issue nonetheless because that overflow happens without any safeguard or warning and isn't documented anywhere.

[yuce]

uint data type is 32 bits in D, so uint.max == 2^^32. I thought that the function signatures would be adequate to convey that the maximum supported value is 2^32. Also uint overflows without warning. There is this https://dlang.org/phobos/std_experimental_checkedint.html module in the standard library to check overflow, don't know how that would affect the performance though. I didn't run any benchmarks against this library yet, so it would be better to wait until that is done.

I'll add 64 bit support soon, but until then it's a good idea to feature this limitation more prominently in the readme.

[cym13]

Honnestly, everything was working smoothly and I absolutely didn't expect it to be limited to as little as 2^32 so I didn't even thought of reading the code and checking the signature.

On one hand it was bad practice on my part, but on the other hand I can't imagine being the only one surprised. In that regard I think mentionning that you're planning to add support for 64 bits in the readme would be great.

[yuce]

I see. I've added the limitations section to the README, to make 32bits limitation more prominent.

If you don't mind me asking, how are you using this library? E.g., do you store IDs in a bitmap?

[cym13]

I needed to run some statistical cryptographical tests and specifically needed to count uniquely more than 2^32 elements. As no normal array would be practical I tried using phobos' bitarray but hit a codegen bug, and found this library right after.

Now, no production relies on this, but I still specifically needed more than 2^32 elements (it's okay now, I worked arround that limitation).

[yuce]

Thanks. I'll leave this ticket open until we have 64bit bitmaps support for this library.