Re: [RFC/PATCH 1/4] tag: speed up --contains calculation

From: Jeff King <peff@peff.net>
Date: Feb 23, 2011, 16:39 UTC
Message-ID: <20110223163938.GB10042@sigill.intra.peff.net>
In-Reply-To: <AANLkTinL-gN3sCkUzzsBbzwxo1AYx1NURjKaE8D4TgvU@mail.gmail.com>

On Wed, Feb 23, 2011 at 04:51:02PM +0100, Ævar Arnfjörð Bjarmason wrote:

Show 12 quoted lines

> On Mon, Jul 5, 2010 at 14:33, Jeff King <peff@peff.net> wrote:
> > When we want to know if commit A contains commit B (or any
> > one of a set of commits, B through Z), we generally
> > calculate the merge bases and see if B is a merge base of A
> > (or for a set, if any of the commits B through Z have that
> > property).
> 
> On a work repo with around 10k tags after and before this patch:
> [...much speed improvement...]
> I'd love to have this merged downwards from pu. It's the single
> biggest usability improvement in my Git workflow for as long as I can
> remember.

Yeah, I have been meaning to revisit the topic. I got sidetracked by looking at clock skew issues, and there was some debate over whether the strict depth-first traversal was the best way to do it (although if you trust the commit timestamps, I think you stop going down dead-ends pretty quickly in practice; and I think we do implicitly trust the commit timestamps in the regular merge base traversals). If we can do a multi-headed merge base, that would be better, but I'll have to think on it.

I'll try to take a look this week and see what I can come up with.

-Peff