Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes

From: Jim Meyering <jim@meyering.net>
Date: Oct 16, 2006, 18:24 UTC
Message-ID: <873b9op19n.fsf@rho.meyering.net>
In-Reply-To: <Pine.LNX.4.64.0610161038200.3962@g5.osdl.org>

Linus Torvalds <torvalds@osdl.org> wrote:

Show 25 quoted lines

> On Mon, 16 Oct 2006, Jim Meyering wrote:
>>
>> That helps a little.
>> Now, instead of taking 63s, my test takes ~30s.
>> (32 for XDL_MAX_EQLIMIT = 16, 30 for XDL_MAX_EQLIMIT = 8)
>
> Btw, what architecture is this on?
>
> I'm testing those two files, and I get much more reasonable numbers with
> both ppc32 and x86. Both 32-bit:
>
> 	[torvalds@macmini test-perf]$ time git show | wc -l
> 	25221
>
> 	real    0m1.437s
> 	user    0m1.436s
> 	sys     0m0.012s
>
> ie it generated the diff in less than a second and a half. Not wonderful,
> but certainly not your 63s either.
>
> HOWEVER. On x86-64, it takes forever (still not 63 seconds, but it takes
> 17 seconds on my 2GHz merom machine).
>
> So I think there's something seriously broken with hashing on 64-bit.

amd_64 @ 2.0GHz

> Try this patch. And make sure to do a "make clean" first, since I think
> the dependencies on xdiff may be broken.

Yep. Dependencies are definitely broken. Applied your patch. No improvement after a plain "make", but doing "make clean && make" solved the problem.

Now, my diff-tree takes 2s (it's comparing other files, too). Thank you!

IMHO, my "&& vs. ||" patch is still worth applying. If not, then the existing code doesn't make sense, and there can be significant simplification in the affected loops. With my patch, I get an additional 3x speed-up: diff-tree takes 0.7s