Re: Git commit generation numbers

From: Jeff King <peff@peff.net>
Date: Jul 16, 2011, 00:42 UTC
Message-ID: <20110716004232.GB32230@sigill.intra.peff.net>
In-Reply-To: <CA+55aFwSgYYaQ8gTQmCw6SNMyr-bz5rJPr0o9xoog-1aCqb5rA@mail.gmail.com>

On Fri, Jul 15, 2011 at 04:36:40PM -0700, Linus Torvalds wrote:

Show 24 quoted lines

> On Fri, Jul 15, 2011 at 4:16 PM, Linus Torvalds
> <torvalds@linux-foundation.org> wrote:
> >
> > I have fewer branches than tags, but I get something similar for "git
> > branch --contains":
> 
> The time-based heuristic does seem to be important. If I just remove
> it, I get increasingly long times for things that aren't contained in
> my branches.
> 
> And in fact, I think that is why the code used the merge-base helper
> functions - not because it wanted merge bases, but because the merge
> base stuff will work from either end until it decides things aren't
> relevant any more. Because *without* the time-based heuristics, the
> trivial "is this a descendant" algorithm ends up working very badly
> for the case where the target doesn't exist in the branches. Examples
> of NOT having a date-based cut-off, but just doing the straightforward
> (non-merge-base) ancestry walk:
> 
>   time ~/git/git branch --contains v2.6.12
>   real	0m0.113s
> 
>   [torvalds@i5 linux]$ time ~/git/git branch --contains v2.6.39
>   real	0m3.691s

Yes, exactly. That is why my first patch (which goes to a recursive search), takes about the same amount of time as "git rev-list --all" (and I suspect your 3.691s above is similar). And then the second one drops that again to .03s.

I think you are simply recreating the strategy and timings I have posted several times now.

-Peff