symbol managment in Caml

symbol managment in Caml

[Stephan Houben]

Hello list,

I am writing an interpreter for a simple language in O'Caml.
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?

Thanks in advance,

Stephan

Re: symbol managment in Caml

[skaller]

Stephan Houben wrote:
> 
> Hello list,
> 
> I am writing an interpreter for a simple language in O'Caml.
> 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?

No, but may I suggest using a hashtable of references to strings?
The compiler will also need to keep a separate set of strings,
which the hash table entries reference. I'd be interested in a
performance
comparison (since I have a similar interpreter :-)

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net

Re: symbol managment in Caml

[Judicael Courant]

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

Re: symbol managment in Caml

[Claudio Sacerdoti Coen]

 Hello,

 I have had the same problem and I was about to write the
 new function when I stopped: the time taken by the hash
 function was not worth the extra coding.

 But I think that it's really a great pity that the
 standard library lacks such a function. Moreover, it
 should be really easy to implement it. Could we expect
 it implemented?

					Cheers,
					C.S.C.


On Fri, Feb 25, 2000 at 13:16:22 +0100, Stephan Houben wrote:
> Hello list,
> 
> I am writing an interpreter for a simple language in O'Caml.
> 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?
> 
> Thanks in advance,
> 
> Stephan

-- 
-----------------------------------------
Real Name: Claudio Sacerdoti Coen
Address: via del Colle n.6
	 S. Lazzaro di Savena (BO)
	 Italy
e-mail:  sacerdot@cs.unibo.it
-----------------------------------------

RE: symbol managment in Caml

[Frank A. Christoph]

[re: hashing identifiers]
>  I have had the same problem and I was about to write the
>  new function when I stopped: the time taken by the hash
>  function was not worth the extra coding.

Even if it takes more, or as much, time as comparing identifiers directly,
there is still an advantage to interning strings: you can share their
representations. Of course, if you don't expect much sharing, or you don't
expect to allocate many identifiers during any single run, it may still not
be worht it.

--fac

Re: symbol managment in Caml

[Sven LUTHER]

On Fri, Feb 25, 2000 at 01:16:22PM +0100, Stephan Houben wrote:
> Hello list,
> 
> I am writing an interpreter for a simple language in O'Caml.
> 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?

Be carefull about this, i had the same kind of idea, but found out that using
references in ocaml is not necessarily a good way of increasing speed, since
some kind of references operation are expensive, and can even trigger a minor
garbage collection wich can in turn start a major garbage collection, thus
making it very expensive.

i was using a small associative list (~15 entries) and it resulted that it was
faster than the reference using version.

Friendly,

Sven LUTHER