New needle_map.CompactMap() implementation for reduced memory usage
#6842
Conversation
This slightly complicates the code, but makes a **massive** difference in memory efficiency - preliminary results show a ~30% reduction in heap usage, with no measurable performance impact otherwise.
|
Could you keep the old compact map implementation and tests in separate files, just for reference and easier comparison. |
As in, |
That would work. Or name it as CompactMapWithOverflow, since Also, the test can have a benchmark to compare the two implementations. |
Done!
I've uploaded benchmark results on #6804 (comment). |
I was thinking about https://pkg.go.dev/testing#hdr-Benchmarks |
I prefer no go build tags for this. You can put it in a sub directory if you don't want to deal with naming conflicts. |
c4cb9af to
6309691
Compare
Done. Note that i still had to tweak a couple lines, as |
What problem are we solving?
#6804
How are we solving the problem?
This PR introduces a new
CompactMap()implementation for in-memory map of needle indices, optimized for memory usage.The idea behind it is replacing the bucket+overflow approach with a map of sorted indices segments, which are in turn accessed through binary search. This guarantees a best-case scenario (ordered inserts/updates) of O(1) and a worst case scenario of O(log n) runtime; notably, memory usage is unaffected by index ordering.
Note that even at O(log n), the clock time for both reads and writes is very low, with
weed benchmarkactually running slightly faster than the existing implementation.The end result is 20-30% improvement in memory usage, compared with v3.89. See #6804 for more details and benchmark results.
How is the PR tested?
Every single existing unit and integration test should pass without issues; the existing API and behavior for
CompactMap()is unchanged.Checks