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.
Roaring bitmaps: what they are and how they work
11–20 of 61 posts
Re: Roaring bitmaps: what they are and how they work
#12Those who do not know judy1 are doomed to reinvent it. http://judy.sourceforge.net/
Re: Roaring bitmaps: what they are and how they work
#13It 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 4k items are only 512 bytes though, so expensive yes but not overly so.
Re: Roaring bitmaps: what they are and how they work
#14Earlier quoted context omitted.
Compressing consecutive 1's and 0's was the first idea that popped into my head as well. Then when they started to talk about inserting into the 800,000th position my brain went "What if they just reversed the array and stored some metadata as the type of array they're dealing with?" It's funny that in the end Bitmaps essentially are a modified data structure and process. The way things are going, I imagine someone w…
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.
Re: Roaring bitmaps: what they are and how they work
#15I'm reading this on a runaway with terrible internet and the figures slowly load to reveal... text :/
Re: Roaring bitmaps: what they are and how they work
#16It 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 4k items are only 512 bytes though, so expensive yes but not overly so.
They are two byte per item; it's the bitmaps (>4k entries) that use 1 bit per item.
Re: Roaring bitmaps: what they are and how they work
#17It 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 4k items are only 512 bytes though, so expensive yes but not overly so.
No. The person you are replying to is talking about the sparse leaf case where the contained integers are actually being stored (to be more precise the low bits are being stored) in a sorted structure. The switch to the bitmap occurs when the sparse structure takes the same number of bits to directly encode the sparsely contained items. In this case they use a 2^16 bitmap and encode sparse elements using 16-bits, so it occurs at ((2^16 / 16) == 2^12) elements.
Re: Roaring bitmaps: what they are and how they work
#18Those 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
Re: Roaring bitmaps: what they are and how they work
#19I thought the trick was going to be indirection.
sorted-list/bitmap/runs, in a two level tree. cool.
it's technically missing sorted compliment-list, i.e. only the items that are missing, although worst case runs only use twice as much space, so more complexity without much savings, esp. considering real workloads
performs better with sequential ids than random uuids because you use fewer pages
further research
investigating the effect of adding more layers to the tree
using additional set representations e.g. balanced tree
Re: Roaring bitmaps: what they are and how they work
#20It 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.