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

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

On Friday 11 January 2008, Jon Harrop wrote:
> On Friday 11 January 2008 13:30:29 Kuba Ober wrote:
> > Are those collisions of any real importance? I mean, do they break
> > anything? If all they do is imply linearly searching a list of a few
> > elements, for the colliding entry, then it's a non-issue?
>
> It would prevent code from compiling so it would be a complete
> show-stopper.

So what you're saying is that the implementation uses the hash with bucket 
size of 1? That's kinda poor decision, methinks.

Maybe perfect hashes should be used, computed at link time (and at runtime 
whenever a module is linked in). The pefect hashing function could probably 
implement some sort of a table, so that no real code would need to be
generated, just recomputing of decision tree table. Gperf code could be
adapted for that. The benefit is that there would be no collisions, the hashed
data structure would be very compact, and the cost to regenerate the hash is
amortized. Ideally, one would generate the actual perfect hashing function,
but this is currently only possible in bytecode, right? I mean, toplevel won't
run in native code? Or am I mistaken?

Kuba