Re: interesting test of hash-table vs a-list

From: Erick Gallesio <eg_at_taloa.unice.fr>
Date: Sun, 2 May 1999 18:33:55 +0200 (CEST)

Brian Denheyer writes:
>
> I ran a simple test of hash-tables vs. a-lists, bith using eq?, to see
> where the "break-even" point was for efficiency in terms of accessing
> the elements.
>
> It turns out a-lists are with 10% of the running speed of hash-tables
> until there are > 60 elements in the list/table.
>
> I didn't expect the break-even to occur for that high a number, I
> figured it would occur down around 10 or 20 elements.
>
> Just thought I'd share the results :-)

That's interesting and ... hum rather disappointing . As you I thought
that the break should be at a number of element smaller than 60 (btw,
I have also made some tests and it seems for me that this number is
higher than 60 and rather 90 but, perhaps it varies depending of the
underlying architecture since the time for hash and a-list are quite
similar).

I found this result so astonish that I suspected that this was my
implementation which was not good. In fact it seems it was: when
you use a symbol as key the current implementation compute the hash
value by scanning the chars of the symbol. Of course, it seems a bad
idea since a key can be obtained by just taking the pointer to
the symbol as an integer (two identical symbols are eq?, so their
address is the same). So I replace the (long) computation of the
key value by a return of the address thinking to boost, not all the
tables, but at least your test ;-)

The effect was the contrary .... In fact it seems that computing
a key from a string yield a better repartition in the table and,
consequently, better performances of the hash table. I was not able to
establish this surely.

Consequently, I have not changed the current implementation of hash
table, but a good implementation could be to use a-list til we have
sufficiently elements in the list and switch to a true hash table after
that.

                -- Erick
Received on Sun May 02 1999 - 18:37:31 CEST