But on most of my unicode use-cases slower. When you can encode ranges of ints or bools, a simple binary search in such ranges is usually faster than roaring bitmaps.
https://github.com/rurban/libu8ident/blob/master/perf.c
Roaring bitmaps are very interesting implementation. It's a mix of using arrays or bitsets (equivalent would be [1]) depending upon which are more efficient. I've used them in the past, and these are very effective, both for storage and for unions and intersections.
The meaning of bitmap here is essentially "bit array". Roaring bitmaps does a bunch of tricks to e.g. compress long runs of identical bits, which also happens to make bitwise operations a lot faster.
Featurebase[1] is a database based on bitmaps. (Formerly known as Piloasa) I'm not sure if they actually use Roaring Bitmaps [2] or they implemented it themselves. Either way it's based on the idea of compressed bitmaps.
7 comments
[ 5.1 ms ] story [ 37.2 ms ] thread[1]: https://en.wikipedia.org/wiki/Bitmap
[2]: https://en.wikipedia.org/wiki/Bit_array
[1]: https://en.cppreference.com/w/cpp/utility/bitset
[1] https://github.com/FeatureBaseDB/featurebase [2] https://roaringbitmap.org/