From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751461AbcEAIhh (ORCPT ); Sun, 1 May 2016 04:37:37 -0400 Received: from www.linutronix.de ([62.245.132.108]:38458 "EHLO Galois.linutronix.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750881AbcEAIhd (ORCPT ); Sun, 1 May 2016 04:37:33 -0400 Date: Sun, 1 May 2016 10:35:54 +0200 (CEST) From: Thomas Gleixner To: George Spelvin cc: eric.dumazet@gmail.com, linux-kernel@vger.kernel.org, riel@redhat.com, torvalds@linux-foundation.org Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism In-Reply-To: <20160430205235.24232.qmail@ns.horizon.com> Message-ID: References: <20160430205235.24232.qmail@ns.horizon.com> User-Agent: Alpine 2.11 (DEB 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Linutronix-Spam-Score: -1.0 X-Linutronix-Spam-Level: - X-Linutronix-Spam-Status: No , -1.0 points, 5.0 required, ALL_TRUSTED=-1,SHORTCIRCUIT=-0.0001 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sat, 30 Apr 2016, George Spelvin wrote: > Thomas Gleixner wrote: > You say that > > hash64 is slightly faster as the modulo prime as it does not have the > > multiplication. > > Um... are you sure you benchmarked that right? The hash_64 code you > used (Thomas Wang's 64->32-bit hash) has a critical path consisting of 6 > shifts and 7 adds. I can't believe that's faster than a single multiply. Sorry I did not express myself clear enough. hash64 (the single multiply with the adjusted golden ratio) is slightly faster than the modulo one which has two mutiplications. So here is the list: hash_64(): (key * GOLDEN_RATIO) >> (64 - bits) 31Mio Ops/sec modulo: 28Mio Ops/sec Thomas Wangs 64 -> 32 bit 21Mio Ops/sec Thanks, tglx