RoaringBitmap / RoaringBitmap/roaring
Optimize generating many bitsets for serialization
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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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