Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S1752101AbcD3PY3 (ORCPT <rfc822;w@1wt.eu>);
	Sat, 30 Apr 2016 11:24:29 -0400
Received: from www.linutronix.de ([62.245.132.108]:37509 "EHLO
	Galois.linutronix.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S1751439AbcD3PY2 (ORCPT
	<rfc822;linux-kernel@vger.kernel.org>);
	Sat, 30 Apr 2016 11:24:28 -0400
Date: Sat, 30 Apr 2016 17:22:47 +0200 (CEST)
From: Thomas Gleixner <tglx@linutronix.de>
To: Linus Torvalds <torvalds@linux-foundation.org>
cc: LKML <linux-kernel@vger.kernel.org>, Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        Sebastian Andrzej Siewior <bigeasy@linutronix.de>,
        Darren Hart <darren@dvhart.com>,
        Michael Kerrisk <mtk.manpages@googlemail.com>,
        Davidlohr Bueso <dave@stgolabs.net>, Chris Mason <clm@fb.com>,
        "Carlos O'Donell" <carlos@redhat.com>,
        Torvald Riegel <triegel@redhat.com>,
        Eric Dumazet <edumazet@google.com>
Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism
In-Reply-To: <CA+55aFyPCN4w6dpaf0p3iQnR=kqJpZ_-=noMVU328-_yDQq9WQ@mail.gmail.com>
Message-ID: <alpine.DEB.2.11.1604301712260.3692@nanos>
References: <20160428161742.363543816@linutronix.de> <20160428163525.495514517@linutronix.de> <CA+55aFzMtEVc_5QS8EUvdKYfNMmJ9fpgcM4iEhdwaY1Oe=JYmw@mail.gmail.com> <CA+55aFyPCN4w6dpaf0p3iQnR=kqJpZ_-=noMVU328-_yDQq9WQ@mail.gmail.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: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
Content-Length: 1363
Lines: 45

On Fri, 29 Apr 2016, Linus Torvalds wrote:
> Picking a new value almost at random (I say "almost", because I just
> started with that 32-bit multiplicand value that mostly works and
> shifted it up by 32 bits and then randomly added a few more bits to
> avoid long ranges of ones and zeroes), I picked
> 
>   #define GOLDEN_RATIO_PRIME_64 0x9e3700310c100d01UL
> 
> and it is *much* better in my test harness.
> 
> Of course, things like that depend on what patterns you test, But I
> did have a "range of strides and hash sizes" I tried. So just for fun:
> try changing GOLDEN_RATIO_PRIME_64 to that value, and see if the
> absolutely _horrid_ page-aligned case goes away for you?

It solves that horrid case:

   https://tglx.de/~tglx/f-ops-h64-t.png

It's faster than the shifts based version but the degradation with
hyperthreading is slightly worse.

Here for comparison the 64bit -> 32 shift version

  https://tglx.de/~tglx/f-ops-wang32-t.png

  FYI, that works way better than the existing shift machinery in hash_64

and the modulo prime one:

  https://tglx.de/~tglx/f-ops-mod-t.png

> It really looks like those multiplication numbers were very very badly picked.

Indeed.
 
> Still, that number doesn't do very well if the hash is small (say, 8
> bits).

I'm still waiting for the other test to complete. Will send numbers later
today.

Thanks,

	tglx