44 ms·

Roaring bitmaps are compressed bitmaps, can be 100x faster

• genpfault 3y ago
  Not a bitmap[1], but a bitmap[2]. [1]: https://en.wikipedia.org/wiki/Bitmap https://en.wikipedia.org/wiki/Bitmap [2]: https://en.wikipedia.org/wiki/Bit_array https://en.wikipedia.org/wiki/Bit_array
• rurban 3y ago
  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 https://github.com/rurban/libu8ident/blob/master/perf.c
• geon 3y ago
  I still have no idea what they mean by "bitmap". Obviously it is not the same thing as I think of.
  • mrjn 3y ago
    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. [1]: https://en.cppreference.com/w/cpp/utility/bitset https://en.cppreference.com/w/cpp/utility/bitset
  • ravi-delia 3y ago
    They're used to make very compact sets when the number of possible items is relatively small.
  • Doxin 3y ago
    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.
• zcw100 3y ago
  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. [1] https://github.com/FeatureBaseDB/featurebase https://github.com/FeatureBaseDB/featurebase [2] https://roaringbitmap.org/ https://roaringbitmap.org/