Skip to contentSkip to conversation

Near-constant time directory index for Ext2

RFC [email protected] 3 participants 5 messages Feb 23, 2001 – Feb 24, 2001

lore
Share & tools
lore
#0 lore raw
Quoted 8 lines
Quoted 1 line

idea of using crc32 as the default hash function

I once liked those things, too - but I've learned better since.

A universal class of hashing functions is a class with the property that given any input, the average performance of all the functions is good. For example, h(k) = (a * k + b) mod m with integers a != 0 and b is a universal class of hash functions.

Here a != 0 should be (a,m) = 1.

Quoted 1 line

for(i=0; *s; s++) i = 131*i + *s;

Yes, that is a good function.

(Also because 131 has only 3 bits, so that there is a cheap shift and add implementation.)

I did some random tests, on the one hand on a collection of 557398 file names (last part of path names) in a file system here.
On the other hand on an artificially generated sequence of file names with increasing number tails: foo0001, foo0002, ...

On the first collection the choice of multiplier didnt really matter provided that it was odd and not too close to a power of two. The smallest number with good behaviour was 11, the winner was 51.

(51 has 4 bits, but is not more expensive because they are evenly spaced:

	/* 51x = 17*3*x */
	x += (x << 1);
	x += (x << 4);

)

On the second collection there were large differences between multipliers. The clear winner was 11.

Some numbers:

Hash 557398 actual names, using

	hash(unsigned char *s) {
	        unsigned int h = 0;

		while(*s)
			h = m*h + *s++;
		return h % sz;
	}

for various values of m and powers of two sz (so that the % is an AND). Report min, max, average length of hash chain, and standard deviation. Of course min and max should be close to average and stddev should be small.

m= 11 sz=2048, min 221, max 324, av 272.17, stddev 254.12 m= 13 sz=2048, min 219, max 322, av 272.17, stddev 259.96 m= 51 sz=2048, min 218, max 325, av 272.17, stddev 265.52 m=131 sz=2048, min 222, max 344, av 272.17, stddev 264.20

m= 11 sz=4096, min 96, max 176, av 136.08, stddev 132.58 m= 13 sz=4096, min 101, max 177, av 136.08, stddev 128.71 m= 51 sz=4096, min 92, max 174, av 136.08, stddev 130.89 m=131 sz=4096, min 85, max 180, av 136.08, stddev 131.99

m= 11 sz=8192, min 38, max 102, av 68.04, stddev 68.26 m= 13 sz=8192, min 42, max 100, av 68.04, stddev 66.30 m= 51 sz=8192, min 41, max 97, av 68.04, stddev 64.98 m=131 sz=8192, min 39, max 102, av 68.04, stddev 66.19

m= 11 sz=16384, min 14, max 57, av 34.02, stddev 33.96 m= 13 sz=16384, min 14, max 58, av 34.02, stddev 33.51 m= 51 sz=16384, min 15, max 60, av 34.02, stddev 32.29 m=131 sz=16384, min 16, max 59, av 34.02, stddev 33.94

m= 11 sz=32768, min 3, max 37, av 17.01, stddev 17.50 m= 13 sz=32768, min 3, max 34, av 17.01, stddev 16.84 m= 51 sz=32768, min 4, max 41, av 17.01, stddev 16.46 m=131 sz=32768, min 3, max 40, av 17.01, stddev 16.90

m= 11 sz=65536, min 0, max 24, av 8.51, stddev 8.70 m= 13 sz=65536, min 0, max 23, av 8.51, stddev 8.56 m= 51 sz=65536, min 0, max 24, av 8.51, stddev 8.31 m=131 sz=65536, min 0, max 23, av 8.51, stddev 8.51

m= 11 sz=131072, min 0, max 17, av 4.25, stddev 4.39 m= 13 sz=131072, min 0, max 16, av 4.25, stddev 4.32 m= 51 sz=131072, min 0, max 16, av 4.25, stddev 4.22 m=131 sz=131072, min 0, max 16, av 4.25, stddev 4.24

m= 11 sz=262144, min 0, max 12, av 2.13, stddev 2.20 m= 13 sz=262144, min 0, max 12, av 2.13, stddev 2.18 m= 51 sz=262144, min 0, max 12, av 2.13, stddev 2.12 m=131 sz=262144, min 0, max 12, av 2.13, stddev 2.12

On the second, nonrandom, collection there are more variations:

m= 11 sz=8192, min 61, max 76, av 68.04, stddev 4.41 m= 13 sz=8192, min 55, max 83, av 68.04, stddev 18.64 m= 51 sz=8192, min 58, max 79, av 68.04, stddev 12.47 m=131 sz=8192, min 52, max 83, av 68.04, stddev 29.05

m= 11 sz=16384, min 26, max 41, av 34.02, stddev  3.61
m= 13 sz=16384, min 24, max 45, av 34.02, stddev  8.76
m= 51 sz=16384, min 25, max 44, av 34.02, stddev  6.32

m=131 sz=16384, min 23, max 47, av 34.02, stddev 14.00

