Avoid unnecessary container allocations

[lemire]

In many instances, especially when computing intersections, we generate empty containers that are immediately garbage collected.

There are clever tricks we could use to start scanning the input containers, advance up to the point where there might be values to be intersected, and bail out without generating an empty container if the intersection is empty.

[lemire]

Example:

c1 := rb.highlowcontainer.getWritableContainerAtIndex(pos1)
c2 := x2.highlowcontainer.getContainerAtIndex(pos2)
diff := c1.iand(c2)
if diff.getCardinality() > 0 {
	rb.highlowcontainer.replaceKeyAndContainerAtIndex(intersectionsize, s1, diff, false)
	intersectionsize++
}

[fjorgemota]

hmmm When I read this issue I was thinking about reusing containers, which would may help here too.

I mean, when roaring decides to automatically optimize a container (like on iAddReturnMinimized method, for example), it discards the old container without any chance to reuse it in the future, so on a dynamic environment, if someone calls Remove on that same bitmap the recently created container is, again, downgraded to the old container, which is allocated again without reusing the old container and increasing GC pressure.

Personally, I think reusing a container could help here too. Yeah, the algorithm you suggested could probably be better for the intersection case, but in cases where adding/removing integers to the bitmap causes a bunch of containers to be allocated and deallocated it could be interesting to reuse containers directly in the library, internally.

So what I suggest is: arrayContainerPool for arrayContainer, bitmapContainerPool for bitmapContainer and, of course, runContainerPool for runContainers. And then, instead of just returning the new container and discarding the old container, we just clear() the old container, put in the pool and, when allocating the container, just get the correspondent container of the pool. So it's a more generic option to improve performance while avoiding container allocations when adding and removing elements from the bitmap.

What do you think?

[lemire]

@fjorgemota Yes, this is sensible, but one would like to see actual performance gains in realistic scenarios.

[fjorgemota]

Oh, for sure. Only benchmarks to test these sort of things. And for sure no-allocation (like in the algorithm for intersections) is always better than one allocation here and there using pools. :)

[damnever]

I have observed high CPU usage caused by the memory allocations when using Bitmap.ReadFrom and bitmap.Or/Clone frequently. By implementing memory reuse, we should be able to effectively resolve the majority of this problem.

[damnever]

I have submitted a pull request to resolve the issue with ReadFrom #395

[tamirms]

There are clever tricks we could use to start scanning the input containers, advance up to the point where there might be values to be intersected, and bail out without generating an empty container if the intersection is empty

@lemire I have applied this technique in 2 PRs and the results are promising!

#566 counts the result before allocating it in runContainer16.andBitmapContainer and bitmapContainer.iandRun16, and runContainer16.intersects now returns at the first shared value instead of computing the whole intersection just to find out whether it is empty.

• empty And: 8 KB → 104 bytes, 5x faster
• in-place And: zero allocations
• Intersects on disjoint containers: zero allocations, 25x faster

#572 carries the same idea into FastAnd with three or more inputs: the input with the fewest containers drives, and a key is probed for a shared value before any containers are intersected, so a key with nothing in common allocates nothing.

• real-data whole-dataset intersection: 43 allocations → 2, 30x faster
• pairwise non-empty but jointly empty: 33 KB and 18 allocations → 80 bytes and 1

Both are ready for review.