Patchwork [1/9] Improve pointer hash function to include all bits

login
register
mail settings
Submitter Andi Kleen
Date April 19, 2013, 9:31 p.m.
Message ID <1366407117-18462-2-git-send-email-andi@firstfloor.org>
Download mbox | patch
Permalink /patch/238115/
State New
Headers show

Comments

Andi Kleen - April 19, 2013, 9:31 p.m.
From: Andi Kleen <ak@linux.intel.com>

The hashtab pointer hash function is not very good. It throws most of the
bits in the pointer away.

This changes pointer_hash to use the mix code from jhash function that mixes
all the bits on the pointer and makes them dependent on each other, before doing
the modulo.

libiberty/:

2013-04-18  Andi Kleen <ak@linux.intel.com>

	* hashtab.c (hash_pointer): Move to end of file and reimplement.
---
 libiberty/hashtab.c | 32 ++++++++++++++++++++++++--------
 1 file changed, 24 insertions(+), 8 deletions(-)
Ian Taylor - April 20, 2013, 6:25 a.m.
On Fri, Apr 19, 2013 at 2:31 PM, Andi Kleen <andi@firstfloor.org> wrote:
> From: Andi Kleen <ak@linux.intel.com>
>
> 2013-04-18  Andi Kleen <ak@linux.intel.com>
>
>         * hashtab.c (hash_pointer): Move to end of file and reimplement.



> +/* Returns a hash code for pointer P. Simplified version of evahash */
> +
> +static hashval_t
> +hash_pointer (const PTR p)
> +{
> +  intptr_t v = (intptr_t)p;

Space after ')'.

> +  unsigned a, b, c;
> +  a = b = 0x9e3779b9;

Blank line after variable declarations.

> +  if (sizeof(intptr_t) == 4)

Space before '('.

> +    {
> +      /* Mix as 16bit for now */
> +      a += v >> 16;
> +      b += v & 0xffff;
> +    }
> +  else
> +    {
> +      a += v >> 32;
> +      b += v & 0xffffffff;
> +    }
> +  c = 0x42135234;
> +  mix(a, b, c);

Space before '('.

This is OK with those changes if it bootstraps and passes tests.

Thanks.

Ian

Patch

diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index dfaec0f..f714a85 100644
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -194,14 +194,6 @@  higher_prime_index (unsigned long n)
   return low;
 }
 
-/* Returns a hash code for P.  */
-
-static hashval_t
-hash_pointer (const PTR p)
-{
-  return (hashval_t) ((intptr_t)p >> 3);
-}
-
 /* Returns non-zero if P1 and P2 are equal.  */
 
 static int
@@ -988,3 +980,27 @@  iterative_hash (const PTR k_in /* the key */,
   /*-------------------------------------------- report the result */
   return c;
 }
+
+/* Returns a hash code for pointer P. Simplified version of evahash */
+
+static hashval_t
+hash_pointer (const PTR p)
+{
+  intptr_t v = (intptr_t)p;
+  unsigned a, b, c;
+  a = b = 0x9e3779b9;
+  if (sizeof(intptr_t) == 4) 
+    {
+      /* Mix as 16bit for now */
+      a += v >> 16;
+      b += v & 0xffff;
+    }
+  else
+    {
+      a += v >> 32;
+      b += v & 0xffffffff;
+    }
+  c = 0x42135234;
+  mix(a, b, c);
+  return c;
+}