From owner-freebsd-hackers@FreeBSD.ORG Thu Jan 20 16:07:51 2011 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 73E8A1065672 for ; Thu, 20 Jan 2011 16:07:51 +0000 (UTC) (envelope-from alexander@leidinger.net) Received: from mail.ebusiness-leidinger.de (mail.ebusiness-leidinger.de [217.11.53.44]) by mx1.freebsd.org (Postfix) with ESMTP id 2A2D88FC1D for ; Thu, 20 Jan 2011 16:07:50 +0000 (UTC) Received: from outgoing.leidinger.net (p57B3B645.dip.t-dialin.net [87.179.182.69]) by mail.ebusiness-leidinger.de (Postfix) with ESMTPSA id A78F0844012; Thu, 20 Jan 2011 16:52:34 +0100 (CET) Received: from webmail.leidinger.net (unknown [IPv6:fd73:10c7:2053:1::2:102]) by outgoing.leidinger.net (Postfix) with ESMTP id 8919120F7; Thu, 20 Jan 2011 16:52:31 +0100 (CET) Received: (from www@localhost) by webmail.leidinger.net (8.14.4/8.13.8/Submit) id p0KFqG1V092595; Thu, 20 Jan 2011 16:52:16 +0100 (CET) (envelope-from Alexander@Leidinger.net) Received: from pslux.ec.europa.eu (pslux.ec.europa.eu [158.169.9.14]) by webmail.leidinger.net (Horde Framework) with HTTP; Thu, 20 Jan 2011 16:52:15 +0100 Message-ID: <20110120165215.1794698qw7ejr18g@webmail.leidinger.net> Date: Thu, 20 Jan 2011 16:52:15 +0100 From: Alexander Leidinger To: Gleb Kurtsou References: <20101223224619.GA21984@tops> In-Reply-To: <20101223224619.GA21984@tops> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; DelSp="Yes"; format="flowed" Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Dynamic Internet Messaging Program (DIMP) H3 (1.1.4) X-EBL-MailScanner-Information: Please contact the ISP for more information X-EBL-MailScanner-ID: A78F0844012.A6BA4 X-EBL-MailScanner: Found to be clean X-EBL-MailScanner-SpamCheck: not spam, spamhaus-ZEN, SpamAssassin (not cached, score=1.274, required 6, autolearn=disabled, RDNS_NONE 1.27) X-EBL-MailScanner-SpamScore: s X-EBL-MailScanner-From: alexander@leidinger.net X-EBL-MailScanner-Watermark: 1296143555.21337@dENTLu4SOwhfBQDCtUPCvQ X-EBL-Spam-Status: No X-Mailman-Approved-At: Thu, 20 Jan 2011 16:32:29 +0000 Cc: freebsd-hackers@freebsd.org Subject: Re: [rfc] Replacing FNV and hash32 with Paul Hsieh's SuperFastHash X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 20 Jan 2011 16:07:51 -0000 Quoting Gleb Kurtsou (from Fri, 24 Dec 2010 00:46:20 +0200): > Hi, > > I've recently noticed that hash table use in nullfs was inefficient, 1/3 > to half of buckets remained unused. I've started investigating it > further and came across SuperFastHash hashing function, SFH > (SuperFastHash) has BSD license, used in WebKit and other open source > projects. Detailed description and Comparision with FNV and Bob Jenkin's > hash can be found here: > http://www.azillionmonkeys.com/qed/hash.html I found some web pages which tell about an unfair speed comparision and about a collision problem in SFH: http://coding.derkeiler.com/Archive/General/comp.programming/2005-03/0650.html http://www.team5150.com/~andrew/blog/2007/03/breaking_superfasthash.html http://blog.clawpaws.net/post/2007/04/22/Good-Hash-Functions It may be that this is not an issue for the use case we have here, but blindly replacing it without looking at the above web pages looks a little bit risky to me. Bye, Alexander. -- The use of money is all the advantage there is to having money. -- Benjamin Franklin http://www.Leidinger.net Alexander @ Leidinger.net: PGP ID = B0063FE7 http://www.FreeBSD.org netchild @ FreeBSD.org : PGP ID = 72077137