And one last comment:
On Fri, Jul 15, 2011 at 4:16 PM, Linus Torvalds
<torvalds@xxxxxxxxxxxxxxxxxxxx> 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
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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html