LMDB uses 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
Thanks 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.
This 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.
Comments
LMDB uses 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
Thanks 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.
This 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.