Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Roaring bitmaps: what they are and how they work

vikramoberoi.com

Post reply on HN
Print view View original

51–60 of 61 posts

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

#51

Post by superjan »

jasonwatkinspdx wrote: post #20
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.

The threshold was chosen empirically. Modern processors are very fast when operating on memory sequentially, as the prefetcher achieves the best case scenario. The cost of a cache line miss is so substantial this ends up dominating things until "n" is in the 1000s. A lot of programmers' intuition is off the mark on this point.

My intuition was indeed trained a long time ago. In terms of memory use, the current choice is likely optimal. But I have a hard time believing that doing an or operation on two sets of sorted numbers will be as fast as the same for two bitmaps of 8k. The latter can be trivially simd accellerated, and could be done in-place.

Having said that, I applaud that this type of datastructure is being investigated. An efficient bitset should be present in every collections library.

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

#52

Post by jerven »

voberoi wrote: post #23
jerven wrote: post #21

I love roaringbitmaps and maybe even over use this library. On the other hand it made a lot of things possible for legacy.uniprot.org over the years that would have been unaffordable otherwise. Quick faceting using permanent filters over 500+ million Documents would have been really hard otherwise.

I’m really curious about this. Are you able to share a bit about your use case and how you use roaring bitmaps outright (vs. through search infra like Solr or ElasticSearch)?

Well the replacement of this code base uses Solr. But when legacy started we where on lucene 1x that over the years upgraded to lucene 9x. So one of the things we used our bitmaps for was for a number extensions to pure lucene. So like facets, but also inter index joins. And then preserving résultats for fast faceting that remained part of the query.

E.g. a thing that legacy can but the new www (Solr) currently can't is allow downloads in a streaming fashion of more than 5million documents. As maintaing a roaringbitmap cost very little memory but depends on docid to key/value store mapping. Our extensions allowed this and gave us a very easy to use rest API.

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

#53

Post by eesmith »

anonymoushn wrote: post #49
eesmith wrote: post #46

Earlier quoted context omitted.

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 la…

> which is pretty well suited to radix sort

Yes, the general approach is to convert the input data into a fixed-length bit-string with the same sort order as the input.

Your example assumes that construction overhead is short. If tie-breaking is rare, and breaking the tie requires an expensive operation, then the trade-off point for radix might be much higher than 100 elements.

The fixed-length requirement works well for small items with relatively equal-length fields. Ragged items, like Wikipedia titles, causes a problem. There is one title which is 253 bytes long. Now, Wikipedia titles are limited to 255 bytes, so radix is certainly directly applicable, but 1) it changes the trade-off point, and 2) reduces cache effects.

Finally, it requires a sort-order-preserving transformation. I mentioned case-insensitive collation of Unicode strings as a well-known difficult problem. I do not believe there is mapping to an order-preserving representation which can be done bitwise. At the very least, it will be difficult to support all of the collation styles that currently exist (eg, French collation is different than Dutch).

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

#54

Post by _0ffh »

jiggawatts wrote: post #50
jandrewrogers wrote: post #25

Earlier quoted context omitted.

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 de…

I think if you go down this road, you'll start to see differences depending on the brand and model of CPU you use. Essentially, you're going into the territory of FFTW's "planner" scheme.

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

#55

Post by vladf »

hansvm wrote: post #28
jandrewrogers wrote: post #22

Earlier quoted context omitted.

Much of this is just threshold effects for algorithm performance, not special cases per se. You don't even need to have specific knowledge of the hardware as long as you can identify cross-over points where one algorithm starts significantly outperforming others. An old HPC trick is to write software that thoroughly measures several algorithm strategies on your specific hardware environment and then code-gens an algo…

For a lot of such algorithms there are also pretty cheap ways to remove jitter from the measurements (in case you're operating on top of a general purpose OS or something) -- you expect for many algorithms that in the absence of external factors the runtime is convex monotonic as a multivariate function of the input sizes and that external confounders don't speed things up. Under that assumption you can measure the r…

Can you give an example of this convex assumption push down? It doesn’t seem right to me. For instance, due to cache line sizes and other blocking/buffering effects throughout hardware and the OS, I actually would expect “staircase” functions which aren’t convex.

Maybe that’s convex if you smooth enough. But depends on the buffer sizes.

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

#56

Post by anonymoushn »

eesmith wrote: post #53
anonymoushn wrote: post #49

Earlier quoted context omitted.

> 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 la…

> which is pretty well suited to radix sort Yes, the general approach is to convert the input data into a fixed-length bit-string with the same sort order as the input. Your example assumes that construction overhead is short. If tie-breaking is rare, and breaking the tie requires an expensive operation, then the trade-off point for radix might be much higher than 100 elements. The fixed-length requirement works well…

This is basically all incorrect. Maybe you are writing about LSB radix sort? I am writing about MSB radix sort. You can get some off-the-shelf MSB radix sort for sorting strings of arbitrary lengths here[0]. While this repository is mainly about parallel string sorts, I've found a version of this MSB radix sort that does not perform a bunch of unnecessary copies and caches more bytes at a time[1] to be competitive with the parallel sorts in the repo.

In general MSB radix sort will have to look at the same parts of the input elements as multi-key quick sort, but one hopes that it gets to make fewer passes over the array. A comparator-based sort would look at about the same parts of the input elements as well, but it would look at them many times more than necessary.

> Finally, it requires a sort-order-preserving transformation. I mentioned case-insensitive collation of Unicode strings as a well-known difficult problem. I do not believe there is mapping to an order-preserving representation which can be done bitwise. At the very least, it will be difficult to support all of the collation styles that currently exist (eg, French collation is different than Dutch).

The requirements are a bit underspecified, but I think these can be solved by unicode normalization + tolower + codepoint-wise comparison, which is probably what you'd do in your comparator for a comparison-based sort as well.

[0]: https://github.com/bingmann/parallel-string-sorting/blob/mas...

[1]: https://github.com/dendibakh/perf-challenge6/blob/Solution_R...

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

#57

Post by vanderZwan »

jasonwatkinspdx wrote: post #47
froh wrote: post #18

Earlier quoted context omitted.

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.

As someone with a degree in contemporary arts who switched to programming I humbly disagree with this statement.

Jokes aside, it took me quite a bit of trial and error to figure out that you are (probably) referring to Adaptive Radix Trees. Because "art tree" doesn't exactly give useful results.

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

#58

Post by froh »

nullc wrote: post #45
froh wrote: post #18

Earlier quoted context omitted.

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.

https://github.com/Reference-LAPACK/lapack/commits/master

said fortran code happily gets minor and major updates

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

#59

Post by nullc »

froh wrote: post #58
nullc wrote: post #45

Earlier quoted context omitted.

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.

https://github.com/Reference-LAPACK/lapack/commits/master said fortran code happily gets minor and major updates

I wasn't actually referring to LAPACK but other FEM code. :)

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

#60

Post by froh »

nullc wrote: post #59
froh wrote: post #58

Earlier quoted context omitted.

https://github.com/Reference-LAPACK/lapack/commits/master said fortran code happily gets minor and major updates

I wasn't actually referring to LAPACK but other FEM code. :)

Point being: a project needs updates to remain useful in contemporary contexts. code that happily built -Wall, pedantic, error... in April 2002 may fail miserably in today's tool chain.

plus it may not benefit from contemporary advances in silicon architecture, etc.

Post reply on HN