🚀 go-pugleaf

In article <jgkDFv094.JKJ@netcom.com>, Joe Keane  <jgk@netcom.com> wrote:
>Whenever i find some important hash table, one of the changes that i make is:
>Take out that stupid `%' operator!
>
>People that don't have low-level knowledge of machines don't realize how slow
>that remainder operation is.  Of course, it depends on the machine, so it can
>range from rather slow to extremely slow.  With no exaggeration, a good hash
>table can do several lookups in the time it takes to compute one remainder.

Time required for % also depends on the modulus.  Remainders modulo 2^n, for
example, are really easy to compute.  Good compilers take advantage of this
whenever the modulus is known at compile time.

People who do hashing usually like primes.  There are some primes of the
form 2^n +- 1; remainders modulo such primes still do not require the full
force of a fully general remainder routine.  Most compilers I've seen do not
optimize this case, but they could--it's only a couple extra shifts and
adds over mod 2^n.
--
Mike Haertel <haertel@ichips.intel.com>