m= 11 sz=32768, min 10, max 23, av 17.01, stddev 4.36 m= 13 sz=32768, min 7, max 28, av 17.01, stddev 8.66 m= 51 sz=32768, min 10, max 25, av 17.01, stddev 4.04 m=131 sz=32768, min 6, max 27, av 17.01, stddev 8.66

Andries

#1 lore raw

Hi,

I while ago I did some experimentation with simple bit-op based string hash
functions. I.e., no multiplications / divides in the hash loop.

The best I found was:

int hash_fn (char * p)
{
int hash = 0;

  while (*p) {
     hash = hash + *p;
     // Rotate a 31 bit field 7 bits:
     hash = ((hash << 7) | (hash >> 24)) & 0x7fffffff;

}
return hash;
}

[I haven't kept my test program / data set - if anyone compares the above
to the others functions mentioned on the list, let me know.]

The 31 and 7 were determined experimentally. But the 31 has a theoretical
explanation (which might even be valid):

The rotate is equivalent to a multiplication by x**7 in Z_2[P=0], where P is the polynomial x**31 - 1 (over Z_2).
Presumably the "best" P would be irreducible - but that would have more bits set in the polynomial, making reduction harder. A compromise is to choose P in the form x**N - 1 but with relatively few factors. X**31 - 1 is such a P.

Also, a 32 bit rotate (modulo X**32 - 1, which is equal to (X - 1) ** 32 over Z_2), came out pretty badly.

One thing that shouldn't be forgotten about hashing for hash tables is that you have to reduce the hash value to the required range - doing that well greatly reduces the difference between various hash functions.

Ralph.

#2 lore raw
In reply to [email protected]
Quoted 8 lines · Ralph Loader

A while ago I did some experimentation with simple bit-op based string hash functions. I.e., no multiplications / divides in the hash loop.

The best I found was:

int hash_fn (char * p)
{
int hash = 0;

Quoted 7 lines
  while (*p) {
     hash = hash + *p;
     // Rotate a 31 bit field 7 bits:
     hash = ((hash << 7) | (hash >> 24)) & 0x7fffffff;

}
return hash;
}

Hmm. This one goes in the "catastrophic" category.

For actual names:

N=557398, m=51 sz=2048, min 82, max 4002, av 272.17, stddev 45122.99

For generated names:

N=557398, m=51 sz=2048, min 0, max 44800, av 272.17, stddev 10208445.83

A very non-uniform distribution.

Quoted 6 lines

The rotate is equivalent to a multiplication by x**7 in Z_2[P=0], where P is the polynomial x**31 - 1 (over Z_2).
Presumably the "best" P would be irreducible - but that would have more bits set in the polynomial, making reduction harder. A compromise is to choose P in the form x**N - 1 but with relatively few factors. X**31 - 1 is such a P.

It has seven irreducible factors. Hardly "almost irreducible".

Shifting the 7-bit ASCII characters over 7 bits makes sure that there is very little interaction to start with. And the final AND that truncates to the final size of the hash chain kills the high order bits. No good.

Andries

#3 lore raw

Andries,

Quoted 1 line

is very little interaction to start with. And the final AND that

truncates

Quoted 2 lines

to the final size of the hash chain kills the high order bits. No good.

I didn't realise you were bit-masking down to the required size.

Yes, it would be pretty useless in that case.

Ralph.

Quoted 5 lines

Andries

#4 lore raw
In reply to Guest section DW

Andries,

Quoted 16 lines
Quoted 10 lines

int hash_fn (char * p)
{
int hash = 0;

  while (*p) {
     hash = hash + *p;
     // Rotate a 31 bit field 7 bits:
     hash = ((hash << 7) | (hash >> 24)) & 0x7fffffff;

}
return hash;
}

Hmm. This one goes in the "catastrophic" category.

Quoted 8 lines

For actual names:

N=557398, m=51 sz=2048, min 82, max 4002, av 272.17, stddev 45122.99

For generated names:

N=557398, m=51 sz=2048, min 0, max 44800, av 272.17, stddev 10208445.83

Instead of masking the hash value down to 11 bits you could try:

index = (hash ^ (hash >> 11) ^ (hash >> 22)) & 0x7ff;

I ran a quick test which gave fairly good results with that: 12871 identifiers
from a source tree) gave a mean square bucket size of 45.65, expected value for a random function is 45.78.

That change might improve some of your other hashes as well - there doesn't
seem to be much point in computing a 32 bit value only to throw 20 bits away -
stirring in the extra bits makes much more sense to me.

Quoted 9 lines
Quoted 7 lines

The rotate is equivalent to a multiplication by x**7 in Z_2[P=0],

where P is the polynomial x**31 - 1 (over Z_2).
Presumably the "best" P would be irreducible - but that would have more bits set in the polynomial, making reduction harder. A compromise is to choose P in the form x**N - 1 but with relatively few factors. X**31 - 1 is such a P.

It has seven irreducible factors. Hardly "almost irreducible".

I didn't say it was. "almost irreducible" polynomials with Hamming weight two are pretty rare... Relative to say, x**32 - 1 or x**24 - 1, having 7 factors is good.

Ralph.