On Fri, Jul 15, 2011 at 04:10:23PM -0700, Linus Torvalds wrote: > On Fri, Jul 15, 2011 at 2:17 PM, Linus Torvalds > <torvalds@xxxxxxxxxxxxxxxxxxxx> wrote: > > > > For example, for the "git tag --contains" thing, what's the > > performance effect of just skipping tags that are much older than the > > commit we ask for? > > Hmm. > > Maybe there is something seriously wrong with this trivial patch, but > it gave the right results for the test-cases I threw at it, and passes > the tests. > > Before: > > [torvalds@i5 linux]$ time git tag --contains v2.6.24 > correct > > real 0m7.548s > user 0m7.344s > sys 0m0.116s > > After: > > [torvalds@i5 linux]$ time ~/git/git tag --contains v2.6.24 > date-cut-off > > real 0m0.161s > user 0m0.140s > sys 0m0.016s > > and 'correct' and 'date-cut-off' both give the same answer. Without even looking carefully at your patches for any minor mistakes, I can tell you that the speedup you're seeing is approximately right. Because it's almost exactly the same optimization I made in my timestamp-based patches (links to which I sent you earlier today). However, you can make it even faster. The "tag --contains" code will ask "is_descendant_of" repeatedly for the same set of "want" commits. So you end up traversing some parts of the graph over and over. My patches share the marks over a set of contains traversals, so you only ever touch each commit once. And that's what my patches do. With yours, on my box: $ time git tag --contains HEAD~1000 >/dev/null real 0m0.113s user 0m0.104s sys 0m0.008s and mine: $ time git tag --contains HEAD~1000 >/dev/null real 0m0.035s user 0m0.020s sys 0m0.012s I suspect you can make the difference even more prominent by having more tags, or by having multiple "want" commits. -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