Copy-pasta from the wikipedia article.
Results from oprofile on a shader-db run:
mesa_hash_data 3.25 ---> 3.11
hash_table_insert 2.52 ---> 2.52
hash_table_search 2.64 ---> 2.64
set_add 1.65 ---> 1.74
set_search 2.07 ---> 2.08
runtime 160 ---> 160
---
src/util/hash_table.c | 5 ++---
src/util/hash_table.h | 54 +++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 56 insertions(+), 3 deletions(-)
diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 8216869..f2b8cf6 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -436,8 +436,7 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
uint32_t
_mesa_hash_data(const void *data, size_t size)
{
- return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
- data, size);
+ return murmur3_32(data, size, _mesa_fnv32_1a_offset_bias);
}
/** FNV-1a string hash implementation */
@@ -447,7 +446,7 @@ _mesa_hash_string(const char *key)
uint32_t hash = _mesa_fnv32_1a_offset_bias;
while (*key != 0) {
- hash = _mesa_fnv32_1a_accumulate(hash, *key);
+ hash = _mesa_murmur3_32(hash, *key);
key++;
}
diff --git a/src/util/hash_table.h b/src/util/hash_table.h
index 6d41338..288e205 100644
--- a/src/util/hash_table.h
+++ b/src/util/hash_table.h
@@ -119,6 +119,60 @@ _mesa_fnv32_1a_accumulate_block(uint32_t hash, const void
*data, size_t size)
#define _mesa_fnv32_1a_accumulate(hash, expr) \
_mesa_fnv32_1a_accumulate_block(hash, &(expr), sizeof(expr))
+#define _mesa_murmur3_32(hash, expr) \
+ murmur3_32(&(expr), sizeof(expr), hash)
+
+static inline
+uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed) {
+ static const uint32_t c1 = 0xcc9e2d51;
+ static const uint32_t c2 = 0x1b873593;
+ static const uint32_t r1 = 15;
+ static const uint32_t r2 = 13;
+ static const uint32_t m = 5;
+ static const uint32_t n = 0xe6546b64;
+
+ uint32_t hash = seed;
+
+ const int nblocks = len / 4;
+ const uint32_t *blocks = (const uint32_t *) key;
+ int i;
+ for (i = 0; i < nblocks; i++) {
+ uint32_t k = blocks[i];
+ k *= c1;
+ k = (k << r1) | (k >> (32 - r1));
+ k *= c2;
+
+ hash ^= k;
+ hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
+ }
+
+ const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);
+ uint32_t k1 = 0;
+
+ switch (len & 3) {
+ case 3:
+ k1 ^= tail[2] << 16;
+ case 2:
+ k1 ^= tail[1] << 8;
+ case 1:
+ k1 ^= tail[0];
+
+ k1 *= c1;
+ k1 = (k1 << r1) | (k1 >> (32 - r1));
+ k1 *= c2;
+ hash ^= k1;
+ }
+
+ hash ^= len;
+ hash ^= (hash >> 16);
+ hash *= 0x85ebca6b;
+ hash ^= (hash >> 13);
+ hash *= 0xc2b2ae35;
+ hash ^= (hash >> 16);
+
+ return hash;
+}
+
/**
* This foreach function is safe against deletion (which just replaces
* an entry's data with the deleted marker), but not against insertion
--
2.2.1
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
