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

From: Linus Torvalds <torvalds@osdl.org>
Date: Oct 16, 2006, 17:56 UTC
Message-ID: <Pine.LNX.4.64.0610161038200.3962@g5.osdl.org>
In-Reply-To: <87ejt8p5l9.fsf@rho.meyering.net>

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.

And I think I know what it is.

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

Davide: there's two things wrong with your old XDL_HASHLONG():

 - the GR_PRIME was just 32-bit, so it wouldn't shift low bits up far 
   enough on a 64-bit architecture, so then shifting things down caused 
   pretty much everything to be very small.

 - The whole idea of shifting up by multiplying and then shifting down to 
   get the high bits is _broken_. Even on 32-bit architectures. Think 
   about what happens when "hashbits" is 16 on a 32-bit architecture: the 
   multiply moves the low bits _up_, but it doesn't move the high bits 
   _down_. And with hashbits being a large fraction of the whole word, you 
   need to shift things down, not up.

So just making GR_PRIME be a bigger value on a 64-bit architecture would not have fixed it. The whole hash was simply broken. Do it the sane and obvious way instead: always pick the low bits, but mix in upper bits there too..

This patch brings the time down from 17 seconds to 0.8 seconds for me.

		Linus

---

diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
index 4c2fde8..bb4830b 100644
--- a/xdiff/xmacros.h
+++ b/xdiff/xmacros.h
@@ -24,14 +24,27 @@ #if !defined(XMACROS_H)
 #define XMACROS_H
 
 
-#define GR_PRIME 0x9e370001UL
+static inline unsigned long xdl_hashlong(unsigned long val, unsigned int bits)
+{
+	unsigned long shift = val >> bits;
+
+	/* Shift in the upper bits too */
+	val += shift;
+
+	/* Do it twice for small values of bits */
+	if (bits < 4*sizeof(unsigned long))
+		val += shift >> bits;
+
+	/* Return the resulting low bits */
+	return val & ((1ul << bits)-1);
+}
 
 
 #define XDL_MIN(a, b) ((a) < (b) ? (a): (b))
 #define XDL_MAX(a, b) ((a) > (b) ? (a): (b))
 #define XDL_ABS(v) ((v) >= 0 ? (v): -(v))
 #define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')
-#define XDL_HASHLONG(v, b) (((unsigned long)(v) * GR_PRIME) >> ((CHAR_BIT * sizeof(unsigned long)) - (b)))
+#define XDL_HASHLONG(v, b) xdl_hashlong(v,b)
 #define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)
 #define XDL_LE32_PUT(p, v) \
 do { \