This gives better performance as we can do bitmasking
instead of modulo operations.
This reduces oprofile hits on a shader-db run accordingly:
hash_table_insert 4.28 ---> 2.57
hash_table_search 4.59 ---> 2.67
runtime 175 ---> 170
Since the last patch hits assertion failures this is
the result for these two patches combined.
---
src/util/hash_table.c | 75 ++++++++++++++++++++++++++-------------------------
1 file changed, 38 insertions(+), 37 deletions(-)
diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 542f583..49a1fea 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -51,44 +51,45 @@
static const uint32_t deleted_key_value;
/**
- * From Knuth -- a good choice for hash values is p, where is prime.
+ * We chose table sizes that's a power of two.
+ * This is computationally less expensive than primes.
+ * FNV-1a has good avalanche properties, so collision is not an issue.
* 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;
} hash_sizes[] = {
- { 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}
+ { 3, 4 },
+ { 7, 8 },
+ { 14, 16 },
+ { 28, 32 },
+ { 57, 64 },
+ { 115, 128 },
+ { 230, 256 },
+ { 460, 512 },
+ { 921, 1024 },
+ { 1843, 2048 },
+ { 3686, 4096 },
+ { 7372, 8192 },
+ { 14745, 16384 },
+ { 29491, 32768 },
+ { 58982, 65536 },
+ { 117964, 131072 },
+ { 235929, 262144 },
+ { 471859, 524288 },
+ { 943718, 1048576 },
+ { 1887436, 2097152 },
+ { 3774873, 4194304 },
+ { 7549747, 8388608 },
+ { 15099494, 16777216 },
+ { 30198988, 33554432 },
+ { 60397977, 67108864 },
+ { 120795955, 134217728 },
+ { 241591910, 268435456 },
+ { 483183820, 536870912 },
+ { 966367641, 1073741824 },
+ { 1932735283ul, 2147483648ul }
};
static int
@@ -181,7 +182,7 @@ _mesa_hash_table_set_deleted_key(struct hash_table *ht,
const void *deleted_key)
static struct hash_entry *
hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
{
- uint32_t start_hash_address = hash % ht->size;
+ uint32_t start_hash_address = hash & (ht->size -1);
uint32_t hash_address = start_hash_address;
uint32_t quad_hash = 1;
@@ -196,7 +197,7 @@ hash_table_search(struct hash_table *ht, uint32_t hash,
const void *key)
}
}
- hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
+ hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
quad_hash++;
} while (hash_address != start_hash_address);
@@ -272,7 +273,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
_mesa_hash_table_rehash(ht, ht->size_index);
}
- start_hash_address = hash % ht->size;
+ start_hash_address = hash & (ht->size -1);
hash_address = start_hash_address;
do {
@@ -304,7 +305,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
return entry;
}
- hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
+ hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
quad_hash++;
} while (hash_address != start_hash_address);
@@ -400,7 +401,7 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
bool (*predicate)(struct hash_entry *entry))
{
struct hash_entry *entry;
- uint32_t i = rand() % ht->size;
+ uint32_t i = rand() & (ht->size -1);
if (ht->entries == 0)
return NULL;
--
2.2.1
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
