Re: hash-tables using equal? very inefficient ?

From: Erick Gallesio <eg_at_unice.fr>
Date: Wed, 24 Mar 1999 11:49:11 +0100 (CET)

Brian Denheyer writes:
>
> I re-wrote one of the hash tables I was using so that it was using
> string=? instead of equal?
>
> This made a big difference in performance.

Yes! This is because the hash table module take this special case into
account. In fact, STk hash tables use the Tcl hash tables
implementation which distinguish two cases (in fact 3 but I don't use
the 3rd case): general pointers and strings. The code is very
efficient for strings so if your hash table has strings keys, that is
if the comparison function is string=?, STk uses the more efficient
implementation.

>
> I was using a pair as a key and it looks as though, from looking at
> the code, that using an equal? hash is very expensive in terms of key
> calculation _and_ cons'ing.
>
It depends. If you can use eq? rather than equal? it will be faster
than strings since the computation of the hash value is direct (this
is the pointer itself, seen as an integer). If you have a string, as
said before we use a special hard-coded function, which is relatively
efficient. In the general case, the computation of a hash value
implies a recursive computation on all the components of the key.


                -- Erick
Received on Wed Mar 24 1999 - 12:22:18 CET