🚀 go-pugleaf

In article <DFLzD9.Anx@uns.bris.ac.uk>
David Shepherd <des@bristol.st.com> writes:
>Yes, even worse with remainder which may be very infrequent globally
>but one of the major uses is forming indices into hash tables where
>it is being used to speed up an application. I use a BDD based
>checker program which hashes BDD results where I discovered on a
>SparcStation 1 it was spending 25% of its time in the function
>call to implement remainder!

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.

In many applications, various hash tables are just critical to performance.
The most important thing for a hash table like this is for it to *go fast*;
things like good distribution of keys are useful only if they improve this.
For most applications, a simple shift-and-add works fine as a hash function.
Keeping the table size a power of two is easier for the machine, and it also
gives you a simple criterion for deciding when and how to resize the table.

Given how slow remainder is, i like the RISC approach of calling a function.
I *like* the SPARC because the remainder function shows up in profiling, so
you know who's calling it and how much time you're wasting.  You can fix this
on the SPARC and get the benefit on other machines, because it's most likely
at least as slow there, it's just less obvious since it's more spread out.

--
Joe Keane, professional programmer