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

From: Linus Torvalds <torvalds@osdl.org>
Date: Oct 16, 2006, 18:03 UTC
Message-ID: <Pine.LNX.4.64.0610161100070.3962@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0610161038200.3962@g5.osdl.org>

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.

			Linus