3 ms·
Heh, I like the tagline: "Grab one of our research papers". It's very readable, too! https://arxiv.org/pdf/1603.06549.pdf https://arxiv.org/pdf/1603.06549.pdf
by sillysaurusx 6y ago
Heh, I like the tagline: "Grab one of our research papers". It's very readable, too! https://arxiv.org/pdf/1603.06549.pdf https://arxiv.org/pdf/1603.06549.pdf
Looks like the last active discussion of Roaring Bitmaps was 6 years ago: https://news.ycombinator.com/item?id=8796997 https://news.ycombinator.com/item?id=8796997 possibly when it was first introduced. Interesting comments!
> How do these compare space and performance wise with Judy arrays, which are 256-ary trees whose nodes also distinguish between sparse and dense subsets? https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array
Good question, since the patent on them won't expire until Nov 29, 2020.
Judy arrays seem to be much less known. Looks like today will be Datastructure Thursday; lots of neat stuff to dig into.
- twic 6y agoThe showstopper with Judy arrays, for me, was that they require a lot of hairy fine control over memory layout to implement (it's been years since i looked at this, so please excuse the lack of detail). You can do that in C, but not in no-sharp-edges languages like Java, which i was using at the time. It would even be quite a headache in Rust. It doesn't help that the documentation is very weird.
- nicoburns 6y agoThere is an implementation of Judy arrays in Rust: https://github.com/adevore/rudy https://github.com/adevore/rudy Not sure how complete / usable it is.
- twic 6y agoThe docs say it's largely complete. As an example of a headache, one node type in Judy has a count, followed by that many index bytes, followed by the same number of pointers. In Rust, that would naturally be a struct with two variable-sized fields, which isn't possible, so it's done by defining a struct generic over a pair of array types: https://github.com/adevore/rudy/blob/300f2cc7842f6329a76fff012056f54bf6a37424/src/util/locksteparray.rs#L81 https://github.com/adevore/rudy/blob/300f2cc7842f6329a76fff0... It looks to me like this is only ever instantiated for 2, 7, or 31 elements, whereas i think for original Judy, it can be any size up to 31 elements (maybe?). Handling a genuinely variable length in Rust would be rather gnarly, because there have to be different types for each length.
- quicknir 6y agoI would assume that within unsafe you could simply do the same kinds of shenanigans you would do in C++, e.g. you have a fixed size struct that is just the "header", it's only created on the heap, and it's immediately followed by the variable amount of data which you get access to by casting. If you couldn't do this in unsafe rust this seems like a pretty huge limitation.
- steveklabnik 6y agoYes, you could.
- c0l0 6y agoI used to work at a small-ish (but very profitable) European company whose "crown jewel", in terms of in-house developed technology, was a distributed in-memory search/database engine, written in hand-crafted, multi-threaded C by a true coding wizard and industry veteran. It used Judy arrays at its heart for the very first filtering/processing stage of queries, and did so to amazing effect. It's quite spectacular what you could and can do with libjudy if you use it wisely :) I always wondered if relatively recent changes in x86 CPU µarchs broke some of the assumptions that made libjudy perform this great even on Pentium-class hardware, and if the de facto only complete implementation (that I happen to be aware of) could be improved as a consequence, if those changes (i.e., hugely increased cache sizes, etc.) were considered.
- Bootvis 6y agoWhat were you working on?