From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 1A5FBBC69 for ; Mon, 14 Jan 2008 16:38:06 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAOIQi0fC2fJWnmdsb2JhbACQCgEBAQEHBAYpmBI X-IronPort-AV: E=Sophos;i="4.24,282,1196636400"; d="scan'208";a="6630911" Received: from anchor-post-36.mail.demon.net ([194.217.242.86]) by mail1-smtp-roc.national.inria.fr with ESMTP; 14 Jan 2008 16:38:05 +0100 Received: from orion.metastack.com ([80.177.38.218]) by anchor-post-36.mail.demon.net with esmtp (Exim 4.67) id 1JERNy-000NIU-K2 for caml-list@yquem.inria.fr; Mon, 14 Jan 2008 15:38:03 +0000 Received: from countertenor (cpc3-cmbg6-0-0-cust100.cmbg.cable.ntl.com [81.101.140.101]) (authenticated bits=0) by orion.metastack.com (8.13.4/8.13.3) with ESMTP id m0EFOe2U011903 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO) for ; Mon, 14 Jan 2008 15:24:41 GMT From: "David Allsopp" To: References: <200801101709.14110.jon@ffconsultancy.com><200801140720.02094.ober.14@osu.edu> <200801140956.25449.ober.14@osu.edu> Subject: RE: [Caml-list] Re: Hash clash in polymorphic variants Date: Mon, 14 Jan 2008 15:37:50 -0000 Organization: MetaStack Solutions Ltd. Message-ID: <001401c856c3$6c692260$6c7ba8c0@countertenor> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook 11 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3198 Thread-Index: AchWu9TaR42iNnD9SUKD/uX32lHjAwABIitw In-Reply-To: <200801140956.25449.ober.14@osu.edu> X-Scanned-By: MIMEDefang 2.63 on 172.16.28.218 X-Spam: no; 0.00; hash:01 variants:01 hash:01 hashing:01 inputs:01 inputs:01 runtime:01 hashing:01 hashes:01 foo:01 foo:01 bool:01 polymorphic:01 polymorphic:01 wrote:01 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.