Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Alternative generic hash function
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2000-05-30 (20:34)
From: Dan Grossman <danieljg@c...>
Subject: Re: Alternative generic hash function

Francois Pottier wrote:
> > there are plenty of clever tricks you can put in the runtime system
> > that exploit the immutability of objects.
> Would you care to elaborate? I am no compiler expert, but I'm not sure
> why it would be so interesting to have this information at runtime,
> where it is already too late to do code optimization.  That would allow
> implementing the `pure' hash function proposed by Manuel Fähndrich, but
> with a cost: the user would have to separate the mutable fields into a
> sub-object, so as to allow the root object to be tagged as immutable.
> Which other tricks do you have in mind?

I think the tricks fall into two categories but none of the tricks may
apply to the current OCaml system.

The first category is optimizing code by dynamically choosing between 
a version that only works for immutable data and one that does not.  The
basic idea is that it is not "too late" so long as you have both
versions available.  The dynamic check is inexpensive, especially if it
is hoisted out of a loop.  Now with OCaml as your source language, I
believe having dynamic checks is worthless because the mutability of an
object is always determined for a program point.  That is, this
information is available statically.  But from a sufficiently low-level
viewpoint, we could consider this an artifact of the source language.

The second category is in the runtime system.  Here, most of the code
does not know whether the object it is manipulating is mutable.  How
could we use this information?  I could imagine having one nursery
(allocation area) for mutable and immutable objects, but then have the
minor collector segregate on mutability.  Segregation is particularly
useful in conjunction with "card marking" which the OCaml system does
not use.  But it could help the memory system performance of the OCaml
major collector as well.

Some more radical ideas I have been playing around with involve using
runtime value information to optimize data representation.  Knowing that
some values cannot change (due to the immutability bit) can enable the
run-time system to perform some transformations, perhaps during garbage

A final idea is that an incremental garbage collector could optimize its
treatment of immutable objects.  Assuming mutable objects are uncommon,
incremental collection costs could decrease significantly.


| Dan Grossman H:607 256 0724 |
| 5157 Upson Hall          O:607 255 9834 |