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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Junio, I think this is worthy to go in before a 1.4.3 release. Possibly 
even back-ported to earlier trees. Anything that causes an almost two 
orders of magnitude slowdown (even if it's just on 64-bit architectures 
and most people won't necessarily compile git that way) is worth fixing 
pronto.

On Mon, 16 Oct 2006, Davide Libenzi wrote:
> 
> Yeah, using an appropriate golden ratio prime for 64 bits fixes it. I 
> think it's the best/minimal fix (use 0x9e37fffffffc0001UL, like the 
> kernel does).

Ok. But then you need something like the appended to avoid warnings..

(This is the only nice portable way to figure out at compile-time whether 
"unsigned long" is more than 32 bits that I can come up with: everything 
that uses actual C expressions ends up warning about integers not fitting 
etc)

Quite frankly, I prefer my previous patch more, it just avoids that whole 
problem, and two shifts and adds (even with a conditional) are often 
faster than a full 64-bit multiply.

		Linus
---
diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
index 4c2fde8..38f8f93 100644
--- a/xdiff/xmacros.h
+++ b/xdiff/xmacros.h
@@ -23,8 +23,13 @@
 #if !defined(XMACROS_H)
 #define XMACROS_H
 
+#include <limits.h>
 
+#if LONG_MAX > 2147483647ul
+#define GR_PRIME 0x9e37fffffffc0001UL
+#else
 #define GR_PRIME 0x9e370001UL
+#endif
 
 
 #define XDL_MIN(a, b) ((a) < (b) ? (a): (b))
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]