Code

Set up for better tree diff optimizations
authorLinus Torvalds <torvalds@linux-foundation.org>
Sun, 18 Mar 2007 22:18:30 +0000 (15:18 -0700)
committerJunio C Hamano <junkio@cox.net>
Mon, 19 Mar 2007 09:01:39 +0000 (02:01 -0700)
commit5d86501742663978dfa4dd8accaee4bb93639fee
tree5681825c2b5635e7fd2c5e1330d80590a4b7196e
parentc711a214c1e9a4dfb5043bc1a11d0f76313b097e
Set up for better tree diff optimizations

This is mainly just a cleanup patch, and sets up for later changes where
the tree-diff.c "interesting()" function can return more than just a
yes/no value.

In particular, it should be quite possible to say "no subsequent entries
in this tree can possibly be interesting any more", and thus allow the
callers to short-circuit the tree entirely.

In fact, changing the callers to do so is trivial, and is really all this
patch really does, because changing "interesting()" itself to say that
nothing further is going to be interesting is definitely more complicated,
considering that we may have arbitrary pathspecs.

But in cleaning up the callers, this actually fixes a potential small
performance issue in diff_tree(): if the second tree has a lot of
uninterestign crud in it, we would keep on doing the "is it interesting?"
check on the first tree for each uninteresting entry in the second one.

The answer is obviously not going to change, so that was just not helping.
The new code is clearer and simpler and avoids this issue entirely.

I also renamed "interesting()" to "tree_entry_interesting()", because I
got frustrated by the fact that

 - we actually had *another* function called "interesting()" in another
   file, and I couldn't tell from the profiles which one was the one that
   mattered more.

 - when rewriting it to return a ternary value, you can't just do

if (interesting(...))
...

   any more, but want to assign the return value to a local variable. The
   name of choice for that variable would normally be "interesting", so
   I just wanted to make the function name be more specific, and avoid
   that whole issue (even though I then didn't choose that name for either
   of the users, just to avoid confusion in the patch itself ;)

In other words, this doesn't really change anything, but I think it's a
good thing to do, and if somebody comes along and writes the logic for
"yeah, none of the pathspecs you have are interesting", we now support
that trivially.

It could easily be a meaningful optimization for things like "blame",
where there's just one pathspec, and stopping when you've seen it would
allow you to avoid about 50% of the tree traversals on average.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
tree-diff.c