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

From: Jeff King <peff@peff.net>
Date: Oct 3, 2007, 06:54 UTC
Message-ID: <20071003065414.GA13737@coredump.intra.peff.net>
In-Reply-To: <alpine.LFD.0.999.0710021916080.3579@woody.linux-foundation.org>

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

Show 7 quoted lines

> 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