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=1.0 required=5.0 tests=AWL,SPF_FAIL autolearn=disabled version=3.1.3 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 45D42BC6C for ; Mon, 14 Jan 2008 16:45:32 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAANMRi0fAXQImh2dsb2JhbACQCgEBAQgKKZgP X-IronPort-AV: E=Sophos;i="4.24,282,1196636400"; d="scan'208";a="7785521" Received: from discorde.inria.fr ([192.93.2.38]) by mail3-smtp-sop.national.inria.fr with ESMTP; 14 Jan 2008 16:45:31 +0100 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id m0EFjRxW022972 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Mon, 14 Jan 2008 16:45:31 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAABMSi0dQW+UCh2dsb2JhbACQCgEBAQgKKZgQ X-IronPort-AV: E=Sophos;i="4.24,282,1196636400"; d="scan'208";a="6022730" Received: from main.gmane.org (HELO ciao.gmane.org) ([80.91.229.2]) by mail2-smtp-roc.national.inria.fr with ESMTP; 14 Jan 2008 16:45:27 +0100 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1JERV7-0003tC-K5 for caml-list@inria.fr; Mon, 14 Jan 2008 15:45:25 +0000 Received: from 206-248-165-105.dsl.teksavvy.com ([206.248.165.105]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 14 Jan 2008 15:45:25 +0000 Received: from monnier by 206-248-165-105.dsl.teksavvy.com with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Mon, 14 Jan 2008 15:45:25 +0000 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Stefan Monnier Subject: Re: Hash clash in polymorphic variants Date: Mon, 14 Jan 2008 10:45:18 -0500 Message-ID: References: <200801101709.14110.jon@ffconsultancy.com> <200801140720.02094.ober.14@osu.edu> <200801140956.25449.ober.14@osu.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Complaints-To: usenet@ger.gmane.org X-Gmane-NNTP-Posting-Host: 206-248-165-105.dsl.teksavvy.com User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.50 (gnu/linux) Cancel-Lock: sha1:CFVdRLmug++MRps02XPI6HA082U= Sender: news X-Miltered: at discorde with ID 478B8397.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; hash:01 variants:01 hash:01 hashing:01 inputs:01 inputs:01 link-time:01 run-time:01 run-time:01 link-time:01 afaict:01 polymorphic:01 compile:01 clash:05 problem:05 >> > 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. That would require postponing the execution of the hash-function to link-time or run-time. Run-time is clearly undesirable, and link-time adds yet-more complexity to the linker. It's not a bad idea, obviously, but AFAICT the linker currently is kept very simple. Stefan