RE: [Caml-list] Re: Hash clash in polymorphic variants

["David Allsopp" <dra-news@metastack.com>]

Kuba Ober wrote:
> On Monday 14 January 2008, Stefan Monnier wrote:
> > > What I meant was simply that instead of using some fixed hash
> > > function, one could use a perfect hashing function which is optimal
> > > for its known set of inputs, and won't ever generate a collision.
> >
> > The problem is that the set of inputs is not know at compile time, only
> > at link time.
>
> As I've said in the cited post, the perfect hash generator would have to
> be invoked at link time, which shouldn't be a big deal.

Assuming you're talking hypothetically and designing a new runtime then,
yes, it's not a big deal.

However, this scheme could not just be dropped into the present system - it
would not work with dynamic linking because once you've hashed a polymorphic
variant tag-name you drop the name so you can't re-hash when you update your
perfect hashing function... unless you can devise a perfect hashing scheme
that hashes all the old keys to their old values and new ones to
non-clashing new values ;o)

Internally, `Foo is indistinguishable from the int 3505894* - so if
caml_hash_variant("Foo") suddenly changes value mid-program then any
previous instances of `Foo in memory cease to be equal to it!


David


* Try:
# (Obj.magic `Foo : int);;
- : int = 3505894
# (Obj.magic 3505894) = `Foo;;
- : bool = true

I don't know whether caml_hash_variant varies between version or even
platform so the actual number may be different on other systems.