Skip to content

Avoid unnecessary container allocations #105

Open

Description

@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.

Activity

  1. lemire commented on Mar 30, 2018

    @lemire
    MemberAuthor

    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++
    }
    
  2. fjorgemota commented on Jan 11, 2019

    @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?

  3. lemire commented on Jan 11, 2019

    @lemire
    MemberAuthor

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

  4. fjorgemota commented on Jan 11, 2019

    @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. :)

  5. damnever commented on Aug 15, 2023

    @damnever
    Contributor

    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.

  6. damnever commented on Aug 16, 2023

    @damnever
    Contributor

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

  7. tamirms commented on Sep 17, 2026

    @tamirms
    Contributor

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions