hash table access time

[Scott Cyphers <Cyphers@scrc-yukon.arpa>]

    Date: Mon, 24 Aug 87 16:58:30 PDT
    From: Robert Kasper <kasper@vaxa.isi.edu>


    To frequent hashers:

    We've just done some timings to compare hash-table
    access speed with assoc-list access speed,
    on a Symbolics using a Genera 7.1 system.

    For EQL hash-tables, the access time was roughly
    the same as the time to find the last element of
    an assoc-list with 19 elements.

    Note that, on the average, it is only necessary to search
    half of an assoc-list, so the threshold of hash-table usefulness
    is something greater than 35 elements.
    I was surprised that it was this high,
    since hash-tables are supposed to be designed to optimize access time.
    Does anyone know what makes hashing this slow?
    Is it simply because the numerical hashing operations
    are much slower than list access operations on the lisp machine hardware?

ASSOC with a test of EQL is microcoded.  On a 3640, the microcoded
version is about twice as fast as an equivalent version in Lisp.  (If
the alist is cdr-coded, then the microcode is almost three times as
fast.)  In the Lisp vs. Lisp competition, the 19 and 35 are halved,
which is probably more in line with what you were expecting.

    Hash-table access fared even worse compared to assoc-lists
    on a TI Explorer system, so this is not just
    a quirk of Symbolics systems.

    Does anyone know of any tricks to make hash-table access faster?

     -- Bob Kasper
	USC/Information Sciences Institute
	ARPANET: KASPER@VAXA.ISI.EDU