Re: [Mesa-dev] [PATCH 1/8] util: Change hash_table to use quadratic probing.

[Erik Faye-Lund]

On Sat, Feb 28, 2015 at 1:53 PM, Thomas Helland
thomashellan...@gmail.com wrote:
 This should give better cache locality, less memory consumption,
 less code, and should also be faster since we avoid a modulo operation.

 This is not the quadratic probing function you see most places.
 They do not accumulate, so you try hash +1, +4, +9, etc.
 My code accumulates; so it becomes hash +1, +5, +14, etc.
 It felt more natural to do it like this.

 However, it causes an assertion failure.
 The search function is apparently returning null when it shouldn't.
 This does not get caught by make-check.
 This gets fixed by the next patch.
 ---
  src/util/hash_table.c | 91 
 ---
  src/util/hash_table.h |  1 -
  2 files changed, 43 insertions(+), 49 deletions(-)

 diff --git a/src/util/hash_table.c b/src/util/hash_table.c
 index 3247593..542f583 100644
 --- a/src/util/hash_table.c
 +++ b/src/util/hash_table.c
 @@ -33,7 +33,7 @@
   */

  /**
 - * Implements an open-addressing, linear-reprobing hash table.
 + * Implements an open-addressing, quadratic probing hash table.
   *
   * For more information, see:
   *
 @@ -51,44 +51,44 @@
  static const uint32_t deleted_key_value;

  /**
 - * From Knuth -- a good choice for hash/rehash values is p, p-2 where
 - * p and p-2 are both prime.  These tables are sized to have an extra 10%
 - * free to avoid exponential performance degradation as the hash table fills
 + * From Knuth -- a good choice for hash values is p, where is prime.
 + * These tables are sized to have an extra 10% free to avoid
 + * exponential performance degradation as the hash table fills

[...] where is prime? Where what is prime?
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev

[Mesa-dev] [PATCH 1/8] util: Change hash_table to use quadratic probing.

[Thomas Helland]

This should give better cache locality, less memory consumption,
less code, and should also be faster since we avoid a modulo operation.

This is not the quadratic probing function you see most places.
They do not accumulate, so you try hash +1, +4, +9, etc.
My code accumulates; so it becomes hash +1, +5, +14, etc.
It felt more natural to do it like this.

However, it causes an assertion failure.
The search function is apparently returning null when it shouldn't.
This does not get caught by make-check.
This gets fixed by the next patch.
---
 src/util/hash_table.c | 91 ---
 src/util/hash_table.h |  1 -
 2 files changed, 43 insertions(+), 49 deletions(-)

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 3247593..542f583 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -33,7 +33,7 @@
  */
 
 /**
- * Implements an open-addressing, linear-reprobing hash table.
+ * Implements an open-addressing, quadratic probing hash table.
  *
  * For more information, see:
  *
@@ -51,44 +51,44 @@
 static const uint32_t deleted_key_value;
 
 /**
- * From Knuth -- a good choice for hash/rehash values is p, p-2 where
- * p and p-2 are both prime.  These tables are sized to have an extra 10%
- * free to avoid exponential performance degradation as the hash table fills
+ * From Knuth -- a good choice for hash values is p, where is prime.
+ * These tables are sized to have an extra 10% free to avoid
+ * exponential performance degradation as the hash table fills
  */
 static const struct {
-   uint32_t max_entries, size, rehash;
+   uint32_t max_entries, size;
 } hash_sizes[] = {
-   { 2,5,  3 },
-   { 4,7,  5 },
-   { 8,13, 11},
-   { 16,   19, 17},
-   { 32,   43, 41},
-   { 64,   73, 71},
-   { 128,  151,149   },
-   { 256,  283,281   },
-   { 512,  571,569   },
-   { 1024, 1153,   1151  },
-   { 2048, 2269,   2267  },
-   { 4096, 4519,   4517  },
-   { 8192, 9013,   9011  },
-   { 16384,18043,  18041 },
-   { 32768,36109,  36107 },
-   { 65536,72091,  72089 },
-   { 131072,   144409, 144407},
-   { 262144,   288361, 288359},
-   { 524288,   576883, 576881},
-   { 1048576,  1153459,1153457   },
-   { 2097152,  2307163,2307161   },
-   { 4194304,  4613893,4613891   },
-   { 8388608,  9227641,9227639   },
-   { 16777216, 18455029,   18455027  },
-   { 33554432, 36911011,   36911009  },
-   { 67108864, 73819861,   73819859  },
-   { 134217728,147639589,  147639587 },
-   { 268435456,295279081,  295279079 },
-   { 536870912,590559793,  590559791 },
-   { 1073741824,   1181116273, 1181116271},
-   { 2147483648ul, 2362232233ul,   2362232231ul}
+   { 2,5   },
+   { 4,7   },
+   { 8,13  },
+   { 16,   19  },
+   { 32,   43  },
+   { 64,   73  },
+   { 128,  151 },
+   { 256,  283 },
+   { 512,  571 },
+   { 1024, 1153},
+   { 2048, 2269},
+   { 4096, 4519},
+   { 8192, 9013},
+   { 16384,18043   },
+   { 32768,36109   },
+   { 65536,72091   },
+   { 131072,   144409  },
+   { 262144,   288361  },
+   { 524288,   576883  },
+   { 1048576,  1153459 },
+   { 2097152,  2307163 },
+   { 4194304,  4613893 },
+   { 8388608,  9227641 },
+   { 16777216, 18455029},
+   { 33554432, 36911011},
+   { 67108864, 73819861},
+   { 134217728,147639589   },
+   { 268435456,295279081   },
+   { 536870912,590559793   },
+   { 1073741824,   1181116273  },
+   { 2147483648ul, 2362232233ul}
 };
 
 static int
@@ -123,7 +123,6 @@ _mesa_hash_table_create(void *mem_ctx,
 
ht-size_index = 0;
ht-size = hash_sizes[ht-size_index].size;
-   ht-rehash = hash_sizes[ht-size_index].rehash;
ht-max_entries = hash_sizes[ht-size_index].max_entries;
ht-key_hash_function =