On Fri, Feb 21, 2025 at 09:15:07AM -0800, Junio C Hamano wrote: > Jeff King <peff@xxxxxxxx> writes: > > > Yeah. I did not see the word "stride" anywhere in your email, so I > > wanted to provide a further hint: the commit-slab "_with_stride()" > > variant is meant to handle this kind of arbitrary-sized data. This was > > part of the original commit-slab implementation in a84b794ad0 > > (commit-slab: introduce a macro to define a slab for new type, > > 2013-04-13), but AFAIK we've never actually used it in practice. See > > that commit for some examples. > > Wow, after reading the log message of that commit, I realize that we > already were considering that one-bit-per-ref needs dynamic scaling > and folks must have been thinking hard about it (I do not think the > author of the commit alone thought it---it must have been a group > effort on the list, which the log message merely explains the motivation > behind the design). > > Thanks for a pointer ;-) Definitely one of the use cases we discussed early on was using it in paint_down_to_common(). This series: https://lore.kernel.org/git/20140625233429.GA20457@xxxxxxxxxxxxxxxxxxxxx/ built a fast --contains traversal using the slab stride. I think I stalled because I hadn't convinced myself fully that it covered all cases. You left some very thoughtful comments, but I guess I just never got back around to it. We ended up taking the early parts (like converting quadratic list access to a prio_queue) as a separate series. I don't know how valuable the rest of it is; there has been a lot of work since then in this area by Stolee, et al. So it's unclear how much it would help now. But the "bitset" API from: https://lore.kernel.org/git/20140625234000.GD23146@xxxxxxxxxxxxxxxxxxxxx/ would probably be useful if somebody is trying to help show-branch. It gives you the arbitrary-sized thing you'd store in the slab. -Peff
