English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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-29 (12:27)
From: Dan Grossman <danieljg@c...>
Subject: Re: Alternative generic hash function

[Veuillez me pardonner; je ne donne pas une traduction en français parce
que j'ai peur de petites fautes qui peut changer sévèrement la

Francois Pottier wrote:
> Currently, mutable and immutable structures cannot be distinguished at
> runtime. This would require maintaining additional type information,
> and would probably introduce a lot of overhead.

Why do you think the overhead would be high?

I agree that:
* Changing the compiler and runtime system is a fair amount of work.
* A slightly different hash function does not justify the cost.
* The cost for recording mutability __per-field__ is probably large.

But I do not see why the __per-object__ overhead would be large.  From
my reading of the OCaml sources, it seems that:
* It is trivial for the compiler to maintain this information all the
way down to an allocation site.  At that point, it suffices to use a
different bytecode or native-code sequence to record that the object 
has at least one mutable field.
* Recording this information would only require 1 header bit.  (I
personally could live with 21 size bits.)  Getting this bit into the
header word should not be hard.
* Checking mutability dynamically would also be cheap.

I ask because there are plenty of clever tricks you can put in the
runtime system that exploit the immutability of objects.  Is there a
deeper problem I am missing?


| Dan Grossman     www.cs.cornell.edu/home/danieljg H:607 256 0724 |
| 5157 Upson Hall  danieljg@cs.cornell.edu          O:607 255 9834 |