On Tue, Jul 05, 2022 at 11:01:43AM -0700, Boris Burkov wrote: > > Unfortunately, I don't think doing this will work out really well for > > you. The bits really are independent of each other, and the power of > > the search marks lies in their ability to skip over vast swathes of > > the array when they're not marked. But to do what you want, we'd end up > > doing something like this: > > > > leaf array 1: > > entry 0 is in category 1 > > entry 1 is in category 2 > > entry 2 is in category 5 > > > > and now we have to set all three bits in the parent of leaf array 1, > > so any search will have to traverse all of leaf array 1 in order to find > > out whether there are any entries in the category we're looking for. > > Thank you for the explanation. To check my understanding, does this > point also imply that currently the worst case for marked search is if > every leaf array has an entry with each mark set? Yes. Each leaf array is 64 entries, and the tags are stored at the end of the node. A mark search consists of scanning one of the three bitmaps. Which means we have to load two cachelines (both the header and the mark array) out of each node which has a mark set. We can avoid accessing six or seven of the nine cachelines if only one bit is set, but with the amount of prefetching CPUs do these days, I don't know how effective that is. I keep meaning to try moving the mark array from the end of the node to the header, but I worry it'll hurt non-marked lookups.
