Re: Size of hash tables was Re: Masters course ...

Matthias Neeracher <neeri@iis.ee.ethz.ch>
4 Jan 2003 22:45:56 -0500

          From comp.compilers
Related articles
Masters course with compiler specialization jeremy.wright@microfocus.com (Jeremy Wright) (2002-11-12)
Re: Masters course with compiler specialization Trevor.Jenkins@suneidesis.com (2002-12-11)
Re: Masters course with compiler specialization etechweb@yahoo.com (2002-12-19)
Size of hash tables was Re: Masters course with compiler specializat Trevor.Jenkins@suneidesis.com (2002-12-22)
Re: Size of hash tables was Re: Masters course ... joachim_d@gmx.de (Joachim Durchholz) (2002-12-30)
Re: Size of hash tables was Re: Masters course ... neeri@iis.ee.ethz.ch (Matthias Neeracher) (2003-01-04)
Re: Size of hash tables was Re: Masters course ... bonzini@gnu.org (2003-01-04)
Re: Size of hash tables was Re: Masters course ... stephan@stack.nl (Stephan Eggermont) (2003-01-07)
| List of all articles for this month |
From: Matthias Neeracher <neeri@iis.ee.ethz.ch>
Newsgroups: comp.compilers
Date: 4 Jan 2003 22:45:56 -0500
Organization: Integrated Systems Laboratory, ETH, Zurich
References: 02-11-060 02-12-056 02-12-092 02-12-107 02-12-127
Keywords: symbols, design
Posted-Date: 04 Jan 2003 22:45:56 EST

Joachim Durchholz <joachim_d@gmx.de> writes:


> Trevor Jenkins wrote:
>>
>> Since the publication of Maurer's paper "An improved hash code for
>> scatter storage" in the Comm of the ACM (vol 11, Jan 1968, pp 35--38)
>> it is taken as gospel that hash tables only work if the size is a
>> prime number.


> Not "only work". Just "distribute their keys in a more random fashion,
> assuming you don't have a priori knowledge about key distribution".


Agreed up to this point.


> I don't see how this argument has been invalidated. Particularly on modern
> hardware, where division and bit masking have roughly the same execution
> cost. Could anybody clarify?


I disagree about "roughly the same execution cost". On a PowerPC 750
(a.k.a. G3), an integer divide takes 19 cycles (and to get the
remainder, you need to multiply back and subtract, pushing the total
to about 25 cycles), while a logical and takes 1 cycle.


I don't know about other architectures, but I'd be surprised if the situation
were fundamentally different on most of them.


Matthias


--
Matthias Neeracher <neeri@iis.ee.ethz.ch> http://www.iis.ee.ethz.ch/~neeri

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.