From: Linus Torvalds Date: Mon, 16 Oct 2006 18:03:41 GMT Subject: Re: git-diff-tree inordinately (O(M*N)) slow on files with many changes Message-ID: In-Reply-To: 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