Re: Git commit generation numbers

And one last comment:

On Fri, Jul 15, 2011 at 4:16 PM, Linus Torvalds <torvalds@linux-foundation.org> wrote:

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

and what ends up happening is that in the latter case, every branch walks all the way to the root and checks every commit (walking all the merges too). While in the first case, it's very quick because it will find that particular commit when it walk straight backwards (so it doesn't even have to do a lot of recursion - the first branch that hits that commit will be a success), so it won't have to look at all the side ways of getting there.

Of course, the above particular difference happens to be due to the "depth-first" implementation working well for the thing I am searching for. But it does show that the date-based cut-off matters due to traversal issues like that.

                          Linus