absurdly slow git-diff

I have a 240k-line file, and I change one character on every sixth line. The resulting diff gives git serious indigestion:

$ git --version git version 1.6.0.3.640.g6331a $ mkdir a; cd a; git init Initialized empty Git repository in /home/ams/a/.git/ $ cp ../1 .; git add 1; git commit -q -m 1 $ cp ../2 1; git add 1; git commit -q -m 2 $ time git show HEAD > x git show HEAD > x 309.88s user 0.46s system 97% cpu 5:17.06 total

(I use commit -q above not only for brevity; for the second commit, calculating the diffstat takes the same five minutes that git show, git log -p, git log --stat etc. all take.)

Note that diff(1) can handle the patch fine:

$ time diff -u ../1 ../2 >/dev/null diff -u ../1 ../2 > /dev/null 0.30s user 0.06s system 69% cpu 0.519 total

If anyone's interested, the files are http://toroid.org/misc/1 and http://toroid.org/misc/2

Does anyone understand why this slowdown might happen or have suggestions about where I should look for it?

Thanks.

-- ams

On Sat, Nov 08, 2008 at 01:31:27AM +0530, Abhijit Menon-Sen wrote:

You don't need to go that far. You can stop at cp ../2 1 and run git diff from there.

All the time is spent in the two loops in xdiff/xprepare.c:xdl_cleanup_records, on line 400 and 412.

I'll leave the rest of the investigation to people actually knowing this code ;)

Mike

On Sat, 8 Nov 2008, Abhijit Menon-Sen wrote:

Btw, you can see this by just doing

	git diff 1 2

without even doing "git init" or doing any actual git repository.

Sure. It's actually fairly simple. You're hitting a O(n^2) thing (possibly higher), and it's triggered by the fact that almost all your lines are identical, ie you have a file that basically has 40,000 lines of each of

	xxxx: xxx, xx xxx xxxx xx:xx:xx +xxxx
	xx: xxxx xxxxxxxxxxx <xxxx@xxxx.xxx>
	xxxx: xxxx xxxxxxxxxxx <xxxx@xxxx.xxx>

and 30,000 of 

	* xxxxx xxxxx (xxxxxx.xxxx xxx xxxxx (\Xxxxxx) xxxxxx.xxxxxx {xxx}

with a smattering of others. And this is a case where the internal git implementation does really badly. And nobody has really cared before, because nobody has ever had a case that mattered.

There's a number of different 'diff' algorithms, and it looks like GNU diff has one that avoids the O(n^2) case for this case.

I'm adding Davide as the original author of the diff library to the cc. I'm also adding Pierre, since he was talking about trying to implement another diff algorithm (although I'm not at all sure that the patience diff really would help this case at all).

		Linus

On Fri, 7 Nov 2008, Linus Torvalds wrote:

That should be an easy fix. Just need to limit the window by which xdl_clean_mmatch() scans the current position.

- Davide

On Fri, 7 Nov 2008, Davide Libenzi wrote:

With +/- 100 lines (200 lines window):

davide@alien:~$ time ./xdiff_test --diff 1 2 > /dev/null 

real 0m1.534s user 0m1.466s sys 0m0.040s

- Davide

On Fri, 7 Nov 2008, Davide Libenzi wrote:

I assume the patch is something like the appended?

		Linus

---
 xdiff/xprepare.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

On Fri, 7 Nov 2008, Linus Torvalds wrote:

Yeah, similar. Mine is below. There's one less branch in the for loops.

- Davide

On Fri, 7 Nov 2008, Davide Libenzi wrote:

..and has a comment and made the magic constant be named.

Junio, the time difference is quite big for Abhijit's admittedly odd test-case:

 - Before:

	[torvalds@nehalem slow-diff]$ time git diff 1 2 > out.old
	
	real	2m19.912s
	user	2m19.885s
	sys	0m0.024s

 - After:

	[torvalds@nehalem slow-diff]$ time ~/git/git diff 1 2 > out

	real	0m0.841s
	user	0m0.816s
	sys	0m0.024s

with no difference in output.

			Linus

At 2008-11-07 15:57:23 -0800, torvalds@linux-foundation.org wrote:

It works fine for me (the time went from 5m17s to 1.8s).

(By the way, my test case is certainly very odd, but it is a real file from my test suite, albeit with the content x'ed away; and the change was to adjust the expected output for all the items. I wasn't looking for bugs. :-)

Thanks for the explanation and the patch.

-- ams

Linus Torvalds <torvalds@linux-foundation.org> writes:

In git.git history, "git-whatchanged -m -p -1" gives different output for the following commits, with and without the patch:

        c0e9892637e8144f10f2c408e276a470520f3601
        d6b3e3a33f71910526ccf80af6c13a230363cd89
        cecb98a9c3ed9271b0974bb6d7edbcf16e8a68f3
        ce18135d862b5dbc731d203b27c279529e58b54b
        36b5b3c65948694d9a92de5a17f2b97c3cd84879
        767e130915015f897fb87b939843b4882212574b
        927a503cd07718ea0f700052043f383253904a56

I've sampled a few (but not all) of them and they are different only because just how common lines are matched up, which is expected.

Davide Libenzi <davidel@xmailserver.org> writes:

Thanks, will apply like this, but I am not sure if you meant windowN or just window...

-- >8 --
From: Davide Libenzi <davidel@xmailserver.org>
Date: Fri, 7 Nov 2008 21:24:33 -0800
Subject: [PATCH] xdiff: give up scanning similar lines early

In a corner case of large files whose lines do not match uniquely, the
loop to eliminate a line that matches multiple locations adjacent to a run
of lines that do not uniquely match wasted too much cycles.  Fix this by
giving up early after scanning 100 lines in both direction.
---
 xdiff/xprepare.c |   15 +++++++++++++--
 1 files changed, 13 insertions(+), 2 deletions(-)

On Fri, 7 Nov 2008, Junio C Hamano wrote:

Whoops, just WINDOW.

- Davide

On Fri, Nov 07, 2008 at 09:37:29PM +0000, Linus Torvalds wrote:

FWIW Patience diff wouldn't help at all here. Patience diff is just a matter of preseeding your preferred diff algorithm with better (wrt human readability) candidate for the invariant lines. IOW it helps dividing the problem into smaller bits, but requires *unique lines* to start with. If you haven't any, then basically, Patience diff does nothing and calls your usual diff algorithm on the whole files.

It does so in a pseudo linear complexity, hence should not make overall time really worse, but will not help for the ending time usually either.