From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <ober.14@osu.edu>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.4 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE 
	autolearn=disabled version=3.1.3
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by yquem.inria.fr (Postfix) with ESMTP id CB13FBC69
	for <caml-list@yquem.inria.fr>; Mon, 14 Jan 2008 13:20:04 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Aq4HAHriikdDWxLC/2dsb2JhbACBVqYj
X-IronPort-AV: E=Sophos;i="4.24,281,1196636400"; 
   d="scan'208";a="21203879"
Received: from ip67-91-18-194.z18-91-67.customer.algx.net (HELO server1.bertec.net) ([67.91.18.194])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 14 Jan 2008 13:20:04 +0100
Received: from kuba.bertec.net (kuba.bertec.net [192.168.2.16])
	by server1.bertec.net (Postfix) with ESMTP id EBFE6105830
	for <caml-list@yquem.inria.fr>; Mon, 14 Jan 2008 07:20:02 -0500 (EST)
From: Kuba Ober <ober.14@osu.edu>
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Hash clash in polymorphic variants
Date: Mon, 14 Jan 2008 07:20:01 -0500
User-Agent: KMail/1.9.6 (enterprise 0.20071123.740460)
References: <200801101709.14110.jon@ffconsultancy.com> <200801111114.03876.ober.14@osu.edu> <000c01c85481$7f727120$6c7ba8c0@countertenor>
In-Reply-To: <000c01c85481$7f727120$6c7ba8c0@countertenor>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200801140720.02094.ober.14@osu.edu>
X-Spam: no; 0.00; hash:01 variants:01 non-issue:01 show-stopper:01 hash:01 variants:01 compiler:01 incorrectly:01 checker:01 hashing:01 hashing:01 inputs:01 link-time:01 run-time:01 cheers:01 

On Friday 11 January 2008, David Allsopp wrote:
> Kuba Ober wrote:
> > 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.
>
> I think you're missing the context - there's no hash table. See 18.3.6 in
> the manual - the hashed values (and resulting collisions) are to do with
> the internal representation of polymorphic variants.
>
> The compiler cannot process code that uses two polymorphic variants whose
> tag names will have the same internal representation (and therefore be
> incorrectly viewed as having the same value). The test is probably
> performed somewhere in the type checker...

Yeah, I sort of put the wagon ahead of the horse. Of course the hashing 
function doesn't imply a hash table.

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 tables that such a function uses to hash its input have to be generated at 
link-time, which means run-time too.

Cheers, Kuba