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
Hash clash in polymorphic variants
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-01-14 (15:44)
From: Kuba Ober <ober.14@o...>
Subject: Re: [Caml-list] Re: Hash clash in polymorphic variants
On Monday 14 January 2008, David Allsopp wrote:
> 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...

A trivial solution to that is to keep both, as obviously each time an 
equivalent of dlopen() is made, everything has to be rehashed. gperf 
is "slightly" memory-hungry, so surely it'd need to be something using a 
different algorithm. I'm talking hypothetically, but I also think it's a 
weird design decision to use those possibly-colliding hashes. String 
sorting/comparison isn't exactly a CPU killer, so couldn't the original names 
have been used instead? I admit not to knowing too many details of the 
current implementation of course ;(

Cheers, Kuba