RoaringBitmap / RoaringBitmap/roaring

Optimize generating many bitsets for serialization

Open
#365 8 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Go
Stars
2.9k
Forks
262
Avg merge
2h 34m
Merged PRs (30d)
8

Description

One of our heaviest workloads uses this library to index a lot of ingested data in real time. In one part of the workload we basically have dozens of goroutines doing something like the following in a loop:

postings := roaring.NewBitmap()
for _, thing := range things {
    postings.Clear()
    for _, row := range $MATCHING_ROWS {
        postings.Add(row)
    }
    postings.WriteTo()
}

We've already heavily optimized the code that generates things to be very efficient and avoid allocations/pointers, however, when its time to actually serialize the index we're building we have to go through this library and it allocates like crazy even though we're trying to reuse a single datastructure.

I've provided a benchmark that demonstrates this along with some improvements in this P.R: https://github.com/RoaringBitmap/roaring/pull/364

I realize that adding pooling of internal datastructures may be a big change, but I tried to structure the P.R so that its completely "opt in" via the new ClearRetainDatastructures() API.

EDIT: I can't provide screenshots of profiling for obvious reasons, but I just went back and checked and the allocations removed by this P.R represent ~ 56% of all allocations in our workload so this will have a very substantial performance impact for us (and others I expect who use the new API).

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the benchmark and improvements described in PR #364, then trace the bitmap Clear(), Add(), and WriteTo() path used by the serialization loop. Check how the proposed ClearRetainDatastructures() API affects allocations, and use the benchmark to verify that the opt-in reuse behavior delivers the intended reduction.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.