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

[Jim Meyering <jim@meyering.net>]

Linus Torvalds <torvalds@osdl.org> wrote:
> 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