Re: What's cooking in git.git (topics)

[Jeff King <peff@peff.net>]

On Tue, Oct 02, 2007 at 07:28:19PM -0700, Linus Torvalds wrote:

> Sadly, that's not the case. It *does* seem to beat the current 
> implementation, but it's not "beat the pants off". It looks like an 
> improvement of about 15%, which is nothing to sneeze at, but it's not an 
> order-of-magnitude improvement either.
> 
> Here's a test-patch. I don't guarantee anything, except that when I did 
> the timings I also did a "wc" on the result, and they matched..

I get slightly better speedups with my pathological case (around 30%):

Before:
  $ /usr/bin/time git-diff --raw -M -l0 06d288^ 06d288 >/dev/null
  105.38user 3.65system 2:14.90elapsed 80%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (15432major+542627minor)pagefaults 0swaps

After:
  $ /usr/bin/time git-diff --raw -M -l0 06d288^ 06d288 >/dev/null
  71.70user 3.47system 1:40.43elapsed 74%CPU (0avgtext+0avgdata 0maxresident)k
  0inputs+0outputs (15065major+551778minor)pagefaults 0swaps

But yes, it's not the order of magnitude we were looking for.

> 	[torvalds@woody linux]$ time git diff -l0 --stat -C v2.6.22.. | wc

I found less noise in the timing by using --raw, since the patch
computation takes an appreciable amount of time.

> but the diff is fairly simple, so if somebody will go over it and say 
> whether it's likely to be *correct* too, that 15% may well be worth it.

Patch looks correct, and it produces correct results on my (admittedly
limited) test data.

I think it's worth applying (though I agree that a comment on the
assumption of a zero "cnt" at the end is worth adding) unless some
drastically different solution comes along (e.g., David's idea to try
avoiding the outer O(n^2) loop). But I don't think there is much more to
be gained from a different approach to comparing the two hash tables.

-Peff