Should be more efficient as we can use a bitmask
operation instead of an expensive modulo.
Results from oprofile on a shader-db run:
set_add 2.70 ---> 1.69
set_search 2.74 ---> 2.11
runtime 165 ---> 157
---
src/util/set.c | 82 +++++++++++++++++++++++++++++++---------------------------
1 file changed, 44 insertions(+), 38 deletions(-)
diff --git a/src/util/set.c b/src/util/set.c
index f350c1e..f231dd1 100644
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -48,40 +48,46 @@
uint32_t deleted_key_value;
const void *deleted_key = &deleted_key_value;
+/**
+ * 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
@@ -166,7 +172,7 @@ set_search(const struct set *ht, uint32_t hash, const void
*key)
uint32_t quad_hash;
quad_hash = 1;
- hash_address = hash % ht->size;
+ hash_address = hash & (ht->size -1);
do {
struct set_entry *entry = ht->table + hash_address;
@@ -178,8 +184,8 @@ set_search(const struct set *ht, uint32_t hash, const void
*key)
}
}
- hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
- } while (hash_address != hash % ht->size);
+ hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
+ } while (hash_address != (hash & (ht->size -1)));
return NULL;
}
@@ -257,7 +263,7 @@ set_add(struct set *ht, uint32_t hash, const void *key)
}
quad_hash = 1;
- hash_address = hash % ht->size;
+ hash_address = hash & (ht->size -1);
do {
struct set_entry *entry = ht->table + hash_address;
@@ -285,8 +291,8 @@ set_add(struct set *ht, uint32_t hash, const void *key)
return entry;
}
- hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
- } while (hash_address != hash % ht->size);
+ hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
+ } while (hash_address != (hash & (ht->size -1)));
if (available_entry) {
if (entry_is_deleted(available_entry))
@@ -363,7 +369,7 @@ _mesa_set_random_entry(struct set *ht,
int (*predicate)(struct set_entry *entry))
{
struct set_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
