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
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.