On Fri, Jul 15, 2011 at 04:36:40PM -0700, Linus Torvalds wrote: > 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 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 -- 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