> It would definitely compress much better than roaring bitmaps. In terms of performance, it depends on the access patterns. If very sparse (large jumps), PEF would likely be faster, if dense (visit a large fraction of the bitmap), it'd be slower.
Just for clarification you mean the access pattern is sparse and not the data itself? How is that relevant?
I did part of the investigation and implementation, but didn't look much into elias fano coding.
The select for the dense codec is already really fast (with popcount), there's not much room for improvement on the instruction side (https://godbolt.org/z/dq7WeE66Y), except implicitly by touching less memory.
The sparse codec with its binary search should be easy to beat though. Partitioned Elias-Fano indexes may be a superior choice in contrast to the sparse codec in terms of rank and compression, and probably less so for select and code complexity.
Just for clarification you mean the access pattern is sparse and not the data itself? How is that relevant?
I did part of the investigation and implementation, but didn't look much into elias fano coding. The select for the dense codec is already really fast (with popcount), there's not much room for improvement on the instruction side (https://godbolt.org/z/dq7WeE66Y), except implicitly by touching less memory. The sparse codec with its binary search should be easy to beat though. Partitioned Elias-Fano indexes may be a superior choice in contrast to the sparse codec in terms of rank and compression, and probably less so for select and code complexity.