Date: Sat, 30 Apr 2016 15:02: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+55aFys0Qtca-dwSVMDf0q4UEsXteFtCNcLsi=9rOqLr2b7ZQ@mail.gmail.com>
Message-ID: <alpine.DEB.2.11.1604301432570.3692@nanos>
References: <20160428161742.363543816@linutronix.de> <20160428163525.495514517@linutronix.de> <CA+55aFzMtEVc_5QS8EUvdKYfNMmJ9fpgcM4iEhdwaY1Oe=JYmw@mail.gmail.com> <alpine.DEB.2.11.1604290119320.3718@nanos>
 <CA+55aFys0Qtca-dwSVMDf0q4UEsXteFtCNcLsi=9rOqLr2b7ZQ@mail.gmail.com>
User-Agent: Alpine 2.11 (DEB 23 2013-08-11)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1641
Lines: 57

On Thu, 28 Apr 2016, Linus Torvalds wrote:
> It's the hashes that _look_ like they might be good hashes, but
> there's not a lot of analysis behind it, that I would worry about. The
> simple prime modulus _should_ be fine, but at the same time I kind of
> suspect we can do better. Especially since it has two multiplications.
> 
> Looking around, there's
> 
>     http://burtleburtle.net/bob/hash/integer.html
> 
> and that 32-bit "full avalanche" hash in six shifts looks like it
> could be better. You wouldn't want to inline it, but the point of a
> full avalanche bit mixing _should_ be that you could avoid the whole
> "upper bits" part, and it should work independently of the target set
> size.

Yes. So I tested those two:

u32 hash_64(u64 key)
{
       key  = ~key + (key << 18);
       key ^= key >> 31;
       key += (key << 2)) + (key << 4);
       key ^= key >> 11;
       key += key << 6;
       key ^= key >> 22;
       return (u32) key;
}

u32 hash_32(u32 key)
{
       key = (key + 0x7ed55d16) + (key << 12);
       key = (key ^ 0xc761c23c) ^ (key >> 19);
       key = (key + 0x165667b1) + (key <<  5);
       key = (key + 0xd3a2646c) ^ (key <<  9);
       key = (key + 0xfd7046c5) + (key <<  3);
       key = (key ^ 0xb55a4f09) ^ (key >> 16);
       return key;
}

They are really good and the results are similar to the simple modulo prime
hash. hash64 is slightly faster as the modulo prime as it does not have the
multiplication.

I'll send a patch to replace hash_64 and hash_32.

Text size:
	   x86_64	i386	arm
hash_64	   88		148	128
hash_32	   88		84	112

So probably slightly too large to inline.

Thanks,

	tglx