Re: Git commit generation numbers

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

On Fri, Jul 15, 2011 at 4:16 PM, Linus Torvalds
[off-list ref] wrote:

quoted

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