Re: Red Gnus v0.76 is released

[David Moore <dmoore@UCSD.EDU>]

Jim Meyering <meyering@asic.sc.ti.com> writes:

> 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've looked into this yes, and it's not as large of a problem
with bucket hashs as it is with quadratic rehashing, typically.  With
the ~12,864 newgroups on my site placed in both 16,384 and 16,383 size
hashtable using the xemacs hash function the number, the collision rate
was virtually the same (less than 5% fewer buckets in the power of 2,
although I can't say much about the chain size from lisp).  However, on
the sparc and some other risc processors, over 75% of the cost to
search/insert into the hashtable is in the modulo operation.

> 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.

	It tends to depend on your hash function and input data,
although I do usually use a rule of thumb of going to a larger table
when using power of two.  But again it only helps when your hash
function is still doing something reasonable.  I didn't bother doubling
the hashtable size here, because I was mostly after reasonable O(1)
operation, rather than 1 hit accesses.  I didn't think a 128k table in
memory was worth it, since the 64k table was doing fine.

-- 
David Moore <dmoore@ucsd.edu>       | Computer Systems Lab      __o
UCSD Dept. Computer Science - 0114  | Work: (619) 534-8604    _ \<,_
La Jolla, CA 92093-0114             | Fax:  (619) 534-1445   (_)/ (_)
<URL:http://oj.egbt.org/dmoore/>    | In a cloud bones of steel.