Re: Red Gnus v0.76 is released

[Jim Meyering <meyering@asic.sc.ti.com>]

Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:
| Thu Dec 12 18:18:11 1996  David Moore  <dmoore@ucsd.edu>
| 
| 	* gnus-util.el (gnus-create-hash-size): Power of 2 hashtables can
| 	be _significantly_ faster than 2^x-1 tables on many risc
| 	machines.  Any gains of 2^x-1 are comparably small on other
| 	machines. 

Hi.

Have you considered any other implications of changing the table size
to be a power of 2?  It's pretty generally accepted that hash tables
get better key distributions (fewer collisions) when the table size
is a prime -- or has relatively few factors.  A bad table size (and
powers of 2 are notoriously bad) can make the normally-very-efficient
(O(1)) insert/delete/lookup operations abyssymally slow O(n) ones.

I suspect that choosing table size == 2^N (rather than the
usually-good and sometimes-even-prime 2^N - 1) would degrade the
efficiency due to the increased frequency of collisions.

Whether this matters depends on how full the tables may become.
If they're always nearly empty, then don't worry.  If they ever
contain more than say, 0.6 * table_size elements, I'd start to worry.
In general, if you have the memory, it's best to keep your tables
under 75% full.  That latter is from Knuth.  The 0.6 is my gut
feeling.  The 2^N business is from memory of Knuth and probably
others.