Re: [PATCH] ref-filter: format iteratively with lexicographic refname sorting

From: Jeff King <peff@peff.net>
Date: Oct 17, 2024, 02:48 UTC
Message-ID: <20241017024828.GC1858436@coredump.intra.peff.net>
In-Reply-To: <ZxA6I67FfPe4fV2F@nand.local>

On Wed, Oct 16, 2024 at 06:11:47PM -0400, Taylor Blau wrote:

Show 19 quoted lines

> On Wed, Oct 16, 2024 at 08:00:30AM +0200, Patrick Steinhardt wrote:
> > But there is one exception here where we _can_ get away with sorting
> > refs while streaming: ref backends sort references returned by their
> > iterators in lexicographic order. So if the following conditions are all
> > true we can do iterative streaming:
> >
> >   - The caller uses at most a single name pattern. Otherwise we'd have
> >     to sort results from multiple invocations of the iterator.
> >
> >   - There must be at most a single sorting specification, as otherwise
> >     we're not using plain lexicographic ordering.
> >
> >   - The sorting specification must use the "refname".
> >
> >   - The sorting specification must not be using any flags, like
> >     case-insensitive sorting.
> 
> Perhaps a niche case, but what about ancient packed-refs files that were
> written before the 'sorted' capability was introduced?

We should be OK there. In that case we actually read in and sort the packed-refs entries ourselves. We have to, since we do an in-order merge with the loose refs while iterating.

I do think this optimization is worth doing, and not a problem with our current backends. The biggest worries would be:

  1. Some new ref backend that doesn't return sorted results. I find
     this unlikely, and anyway it's easily caught by having coverage in
     the test suite (which I assume we already have, but I didn't look).

  2. Some new flag combination that requires disabling the optimization,
     and which must be dealt with in the code. This seems unlikely to me
     but not impossible. I think enabling the optimization is worth it,
     though.

> >   - The caller uses at most a single name pattern. Otherwise we'd have
> >     to sort results from multiple invocations of the iterator.

I think this part is erring on the cautious side, as we can often collapse these into a single iteration due to the ref-prefix work. It may be OK to keep using the slower code here if multiple patterns aren't commonly used, but I'd suspect that:

  git for-each-ref --sort=refname refs/heads refs/tags

could benefit.

-Peff