Roaring bitmaps: what they are and how they work • Hacker News Board

Re: Roaring bitmaps: what they are and how they work

#41

Post by jpgvm » Sun, Sep 04, 2022, 2:41 AM UTC

froh wrote: post #18

nullc wrote: post #5

Those who do not know judy1 are doomed to reinvent it. http://judy.sourceforge.net/

which possibly is a good thing the Judy project seems inactive to me: https://sourceforge.net/p/judy/bugs/ this short HN thread resonates with the intuition of jude1 being stalled, it's last optimistic comment points to an orphaned comment in the big list above https://news.ycombinator.com/item?id=32188204

It's certainly not active but perhaps could be revived now that the patents have expired (filed in 2001 so expired last year).

On the surface it's just a very optimized 256-ary radix trie. I think it would take some software archeology to determine if there was more to it than that and if it's assumptions still hold on todays processors.

Re: Roaring bitmaps: what they are and how they work

#42

Post by zibby8 » Sun, Sep 04, 2022, 3:02 AM UTC

TacticalCoder wrote: post #9

> When a set is sparse, traditional bitmaps compress poorly. They waste space. But if you were to compress them, they'd compress very well. As in, for example, if you were to compress them using roaring bitmaps.

If you compressed them using some naive scheme, they would be smaller but they would lose their fast set-wise operations like lookup and union.

Re: Roaring bitmaps: what they are and how they work

#43

Post by anonymoushn » Sun, Sep 04, 2022, 3:47 AM UTC

celeritascelery wrote: post #3

I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics. Often they involve specific knowledge of the hardware instead of treating software as abstract. To me this is the big difference between “computer science” and “computer engineering”.

timsort and pdqsort seem to be significantly slower than radix sort for random inputs, but presumably radix sort could also benefit from a pile of pattern-finding heuristics.

Re: Roaring bitmaps: what they are and how they work

#44

Post by nullc » Sun, Sep 04, 2022, 3:53 AM UTC

latchkey wrote: post #12

nullc wrote: post #5

Those who do not know judy1 are doomed to reinvent it. http://judy.sourceforge.net/

http://nothings.org/computer/judy/

Not applicable to this subject. :) A comparison between judy1 and roaring would be interesting.

Re: Roaring bitmaps: what they are and how they work

#45

Post by nullc » Sun, Sep 04, 2022, 3:54 AM UTC

froh wrote: post #18

nullc wrote: post #5

Those who do not know judy1 are doomed to reinvent it. http://judy.sourceforge.net/

which possibly is a good thing the Judy project seems inactive to me: https://sourceforge.net/p/judy/bugs/ this short HN thread resonates with the intuition of jude1 being stalled, it's last optimistic comment points to an orphaned comment in the big list above https://news.ycombinator.com/item?id=32188204

Does it need to be active? It's done and it works.

It's not written in an highly unstable language. The safety of every bridge you drive over was probably partially validated using fortran numerical code from the 1980s.

Re: Roaring bitmaps: what they are and how they work

#46

Post by eesmith » Sun, Sep 04, 2022, 4:15 AM UTC

anonymoushn wrote: post #43

celeritascelery wrote: post #3

I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics. Often they involve specific knowledge of the hardware instead of treating software as abstract. To me this is the big difference between “computer science” and “computer engineering”.

timsort and pdqsort seem to be significantly slower than radix sort for random inputs, but presumably radix sort could also benefit from a pile of pattern-finding heuristics.

timsort and pdqsort (two comparison sort methods) and radix sort (a non-comparative sorting algorithm) have different albeit overlapping domains of applicability.

Given a large number of 32-bit integers, radix sort is indeed significantly faster.

While I would reach for a comparison sort method if I had a large number of arbitrary-length Unicode strings, which I wanted to sort in a case-ignoring order.

Also, I found timsort faster than radix sort when there was a small number (as I recall, <100 or so) of elements.

Re: Roaring bitmaps: what they are and how they work

#47

Post by jasonwatkinspdx » Sun, Sep 04, 2022, 4:28 AM UTC

froh wrote: post #18

nullc wrote: post #5

