MIME-Version: 1.0
In-Reply-To: <20160429025751.8368.qmail@ns.horizon.com>
References: <20160429025751.8368.qmail@ns.horizon.com>
Date: Thu, 28 Apr 2016 20:16:02 -0700
Message-ID: <CA+55aFxS9zZ8Gpyg9cn=xgkamx-G6dDZ3DTR2B=iQzXYcAhGoQ@mail.gmail.com>
Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism
From: Linus Torvalds <torvalds@linux-foundation.org>
To: George Spelvin <linux@horizon.com>
Cc: Thomas Gleixner <tglx@linutronix.de>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset=UTF-8
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1344
Lines: 32

On Thu, Apr 28, 2016 at 7:57 PM, George Spelvin <linux@horizon.com> wrote:
>
> How many 32-bit platforms nead a multiplier that's easy for GCC to
> evaluate via shifts and adds?
>
> Generlly, by the time you've got a machine grunty enough to
> need 64 bits, a multiplier is quite affordable.

Probably true.

That said, the whole "use a multiply to do bit shifts and adds" may be
a false economy too. It's a good trick, but it does limit the end
result in many ways: you are limited to (a) only left-shifts and (b)
only addition and subtraction.

The "only left-shifts" means that you will always be in the situation
that you'll then need to use the high bits (so you'll always need that
shift down). And being limited to just the adder tends to mean that
it's harder to get a nice spread of bits - you're basically always
going to have that same carry chain.

Having looked around at other hashes, I suspect we should look at the
ones that do five or six shifts, and a mix of add/sub and xor. And
because they shift the bits around more freely you don't have the
final shift (that ends up being dependent on the size of the target
set).

It really would be lovely to hear that we can just replace
hash_int/long() with a better hash. And I wouldn't get too hung up on
the multiplication trick. I suspect it's not worth it.

              Linus