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]

 




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
-
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]