Those who do not know judy1 are doomed to reinvent it. http://judy.sourceforge.net/

which possibly is a good thing the Judy project seems inactive to me: https://sourceforge.net/p/judy/bugs/ this short HN thread resonates with the intuition of jude1 being stalled, it's last optimistic comment points to an orphaned comment in the big list above https://news.ycombinator.com/item?id=32188204

Judy arrays have never been particularly compelling, but for some reason gained huge mindshare among programmers on Slashdot.

Today it'd make much more sense to implement ART, which is dramatically simpler.

Re: Roaring bitmaps: what they are and how they work

#48

Post by ww520 » Sun, Sep 04, 2022, 4:36 AM UTC

ww520 wrote: post #35

Xeoncross wrote: post #10

Can someone explain how this is laid out in memory and what it would look like serialized? It's easy to have an array of N size that fits all bits and just write to disk. You can also mmap a file as a large array of bytes and just mutate it and let the OS handle the disk syncs if you're okay with some data loss of recent state changes if the machine crashes. What would an array of pointers to X containers which are N…

The containers are not in a contiguous memory block. To serialize it, you could write out each container as a length prefixed block with the container id, which is the 16-bit MSB of the container. The top level sorted list can be ignored, as it can be reconstructed. To de-serialize, read each container by reading its prefix length and its container id, and then read the rest of the container by the length. The top le…

Just to add a bit. The top level list can be appended to the end of the file as a directory of the pairs of id and the file offset of the container. In this way, the list at the end of the file can be read into memory to form a mapping of container-id to file offset, which can provide random access to the container blocks in the file.

Re: Roaring bitmaps: what they are and how they work

#49

Post by anonymoushn » Sun, Sep 04, 2022, 4:52 AM UTC

eesmith wrote: post #46

anonymoushn wrote: post #43

Earlier quoted context omitted.

timsort and pdqsort seem to be significantly slower than radix sort for random inputs, but presumably radix sort could also benefit from a pile of pattern-finding heuristics.

timsort and pdqsort (two comparison sort methods) and radix sort (a non-comparative sorting algorithm) have different albeit overlapping domains of applicability. Given a large number of 32-bit integers, radix sort is indeed significantly faster. While I would reach for a comparison sort method if I had a large number of arbitrary-length Unicode strings, which I wanted to sort in a case-ignoring order. Also, I found…

> timsort and pdqsort (two comparison sort methods) and radix sort (a non-comparative sorting algorithm) have different albeit overlapping domains of applicability.

Most comparators are of the form "compare by this, then if tied, compare by that, then if tied, compare by the other thing" which is pretty well suited to radix sort. You are correct though.

> While I would reach for a comparison sort method if I had a large number of arbitrary-length Unicode strings, which I wanted to sort in a case-ignoring order.

It seems like the radix sort is likely to be a lot faster for this too, mainly due to cache effects. If you have a dataset in mind I'll be happy to give it a shot.

> Also, I found timsort faster than radix sort when there was a small number (as I recall, For sure. 100 isn't so far from the threshold where a radix sort should fall back to something else anyway.

Re: Roaring bitmaps: what they are and how they work

#50

Post by jiggawatts » Sun, Sep 04, 2022, 7:06 AM UTC

jandrewrogers wrote: post #25

superjan wrote: post #11

It looks a bit too simplistic: Blocks with up to 4k items are stored as sorted lists. Having to insert in a sorted list up to 4k items seems very expensive to me.

CPUs have a strong performance bias toward sequential memory access and there are large threshold effects at work here. The block size used is not arbitrary. Improvements in prefetching and cache line utilization can have such large performance benefits that it more than justifies any apparent increase in computational cost because of how the code is organized to obtain those improvements. Most developers do not have…

I would have expected 2048 items to be the optimal cutover point, because with 16-bit entries that would result in 4KB arrays. Those fit exactly into a typical CPU memory page, whereas 8KB requires two. In the worst case that might double the page table overheads, e.g.: for random point reads.

I wonder if it would be worth the trouble to code-gen a bunch of variants with things like 8-bit entries, and benchmark to death to determine the optimal cutover points...