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

From: Davide Libenzi <davidel@xmailserver.org>
Date: Oct 16, 2006, 18:41 UTC
Message-ID: <Pine.LNX.4.64.0610161138140.7697@alien.or.mcafeemobile.com>
In-Reply-To: <Pine.LNX.4.64.0610161100070.3962@g5.osdl.org>

On Mon, 16 Oct 2006, Linus Torvalds wrote:

Show 19 quoted lines

> On Mon, 16 Oct 2006, Linus Torvalds wrote:
> > 
> > So just making GR_PRIME be a bigger value on a 64-bit architecture would 
> > not have fixed it.
> 
> Side note: in _practice_ I think it would have fixed it. The "not mixing 
> in high bits" is not a real problem if the original hash-value has a good 
> distribution of bits, which I think we do have. So it's unclear whether we 
> even need any mixing in of bits at all, and it's possible that it would be 
> fine to just have
> 
> 	#define XDL_HASHLONG(v,b) ((unsigned long)(v) & ((1ul << (b))-1))
> 
> which is simpler than my patch.
> 
> I prefer the mixing in of high bits just because it can help if the 
> original hash was bad (or had a tendency to have patterns in the low bits, 
> which could be the case). But I'm not sure xdiff actually needs it in this 
> case.

ATM, I added AC_CHECK_SIZEOF(long) inside libxdiff's configure.in, and I have (inside xmacros.h):

#if SIZEOF_LONG == 4 #define GR_PRIME 0x9e370001UL #else #define GR_PRIME 0x9e37fffffffc0001UL #endif

I'm also looking into streamlining the discard loop to reuse information collected during the context-setup phase ...

- Davide