Date: Tue, 6 May 2008 06:06:35 -0700 From: "Johan Bucht" <jbucht@gmail.com> To: hackers@freebsd.org Cc: Adrian Chadd <adrian@freebsd.org>, Roman Divacky <rdivacky@freebsd.org> Subject: Re: hashinit versus phashinit Message-ID: <947010c30805060606l1a92d56ayfc7e08e179baf5cc@mail.gmail.com> In-Reply-To: <d763ac660805060508x4b5a506ew57151ee65263c2c4@mail.gmail.com> References: <20080505204350.GA45321@freebsd.org> <20080506062556.GA68171@zim.MIT.EDU> <20080506074830.GA70848@freebsd.org> <d763ac660805060508x4b5a506ew57151ee65263c2c4@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Tue, May 6, 2008 at 5:08 AM, Adrian Chadd <adrian@freebsd.org> wrote: > 2008/5/6 Roman Divacky <rdivacky@freebsd.org>: > > > > > > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?947010c30805060606l1a92d56ayfc7e08e179baf5cc>