Re: [GSoC][RFC PATCH] show-branch: use commit-slab for flag storage

From: Jeff King <peff@peff.net>
Date: Feb 25, 2025, 01:17 UTC
Message-ID: <20250225011757.GA752084@coredump.intra.peff.net>
In-Reply-To: <xmqqy0xzb4o4.fsf@gitster.g>

On Fri, Feb 21, 2025 at 09:15:07AM -0800, Junio C Hamano wrote:

Show 18 quoted lines

> Jeff King <peff@peff.net> 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@sigill.intra.peff.net/

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@sigill.intra.peff.net/

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