Make hash_64() use a 64-bit multiply when appropriate
authorLinus Torvalds <torvalds@linux-foundation.org>
Sat, 13 Sep 2014 18:24:03 +0000 (11:24 -0700)
committerLinus Torvalds <torvalds@linux-foundation.org>
Sat, 13 Sep 2014 18:24:03 +0000 (11:24 -0700)
The hash_64() function historically does the multiply by the
GOLDEN_RATIO_PRIME_64 number with explicit shifts and adds, because
unlike the 32-bit case, gcc seems unable to turn the constant multiply
into the more appropriate shift and adds when required.

However, that means that we generate those shifts and adds even when the
architecture has a fast multiplier, and could just do it better in
hardware.

Use the now-cleaned-up CONFIG_ARCH_HAS_FAST_MULTIPLIER (together with
"is it a 64-bit architecture") to decide whether to use an integer
multiply or the explicit sequence of shift/add instructions.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
include/linux/hash.h

index bd1754c..d0494c3 100644 (file)
@@ -37,6 +37,9 @@ static __always_inline u64 hash_64(u64 val, unsigned int bits)
 {
        u64 hash = val;
 
 {
        u64 hash = val;
 
+#if defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64
+       hash = hash * GOLDEN_RATIO_PRIME_64;
+#else
        /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
        u64 n = hash;
        n <<= 18;
        /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
        u64 n = hash;
        n <<= 18;
@@ -51,6 +54,7 @@ static __always_inline u64 hash_64(u64 val, unsigned int bits)
        hash += n;
        n <<= 2;
        hash += n;
        hash += n;
        n <<= 2;
        hash += n;
+#endif
 
        /* High bits are more random, so use them. */
        return hash >> (64 - bits);
 
        /* High bits are more random, so use them. */
        return hash >> (64 - bits);