Hi,
In his message of Fri February 25, 2000, Stephan Houben writes:
>
> The interpreter often needs to search a hash table with a string
> as key. A common optimization for this is to use pointer identity
> instead of string equality, and "intern" every string before using
> it as a key to the hash table.
>
> Unfortunately, I don't see how to do this with the current O'Caml
> libs. You can do identity checks with ==, but there seems no way
> to get a good hash corresponding to ==.
>
> Has anyone already written some code for this task?
>
I guess it is very difficult to provide a good hash function
corresponding to == because the GC may move the block the string has
been allocated to at any time.
However, in older versions of Coq (http://coq.inria.fr) there was some
code achieving what you are looking for : roughly, identifiers were
internally represented as (unique) integers and we had two conversion
functions ident_of_string and string_of_ident (each time a new string
was interned through ident_of_string, a new integer was
allocated). Therefore, ident comparison was integer comparison, and we
had a hash function over idents.
NB : after a while, the code implementing this was removed from Coq
(we spent more time (re)interning terms than we saved...)
Judicaël Courant.
-- Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/ (+33) (0)1 69 15 64 85 "Montre moi des morceaux de ton monde, et je te montrerai le mien" Tim, matricule #929, condamné ŕ mort. http://rozenn.picard.free.fr/tim.html
This archive was generated by hypermail 2b29 : Fri Feb 25 2000 - 18:09:55 MET