Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited

From: Jeff King <peff@peff.net>
Date: Jan 19, 2021, 22:53 UTC
Message-ID: <YAdjBC7z2eE1Z0uk@coredump.intra.peff.net>
In-Reply-To: <20210119144251.27924-2-jacob@gitlab.com>

On Tue, Jan 19, 2021 at 03:42:51PM +0100, Jacob Vosmaer wrote:

Show 8 quoted lines

> The previous implementation of ls-refs would perform exactly one ref
> walk, matching each ref against the prefixes (if any) provided by the
> user. This can be expensive if there are a lot of refs and the user
> only cares about a small subset of them.
> 
> In this patch we analyze the prefixes provided by the user and build a
> minimal set of disjoint prefixes that contains all of them. We then do
> a ref walk for each of these minimal prefixes.

Thanks for posting this. I have a vague recollection that we considered this either when we did the for-each-ref prefixes, or when we added ls-refs prefixes, but I can't seem to find either. At any rate, at GitHub we haven't generally found it to be a problem because our horrifically-large repos tend to be aggregated alternates repos, not the ones people serve upload-pack out of (though I did just time it, and some of our largest repos should save a few hundred milliseconds per advertisement, which is certainly not nothing).

I do think we should reuse the code from ref-filter, as Taylor showed.

> This commit also fixes a bug in ls-refs.c that was not triggered
> before: we were using a strvec set to zero, which is not how you are
> supposed to initialize a strvec. We now call strvec_init after zeroing.

Good catch. It didn't matter until now because nobody relied on having a NULL entry when no prefix had been added (instead, they always iterated over prefixes->nr). IMHO that is worth fixing as a separate commit.

-Peff