[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
hash table access time
Date: Mon, 24 Aug 87 16:58:30 PDT
From: Robert Kasper <email@example.com>
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