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.
Roaring bitmaps: what they are and how they work
21–30 of 61 posts
Re: Roaring bitmaps: what they are and how they work
#22I 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”.
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 algorithm that has an optimal set of strategies and strategy-switching thresholds. The meta-algorithm is mostly focused on cheaply detecting these thresholds at runtime.
Re: Roaring bitmaps: what they are and how they work
#23I 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)?
Re: Roaring bitmaps: what they are and how they work
#24I 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”.
No this is still comp sci. Comp sci doesn’t mean that practical considerations in algorithm design are ignored. Computer engineering has to do with the actual design and construction of computing machinery. It’s an accredited engineering field and the undergraduate coursework includes electronics, semiconductors, computer architecture and generally a lot of overlap with electrical engineering. I had to take one dumb programming course - all the data structures and algorithms stuff I had to learn elsewhere.
Re: Roaring bitmaps: what they are and how they work
#25It 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 a good intuition for the efficiency and scalability of sequential brute-force on modern architectures. There is a cross-over threshold but I think many people would be surprised at how high it is in practice.
Re: Roaring bitmaps: what they are and how they work
#26Can 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…
This article has a section titled "how Roaring bitmaps are represented in memory". I suggest you actually read the article, it will likely answer all your questions.
Re: Roaring bitmaps: what they are and how they work
#27Earlier quoted context omitted.
I was thinking a similar thought that 4096 seemed quite magic (although it seems to be chosen based on research) and that RB perf could probably be tuned based on the workload
I don't think 4096 is arbitrary. It's an array of 16bit integers, and 4096 * 16 = 65536. So 4096 represents the boundary point below which an array of integers uses less memory than a traditional bitmap.
Oops, thanks for pointing that out
Re: Roaring bitmaps: what they are and how they work
#28I 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”.
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 runtime for many different input sizes and de-jitter each data point by pushing down that convexity constraint, even if for each input size you only gather one single noisy data point.
Where possible, I always liked arrays of function pointers for each next power of 2 in the input sizes. A few popcounts and a jump later, and you're executing the right routine. It's not great if you're throwing a general-purpose tool against tiny problems, but it's not a huge amount of overhead either, and it's dead simple to code.
Re: Roaring bitmaps: what they are and how they work
#29Can 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…
This article has a section titled "how Roaring bitmaps are represented in memory". I suggest you actually read the article, it will likely answer all your questions.
I was actually asking how they were serialized and stored on disk.
Re: Roaring bitmaps: what they are and how they work
#30Not .bmp bitmaps used to store photographic images as I would have guessed:
> Bitmaps are arrays of bits used to store sets of integers. They work by setting the Nth bit when an integer N is in the set