[Python-Dev] Python hash function

[Damien Morton]

Ive been doing some investigation of python hashtables and the hash
function used in Python.

It turns out, that when running pystone.py, as much time is spent in
string_hash() as is spent in lookdict_string(). If you look at
python's hash function, shown below, you can get an idea why - a
multiply is used for every character in the string.

The following function, called 2^22 times in a loop, times in at 530ms
for 7-character strings.

static long
string_hash1(register char *p, int size)
{
	register int len;
	register long x;

	len = size;
	x = *p << 7;
	while (--len >= 0)
		x = (100003*x) ^ *p++;
	x ^= size;
	return x;
}

Looking around the web I found the following hash function, which is
much faster, and seems to distribute better than the python hash
function.

The following function, called 2^22 times in a loop, times in at 160ms
for 7-character strings.

static long
string_hash3(register char *p, register int size)
{
	register long x;
	register char c;

	x = 0xd2d84a61;
        while (c = *p++)
		x ^= ( (x<<7) + c + (x>>5) );
	return x;
}

I also came up with a hash function of my own, which seems to
distribute near-perfectly (in the sense of being comparable to
assigning, as hashes, random numbers to unique strings) and be faster
yet (at least, on my P4 box).

The following function, called 2^22 times in a loop, times in at 120ms
for 7-character strings.

static long
string_hash6(register unsigned short *p, int size)
{
	register unsigned long x = 0;
       
      if (size==0) return 0;

	len = (size+1) >> 1;
	while (len--) {
		x += (x>>14) + (*p++ * 0xd2d84a61);
		}
	x += (x>>14) + (size*0xd2d84a61);
	
	return x;
}

Ive tested these functions by hashing a large set of strings generated
by instrumenting the python interpeter to emit a string every time a
string is added to a dictionary. These strings are hashed and thrown
into the buckets of various sized tables. I then calculate sigma
statistics (sum((observed-expected)^2)/(N-1)) for the number of items
in the buckets of those tables.

Here are the sum(sigma) results I am getting in my tests:
string_hash1       sum(sigma) ~= 30K
string_hash3       sum(sigma) ~= 23-24K
string_hash6       sum(sigma) ~= 23-34K
string_hashRandom  sum(sigma) ~= 23-24K


Maddeningly, I havent been able to translate these near-perfect
distributions into improvements in pystones.

With the current hash function, pystone does an average of 1.2 probes in
the lookdict_string() function. With either of these "near-perfect" hash
functions, it does at best 1.3 probes (given exhaustive searches for
'good' shift paramaters, though not multipliers).

Im not sure what other tests to try out, or how I might go about
tweaking the hashes to perform better in pystone. Im hoping that someone
on python-dev has some experience in testing hash functions, and can
suggest some additional tests and/or tweaks.