Version française
Home     About     Download     Resources     Contact us    
Browse thread
symbol managment in Caml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Judicael Courant <Judicael.Courant@l...>
Subject: Re: symbol managment in Caml

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