Why MULT 31 (hash function for string)?

[Michael Wojcik]

Engineer: 3 is prime, 5 is prime, 7 is prime, 9 is an
observational error, 11 is prime, ...

Like Richard Harter, I think the version I heard ascribes this one
to a Physicist.

The Engineer version I know goes something like: 3 is prime, 5 is
prime, 7 is prime, 9 is ... OK, we have a 25% defect rate.

Programmer: 3 is prime, 5 is prime, 7 is prime, 9 is
prime, 11 is prime, ...

I've seen Programmer given the "looping" answer, though I think it
looped on 7 ("7 is prime, 7 is prime, ..."), which IMO makes more
sense - the solution breaks when it reaches the first input that it
doesn't handle correctly.

Another Programmer answer might be: 3 is prime, 5 is prime, 7 is
prime. All the test cases pass - let's ship.

Like the various humorous versions of Dining Philosophers, lightbulb
jokes, and so forth, this seems to be a generative structure. Here
are some other possibilities, off the top of my head:

Executive: 3 is prime, 5 is prime, 7 is prime, 9 is prime (for
accounting purposes), ...

Marketer: 3 is prime, 5 is prime, 7 is prime, 9 is Prime 2.0!, ...

Rhetorician: 3 is prime, 5 is prime, 7 is prime. Let us pass over
9 in silence, and dwell no more on its merits or faults. 11 is
prime...

Multiculturalist: 3 is prime, 5 is prime, 7 is prime. Excluding 9
from the primes would recapitulate the inequal relations inherent
in patriarchal-imperialist hegemony. Let us instead recognize that
9 is differently-primal.

Dadaist: 3 is prime, 5 is prime, 7 is prime, banana, 11 is prime...

 

[SM Ryan]

(e-mail address removed) (Richard Tobin) wrote:
# In article <[email protected]>,
#
# >Computer scientist:
# > 3 is prime, 5 is prime, 5 is prime, 5 is prime, 5 is prime, 5 is
# > prime, 5 is prime, ...
#
# Typical programmer:
#
# 3 is prime, 5 is prime, 6.9999999998 is prime, ...

Prove that all odd integers higher than 2 are prime:
-Chemist: 3 is prime, 5 is prime, 7 is prime... hey, let's publish!

-Computer programmer: "3 is prime, 5 is prime, 7 is prime, 9 is... 3 is
prime, 5 is prime, 7 is prime, 9 is... 3 is..."
Um, right. Okay, how about this:
"3 is not prime, 5 is not prime, 7 is not prime, 9 is not prime..."
So much for the beta releases. Ship this:
"3 is prime, 5 is prime, 7 is prime, 9 is a feature, 11 is prime..." and
put on the cover "More prime numbers than anyone else in the industry!"

-Drunk: 3 is an odd prime, 5 is an odd prime, 7 is an odd prime,
9 is a very odd prime...

-Economist: 3 is prime, 5 is prime, 7 is prime, 9 is not prime. Look,
the prime rate is dropping!

-Engineer: 3 is prime, 5 is prime, 7 is prime, 9 is... 9 is... well,
if you approximate, 9 is prime, 11 is prime, 13 is prime...

-Engineer: 3 is prime, 5 is prime, 7 is prime, 9 is not working. Hand
me the pliers.

-New Yorker: 3 is prime, 5 is prime, 7 is prime, 9 is... NONE OF YOUR
DAMN BUSINESS!

-Physicist: 3 is prime, 5 is prime, 7 is prime, 9 is... uh, 9 is an
experimental error, 11 is prime, 13 is prime...

-Theologist: 3 is prime and that's good enough for me!

 

[Chris Torek]

... 31 may be attractive because it is close to a power of two,
and it may be easier for the compiler to replace a possibly slow
multiply instruction with a shift and subtract (31*x == (x << 5)
- x) on machines where it makes a difference. Setting MULT one
greater than a power of two (e.g., 33) would also be easy to
optimize, but might produce too "simple" an arrangement: mostly a
juxtaposition of two copies of the original set of bits, with a
little mixing in the middle. So you want an odd MULT that has
plenty of one-bits.

I thought the same, some (ok, now "many") years ago, and suggested
trying both 31 and 33 back when the original Berkeley DB was being
written and tested.

On a number of sample data sets, it turns out that 33 performed
slightly better, given the way the hash value was used.

Because of the optimization issue (multiply into shift-and-add),
"multiply by 33 and add *p++" performed better than some other
"better" (in terms of bit distribution) algorithms. That is, the
other algorithms resulted in slightly fewer hash collisions, but
the time saved resolving such collisions was insufficient to make
up for the extra CPU time used calculating the more-complex hash
function.

Of course, this was in the 1990s, when 300 MHz was an amazingly
fast CPU.

 

[Samuel Stearley]

Because of the optimization issue (multiply into shift-and-add),
"multiply by 33 and add *p++" performed better than some other
"better" (in terms of bit distribution) algorithms. That is, the
other algorithms resulted in slightly fewer hash collisions, but
the time saved resolving such collisions was insufficient to make
up for the extra CPU time used calculating the more-complex hash
function.

So what cpu is this that can shift by 5 then add (mult by 33) faster
than it can shift by 5 and subtract (mult by 31) ?


Regarding the performance of mod operations:
On the powerPCs I use at work division takes 19 cycles.

 

[Chris Torek]

So what cpu is this that can shift by 5 then add (mult by 33) faster
than it can shift by 5 and subtract (mult by 31) ?

Hmm, I did realize, after I posted that, that what I wrote could
be misread that way. 33 produced *better* distributions (but only
very slightly) than 31, for the test data. So "h = (h*33) + c"
was better than "h = (h*31) + c". Other hash functions existed
that produced even-better distributions than either of those --
for instance, doing CRCs on the data -- but took sufficiently
longer, etc.

Regarding the performance of mod operations:
On the powerPCs I use at work division takes 19 cycles.

If the division instruction (and/or registers; see, e.g., MIPS)
can "free run" while the CPU does other things, *and* the C
compiler is able to insert "useful" instructions between the
start of the "divide" operation and the use of its result, the
cycles required for division can sometimes be hidden. For most
hash algorithms, however, there is just not enough insertable
work:

hash = compute_hash(key);
entry_ptr = table[hash % tablesize];
... do stuff with *entry_ptr ...

Here, there are usually no more than two or three instructions'
worth of work to move, which will take only a cycle or two, leaving
most of those 19 as "not executed in parallel with anything".

It is worth adding that the Berkeley DB code uses (used?) a
"variable-size power-of-two mod via mask" on the result of the hash
in this case, via code much (but not exactly) like this:

SOMETYPE lookup(SOMETYPE2 *table, const char *p) {
char *s;
unsigned char c;
unsigned int h;
SOMETYPE3 *entry_ptr;

for (h = 0; (c = *p) != 0; p++)
h = h * 33 + c;
entry_ptr = table->entries[h & table->mask];
while (entry_ptr != NULL)
if (entry_ptr->hash == h && strcmp(entry_ptr->key, p) == 0)
... found, stop looping ...
else
entry_ptr = entry_ptr->next;
}

(This is an "open chain" hash that is only suitable for in-memory
storage; Berkeley DB includes a bunch of methods that work better
for on-disk storage. The main advantage to open chain hashing is
that it is quite simple. In this case, the adjustable mask allows
the table size to be doubled whenever some desired "maximum load
factor" is exceeded.)