From owner-freebsd-hackers@FreeBSD.ORG Tue May 6 13:30:37 2008 Return-Path: Delivered-To: hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id E37681065671 for ; Tue, 6 May 2008 13:30:37 +0000 (UTC) (envelope-from jbucht@gmail.com) Received: from rv-out-0506.google.com (rv-out-0506.google.com [209.85.198.225]) by mx1.freebsd.org (Postfix) with ESMTP id BC8A58FC20 for ; Tue, 6 May 2008 13:30:37 +0000 (UTC) (envelope-from jbucht@gmail.com) Received: by rv-out-0506.google.com with SMTP id b25so599855rvf.43 for ; Tue, 06 May 2008 06:30:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; bh=46KO+xadqiHDZQ2iAFQXRTd0uZx6yODPIMXCZGzRRDI=; b=rBiMXGpAR8oL9FVEm7RGWIwP4RUZFF53bV/c16WwnPudybL7GH0ug4NkfQeZRPmTPB4g3D6Y++rY2in1O8FOn5hCc0AW3EVt3x1dc6nB0T1voskMfbJL64KCXJpnkDo6n961Mvpv0RzRpnIfIVcILySooy7uf/utaJfkGosyrxc= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=Kg/JTPZydoPqeCq9gYrlb/zi8kv+zhXhxyzDWH1Gk3kkabZ+GrdHFPkJ/WEVZ4Te5UWpM50mKZLmTzKQEjNRXN72aBAYl7+yxg6V9lbrsxFPAY6wiUP94BmjJQjPJGeH5Na2p4DhW7bFIrwBSUZ1TxoAwkGOIOuE0oPy8sgB2QE= Received: by 10.140.164.6 with SMTP id m6mr328773rve.210.1210079195583; Tue, 06 May 2008 06:06:35 -0700 (PDT) Received: by 10.140.166.16 with HTTP; Tue, 6 May 2008 06:06:35 -0700 (PDT) Message-ID: <947010c30805060606l1a92d56ayfc7e08e179baf5cc@mail.gmail.com> Date: Tue, 6 May 2008 06:06:35 -0700 From: "Johan Bucht" To: hackers@freebsd.org In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <20080505204350.GA45321@freebsd.org> <20080506062556.GA68171@zim.MIT.EDU> <20080506074830.GA70848@freebsd.org> Cc: Adrian Chadd , Roman Divacky Subject: Re: hashinit versus phashinit 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: Tue, 06 May 2008 13:30:38 -0000 On Tue, May 6, 2008 at 5:08 AM, Adrian Chadd wrote: > 2008/5/6 Roman Divacky : > > > > > > Most general-purpose hash implementations I've used (e.g., GNU > > > libstdc++, Sun JDK, Microsoft .NET) use prime table sizes, > > > probably to make it less likely that programmers will shoot > > > themselves in the foot with pathological data or bad hash functions. > > > > yes... a division takes roughly 40 cycles on modern i386 hw, while > > and is just 1, but does it matter compared to the access times of > > memory these days? > > > > the ratio between cpu-speed/mem-speed has changed a lot. I am not > > arguing if it's still true that avoiding the division helps the performance > > these days... > > My 2c - I'd poke the assembler, a book or two on current > architectures, and combine it with some benchmarking followed by > logical reasoning. > > Modern microprocessors don't execute instructions like they used to > before I was born; "divide versus logical shift/operator" speed may be > secondary to pipeline and IU effects, memory access (as mentioned > before), etc. > > (I know its not much - but I'm a firm believer in "Science!", and this > is one of those questions which can be understood with a little bit of > it..) > > If a hash algorithm relies on prime sized tables to produce uniform results it's a bad hash algorithm. =) http://burtleburtle.net/bob/hash/index.html is a recommended read, especially the article for Dr Dobb's. /Johan