Re: [PATCH 0/4] Speed up git tag --contains

From: Jeff King <peff@peff.net>
Date: Mar 12, 2018, 23:59 UTC
Message-ID: <20180312235907.GG1968@sigill.intra.peff.net>
In-Reply-To: <63e9c6a8-4efc-6f86-f355-1ec40dd674e4@gmail.com>

On Mon, Mar 12, 2018 at 09:45:27AM -0400, Derrick Stolee wrote:

Show 19 quoted lines

> > diff --git a/builtin/branch.c b/builtin/branch.c
> > index 8dcc2ed058..4d674e86d5 100644
> > --- a/builtin/branch.c
> > +++ b/builtin/branch.c
> > @@ -404,6 +404,7 @@ static void print_ref_list(struct ref_filter *filter, struct ref_sorting *sortin
> >   	memset(&array, 0, sizeof(array));
> > +	filter->with_commit_tag_algo = 1;
> >   	filter_refs(&array, filter, filter->kind | FILTER_REFS_INCLUDE_BROKEN);
> >   	if (filter->verbose)
> > 
> > drops my run of "git branch -a --contains HEAD~100" from 8.6s to
> > 0.4s on a repo with ~1800 branches. That sounds good, but on a repo with
> > a smaller number of branches, we may actually end up slower (because we
> > dig further down in history, and don't benefit from the multiple-branch
> > speedup).
> 
> It's good to know that we already have an algorithm for the multi-head
> approach. Things like `git branch -vv` are harder to tease out because the
> graph walk is called by the line-format code.

Yeah, the ahead/behind stuff will need some work. Part of it is just code structuring. We know ahead of time which branches (and their upstreams) are going to need this ahead/behind computation, so we should be able to do collect them all for a single call.

But I'm not sure if a general multi-pair ahead/behind is going to be easy. I don't have even experimental code for that. :)

We have a multi-pair ahead/behind command which we use at GitHub, but it does each pair separately. It leans heavily on reachability bitmaps, so the main advantage is that it's able to amortize the cost of loading the bitmaps (both off disk, but also we sometimes have to walk to complete the bitmaps).

-Peff