Optimize the implementation of OrCardinality

[lemire]

Currently, the OrCardinality function materializes temporary containers that are immediately (?) garbage collected. This is wasteful. Instead, we should have fast container-to-container union functions that just return the cardinality without doing memory allocation, as is the case with the intersections.

roaring/roaring.go

Line 416 in db18267

// TODO: could be faster if we did not have to materialize the container

c.c. @tgruben @statik @bpot @tvmaly

[statik]

@lemire I started taking a look at this and got a little confused. I'll list out what I found, and just say there is a good chance I'm missing something and would greatly appreciate any pointers on what operations are still missing here.

https://github.com/RoaringBitmap/roaring/blob/master/setutil.go#L211 has intersects2by2. Not sure if the 2by2 suffix is correct, when comparing https://github.com/RoaringBitmap/RoaringBitmap/blob/50d435c5f82df78b5d369f4120559e10c3455e95/src/main/java/org/roaringbitmap/Util.java#L680

intersects2by2 is called from

roaring/arraycontainer.go

Line 647 in b747b1b

return intersects2by2(

which seems similar to the way it is used in java https://github.com/RoaringBitmap/RoaringBitmap/blob/78ad3a1c11e374e471e4fc666257569269447412/src/main/java/org/roaringbitmap/ArrayContainer.java#L573

I also see OrCardinality, AndCardinality, and Intersects implemented herev in the public API:

roaring/roaring.go

Line 387 in db18267

// OrCardinality returns the cardinality of the union between two bitmaps, bitmaps are not modified

roaring/roaring.go

Line 441 in db18267

func (rb *Bitmap) AndCardinality(x2 *Bitmap) uint64 {

roaring/roaring.go

Line 488 in db18267

func (rb *Bitmap) Intersects(x2 *Bitmap) bool {

[lemire]

@statik I'll get back to you.

[lemire]

@statik

Not sure if the 2by2 suffix is correct

It means that we take the intersection of two sets... as opposed to intersecting 3 sets, and so forth. Arguably, the 2by2 suffix is unnecessary but that's a private function.

[lemire]

@statik

Ok. So the current status of this issue is that it is all implemented except that the OrCardinality function materializes the temporary containers needlessly.

roaring/roaring.go

Line 416 in db18267

// TODO: could be faster if we did not have to materialize the container

I'll update the issue description to avoid confusion.

[lemire]

@statik

Done. Let us hope that things are clearer now. Thanks for the feedback.

[statik]

@lemire thanks! this makes sense. I hope to find some time to work on this.

[lemire]

@statik Please do. And, also, if you do, don't forget to throw in extra tests for good measure!

[lemire]

Resolved as of this commit 8a91ca4