From: "George Spelvin" <linux@horizon.com>
To: linux@horizon.com, tglx@linutronix.de
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
Date: 1 May 2016 05:43:58 -0400 [thread overview]
Message-ID: <20160501094358.4706.qmail@ns.horizon.com> (raw)
In-Reply-To: <alpine.DEB.2.11.1605011012020.3692@nanos>
> 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.
Yes, I figured out that was probably what you were talking about,
and benchmarked it similarly.
But I noticed a much greater difference.
Wang * PHI % 4093 Wang * PHI % 4093
13599486 3494816 5238442 13584166 3460266 5239463
13589552 3466764 5237327 13582381 3422304 5276253
13569409 3407317 5236239 13566738 3393215 5267909
13575257 3413736 5237708 13596428 3379811 5280118
13583607 3540416 5325609 13650964 3380301 5265210
At 3.7 GHz, that's
* PHI: 1059 M ops/second
* Modulo: 706 M ops/second
* Wang: 271 M ops/second
Of course, that's a tight loop hashing; I presume your test case
has more overhead.
Anyway, my recommendation (I'll write the patches if you like) is:
* Modify the multiplicative constants to be
#define COLDEN_RATIO_32 0x61C88647
#define COLDEN_RATIO_64 0x61C8864680B583EB
* Change the prototype of hash_64 to return u32.
* Create a separate 32-bit implementation of hash_64() for the
BITS_PER_LONG < 64 case. This should not be Wang's or anything
similar because 64-bit shifts are slow and awkward on 32-bit
machines.
One option is something like __jhash_final(), but I think
it will suffice to do:
static __always_inline u32 hash_64(u64 val, unsigned int bits)
{
u32 hash = (u32)(val >> 32) * GOLDEN_RATIO_32 + (u32)val;
hash *= GOLDEN_RATIO_32;
return hash >> (32 - bits);
}
(S-o-b on that if you want it, of course.)
(If you want it out of line, make a helper function that
computes the 32-bit hash and have an inline wrapper that
does the shifting.)
* Eliminate the !CONFIG_ARCH_HAS_FAST_MULTIPLIER code path. Once we've
got rid of the 32-bit processors, we're left with 64-bit processors,
and they *all* have hardware multipliers. Even the MIPS R4000 (first
64-bit processor ever) and Alpha 21064 had one.
(Admittedly, the R4000 was 20 cycles, which is slower than Wang's hash,
but 18 of them could overlap other instructions.)
The worst multiply support is SPARCv9, which has 64x64-bit
multiply with a 64-bit result, but no widening multiply.
* If you feel ambitious, add a 32-bit CONFIG_ARCH_HAS_SLOW_MULTIPLIER
exception path.
next prev parent reply other threads:[~2016-05-01 9:44 UTC|newest]
Thread overview: 43+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CA+55aFxBWfAHQNAdBbdVr+z8ror4GVteyce3D3=vwDWxhu5KqQ@mail.gmail.com>
2016-04-30 20:52 ` [patch 2/7] lib/hashmod: Add modulo based hash mechanism George Spelvin
2016-05-01 8:35 ` Thomas Gleixner
2016-05-01 9:43 ` George Spelvin [this message]
2016-05-01 16:51 ` Linus Torvalds
2016-05-14 3:54 ` George Spelvin
2016-05-14 18:35 ` Linus Torvalds
2016-05-02 7:11 ` Thomas Gleixner
2016-05-02 10:20 ` [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits George Spelvin
2016-05-02 10:22 ` [PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem George Spelvin
2016-05-02 20:08 ` Linus Torvalds
2016-05-02 10:27 ` [RFC PATCH 3/2] (Rant) Fix various hash abuses George Spelvin
2016-05-02 10:31 ` [RFC PATCH 4/2] namei: Improve hash mixing if CONFIG_DCACHE_WORD_ACCESS George Spelvin
2016-05-16 18:51 ` Linus Torvalds
2016-05-02 13:28 ` [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Peter Zijlstra
2016-05-02 19:08 ` George Spelvin
2016-05-02 16:24 ` Linus Torvalds
2016-05-02 20:26 ` George Spelvin
2016-05-02 21:19 ` Linus Torvalds
2016-05-02 21:41 ` Linus Torvalds
2016-05-03 1:59 ` George Spelvin
2016-05-03 3:01 ` Linus Torvalds
2016-04-29 2:57 [patch 2/7] lib/hashmod: Add modulo based hash mechanism George Spelvin
2016-04-29 3:16 ` Linus Torvalds
2016-04-29 4:12 ` George Spelvin
2016-04-29 23:31 ` George Spelvin
2016-04-30 0:05 ` Linus Torvalds
2016-04-30 0:32 ` George Spelvin
2016-04-30 1:12 ` Linus Torvalds
2016-04-30 3:04 ` George Spelvin
-- strict thread matches above, loose matches on Subject: below --
2016-04-28 16:42 [patch 0/7] futex: Add support for process private hashing Thomas Gleixner
2016-04-28 16:42 ` [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner
2016-04-28 18:32 ` Linus Torvalds
2016-04-28 23:26 ` Thomas Gleixner
2016-04-29 2:25 ` Linus Torvalds
2016-04-30 13:02 ` Thomas Gleixner
2016-04-30 16:45 ` Eric Dumazet
2016-04-30 17:12 ` Linus Torvalds
2016-04-30 17:37 ` Eric Dumazet
2016-06-12 12:18 ` Sandy Harris
2016-04-29 21:10 ` Linus Torvalds
2016-04-29 23:51 ` Linus Torvalds
2016-04-30 1:34 ` Rik van Riel
2016-05-02 9:39 ` Torvald Riegel
2016-04-30 15:22 ` Thomas Gleixner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160501094358.4706.qmail@ns.horizon.com \
--to=linux@horizon.com \
--cc=eric.dumazet@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=riel@redhat.com \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).