[Mesa-dev] [PATCH v2 3/3] util: Use 32 bit integer hash function for

[Thomas Helland]

Since a pointer is basically just an int we can use integer hashing.
This implementation is found on Bob Jenkins' webpage on:
http://burtleburtle.net/bob/hash/integer.html
It states that this implementation is faster than any of his algorithms.
It also statest that the algorithm is public domain.
Since it operates 32 bits at a time it is really effective.

Oprofile of shader-db run with INTEL_USE_NIR set:
mesa_hash_data 3.09 % ---> 2.15 %

V2: Feedback from Matt Turner
   - Use a for-loop for readability
   - Don't mix code and declaration

    Feedback from Jordan Justen
   - Add comment regarding licensing

Signed-off-by: Thomas Helland <thomashelland90 at gmail.com>
---
 src/util/hash_table.c | 38 ++++++++++++++++++++++++++++----------
 1 file changed, 28 insertions(+), 10 deletions(-)

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 24184c0..7c6b3ae 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -393,21 +393,39 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
    return NULL;
 }
 
-
 /**
- * Quick FNV-1a hash implementation based on:
- * http://www.isthe.com/chongo/tech/comp/fnv/
- *
- * FNV-1a is not be the best hash out there -- Jenkins's lookup3 is supposed
- * to be quite good, and it probably beats FNV.  But FNV has the advantage
- * that it involves almost no code.  For an improvement on both, see Paul
- * Hsieh's http://www.azillionmonkeys.com/qed/hash.html
+ * This hashing function is described on Bob Jenkins' website:
+ * http://burtleburtle.net/bob/hash/integer.html
+ * It states that the code originally is Thomas Wang's,
+ * and that it is public domain.
+ * The original page is down, but a copy can be found on
+ * http://web.archive.org/web/20120720045250/http://www.cris.com/~Ttwang/tech/inthash.htm
  */
+static inline uint32_t
+hash_32bit_int(uint32_t a) {
+   a = (a ^ 61) ^ (a >> 16);
+   a = a + (a << 3);
+   a = a ^ (a >> 4);
+   a = a * 0x27d4eb2d;
+   a = a ^ (a >> 15);
+   return a;
+}
+
 uint32_t
 _mesa_hash_data(const void *data, size_t size)
 {
-   return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
-                                          data, size);
+   uint32_t hash = _mesa_fnv32_1a_offset_bias;
+   const uint32_t *ints = (const uint32_t *) data;
+   uint32_t i = 0;
+
+   assert((size % 4) == 0);
+
+   uint32_t i = size / 4;
+
+   for (i = size / 4; i != 0; i--, ints++)
+      hash ^= hash_32bit_int(*ints);
+
+   return hash;
 }
 
 /** FNV-1a string hash implementation */
-- 
2.3.4