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

[Kuba Ober <ober.14@osu.edu>]

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