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

[Davide Libenzi <davidel@xmailserver.org>]

On Mon, 16 Oct 2006, Linus Torvalds wrote:

> 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