Re: git-diff-tree -M performance regression in 'next'

From: Linus Torvalds <torvalds@osdl.org>
Date: Mar 13, 2006, 01:29 UTC
Message-ID: <Pine.LNX.4.64.0603121710110.3618@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0603121700410.3618@g5.osdl.org>

On Sun, 12 Mar 2006, Linus Torvalds wrote:

Show 5 quoted lines

> 
> Also, I think it is likely really wasteful to try to actually hash at 
> _each_ character. Instead, let's say that the chunk-size is 8 bytes (like 
> you do now), and let's say that you have a 32-bit good hash of those 8 
> bytes. What you can do is:

Side note: regardless, your new algorithm clearly does seem faster.

However, it worries me a bit that you don't check the source strings, especially since the hash you use seems somewhat suspect (why limit it to essentially just 16 bits? Wouldn't it be best to have the _biggest_ prime that fits in the "hashval" thing, which is at least 32 bits? Also, shouldn't you make that spanhash thing use a "unsigned int" instead of "unsigned long"?)

So I would suggest instead the hash function to be:

	typedef unsigned long long u64;

	/* Biggest prime in 32 bits */
	#define HASHVAL (4294967291u)

	u64 value = *(u64 *)src;
	src += 8;
	hash = value % 4294967291u;

which does a 64-bit modulus, but hey, 64-bit hw isn't _that_ uncommon any more, and it's not _excessively_ slow on x86 (gcc doesn't generate good code, but we could actually use the kernel "do_div()" routine for much faster division of 64 % 32 than what gcc can do - since the dividend is 32-bit, you actually only need to do one 32/32 division and one 64/32 division, so the optimized hash function on a good x86 will be just in the teens of cycles for the 64-bit modulus).

		Linus