[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

hash table access time

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?

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