8 ms·
LMDB uses https://git.burd.me/greg/sparsemap https://git.burd.me/greg/sparsemap for storing compressed ranges of bitmaps for their page allocator, similar to Ro
by chc4 2y ago
LMDB uses https://git.burd.me/greg/sparsemap https://git.burd.me/greg/sparsemap for storing compressed ranges of bitmaps for their page allocator, similar to RoaringBitmap or Linux's fdarray, which might be applicable here. With compressed bitmaps finding the next free is cheap. If your ranges are very sparse then it will have bad performance, however
- grovesNL 2y agoThanks for the suggestion! I tried dense bitsets in an earlier iteration but the performance wasn't great, so I thought something like RoaringBitmap probably wouldn't work out very well. The ranges are relatively dense but there also aren't that many of them (only a few thousand or so), so the bitset seemed to spend a huge amount of time searching within elements.
- chc4 2y agoThis sparsemap uses essentially run-length encoding so it might still have slightly better performance. I think RoaringBitmap only uses the list of set bits below <1024 before it uses the compressed representation which you'd be over, and then having to do the compressed scan.