3 ms·

> but we decided to go with RoaringBitmaps to reduce their size Interesting. Could you elaborate on the benefit of this? I've (possibly prematurely) discarde

> but we decided to go with RoaringBitmaps to reduce their size Interesting. Could you elaborate on the benefit of this? I've (possibly prematurely) discarded the notion of using RoaringBitmaps like this because while they use less memory, traversal is and mutation is so much slower using a fixed buffer out of a pool and considering an upper bounded slice of putative results at a time. Although this is for a search engine that typically deals with under-specified queries and is designed for best-effort retrieval given an upper computation time.

Kerollmops 3y ago
> Interesting. Could you elaborate on the benefit of this? I don't know on what I can elaborate. Storing integers that are near each other is much more optimal in a RoaringBitmap than in a flat array. The reason is that it will only store the integers by storing the high part once and the low part in an array or bitmap efficiently. Also we already use RoaringBitmaps on the other end of Meilisearch and converting that to another data structure could take a lot of times.
- marginalia_nu 3y ago
  It's clearly a more succinct representation, but based on my prior experience with these structures it seems like it would come at a not insignificant fee in access costs, and while sometimes they're better, there appear to be many cases where they are not. Don't take this as me questioning your design process or choices, I'm sure they are well motivated, I just think it's a good practice to be curious as to how when someone reaches a different conclusion than yourself :-)
  - Kerollmops 3y ago
    Indeed, there could probably be cases where you see higher deserialization cost than raw lists of integers. But when it comes to high number of integers I can confirm that it is much more efficient.
    - marginalia_nu 3y ago
      Hmm, I should do some benchmarks I guess... Thanks for the datapoints :)

Kerollmops 3y ago

> Interesting. Could you elaborate on the benefit of this? I don't know on what I can elaborate. Storing integers that are near each other is much more optimal in a RoaringBitmap than in a flat array. The reason is that it will only store the integers by storing the high part once and the low part in an array or bitmap efficiently. Also we already use RoaringBitmaps on the other end of Meilisearch and converting that to another data structure could take a lot of times.

marginalia_nu 3y ago
It's clearly a more succinct representation, but based on my prior experience with these structures it seems like it would come at a not insignificant fee in access costs, and while sometimes they're better, there appear to be many cases where they are not. Don't take this as me questioning your design process or choices, I'm sure they are well motivated, I just think it's a good practice to be curious as to how when someone reaches a different conclusion than yourself :-)
- Kerollmops 3y ago
  Indeed, there could probably be cases where you see higher deserialization cost than raw lists of integers. But when it comes to high number of integers I can confirm that it is much more efficient.
  - marginalia_nu 3y ago
    Hmm, I should do some benchmarks I guess... Thanks for the datapoints :)