The target representation is very memory intensive anyway, but I feel like it would be better to have a specialised implementation to halve the allocation pressure here, since the actual implementation isn't too complicated.

Note that because a concern was mentioned in relation to BitSet, there are no correctness concerns about storing large values because a byte[] can store 8 * ((2^31 - 1) - 2) bits ~ 2^34 > 2^32 - 1 (largest value a RoaringBitmap can store).

BitSet.valueOf copies the array, but the BitSet can be told the max capacity up front, so it may be worth considering a specialised implementation here. It depends which is worse: updating a presized BitSet one bit at a time, or the allocation and the copy. I don't know which is better or worse.

Sorry, I had written up a long description of a thorny issue here which is the most important part of the review, which somehow got lost when "commenting" the review, I'm not sure I can write it out in full again, but tl;dr BitSet does weird things when constructed from long[] containing values >= Integer.MAX_VALUE, which toLongArray() can produce. The impact includes BitSet#cardinality() being correct, but inconsistent with iteration, idiomatic iteration loops throwing exceptions and so on. This can be demonstrated with this code:

            long[] longArray = new long[(Integer.MAX_VALUE >>> 6) + 2];
            longArray[longArray.length - 1] = -1;
            longArray[0] = -1;
            BitSet bitSet = BitSet.valueOf(longArray);
            assertEquals(128, bitSet.cardinality());
            int computedCardinality = 0;
            int next = 0;
            while (true) {
                // will throw at the next iteration after producing -2147483648
                next = bitSet.nextSetBit(next + 1);
                if (next == -1) {
                    break;
                }
                computedCardinality++;
            }
            // will not get here, but this would fail no matter how the loop works around what's above
            assertEquals(bitSet.cardinality(), computedCardinality);

This is apparently already known about: JDK-8311905 but it doesn't appear to be easy to fix, so we need to avoid creating BitSets which behave strangely by checking the last value in the bitmap is < Integer.MAX_VALUE. This can be done by checking the 16th bit of the last key in the RoaringArray is absent.

That's context I wasn't aware of, super useful, thanks. I'll add a check for that to make sure we don't get into trouble. I thought about the signed values, but figured that if you're using BitSet it's for interoperability/speed and you're already under Integer.MAX_VALUE.

I went with the allocation/copy because I wanted valueOf to be fast as possible. I'm using this code already with MethodHandles to get at the bitmap field in my own code. I can add a variant that uses forEach(IntConsumer), it looks like that should be the next fastest approach available.

We're using Daniel's approach for iterating over BitSet because it's about three times faster than the example for nextSetBit even with the array copy (for our use case, our largest bitmap is 7,439 words long):

    public final void bitIndexes(IntConsumer consumer) {
        long[] words = toLongArray();
        for (int k = 0; k < words.length; ++k) {
            long word = words[k];
            while (word != 0) {
                long t = word & Long.lowestOneBit(word);
                int r = Long.numberOfTrailingZeros(t);
                consumer.accept(k * Long.SIZE + r);
                word ^= t;
            }
        }
    }

For reference, you could speed that up quite a lot by replacing the call to lowestOneBit (which isn’t an intrinsic and used quite a few instructions to isolate the bit last time I checked) with just numberOfTrailingZeros, as they are equivalent, then replacing the xor with word &= (word - 1) to unset the lowest bit, which is compiled to blsr on x86.

on the review, yes. I think adding the check and throwing when there is a value too large would suffice.

bitmap.last() can produce a negative int for bitmaps with values >= 2^31, so it should be masked with 0xFFFF_FFFFL and the result should be a long, with minor consequences for the arithmetic below.

Sound like I can address both comments by just bailing if bitmap.last() < 0?

It depends. A long[] has enough bits to store any RoaringBitmap, so it could produce a result here, in which case your arithmetic needs to handle values in the [2^31, 2^32) range. Or you could just check and bail and someone else can add support for larger bitmaps if they really want it down the line.

😍