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

[Linus Torvalds <torvalds@osdl.org>]

On Sun, 12 Mar 2006, Linus Torvalds wrote:
> 
> 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).

Actually, on x86, where we can do the 64-by-32 division with a single 
instruction, this seems to be the best possible code:

	#define HASH_VAL (4294967291u)

	static inline unsigned int hash64x32(unsigned long long a)
	{
		unsigned int high, low;
		unsigned int modulus;

		asm(""
			:"=a" (low), "=d" (high)
			:"A" (a));
		if (high > HASH_VAL)
			high -= HASH_VAL;
		asm("divl %2"
			:"=a" (low), "=d" (modulus)
			:"rm" (HASH_VAL), "0" (low), "1" (high));
		return modulus;
	}

at least as far as I can think.

The magic is the reduction of the high 32 bits: for the general case you
want a modulus for that reduction, but since we're dividing with a
really big value, the modulus of the high bits really does end up
becoming just that simple

	if (high > HASH_VAL)
		high -= HASH_VAL;

and then we just need to do a single "divl" instruction.

So if you want a 32-bit hash of an 8-byte area, this should be a pretty
good and fast way to calculate it. 

Of course, maybe just doing an adler32() is simpler/better.  But with
the above, at least on x86, I suspect you get an even better
distribution at a lower cost (of course, different coress do differently
well on large divisions, but integer division being pretty important for
some codes, modern cores actually tend to be pretty good at it). 

			Linus