From f7ff6856492e8437ad78bb6a853a681afd3fc98c Mon Sep 17 00:00:00 2001 From: Connor Abbott Date: Mon, 20 May 2019 14:58:06 +0200 Subject: [PATCH] util/set: Pull out loop-invariant computations Unfortunately GCC can't do this for us, probably because we call the key comparison function which GCC can't prove won't modify arbitrary memory. This is a pretty hot function, so do the optimization manually to be sure the compiler will get it right. While we're here, make the computation of the new probe address use a single conditional subtract instead of a modulo, since we know that it won't ever get as big as 2 * ht->size before the modulo. Modulos tend to be pretty expensive operations. shader-db compile time results for my database: Difference at 95.0% confidence -2.24934 +/- 0.69897 -0.516296% +/- 0.159993% (Student's t, pooled s = 0.983684) Reviewed-by: Eric Anholt Acked-by: Jason Ekstrand --- src/util/set.c | 32 ++++++++++++++++---------------- 1 file changed, 16 insertions(+), 16 deletions(-) diff --git a/src/util/set.c b/src/util/set.c index 599a44a707a..a1cf05cb4dc 100644 --- a/src/util/set.c +++ b/src/util/set.c @@ -206,12 +206,11 @@ _mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry static struct set_entry * set_search(const struct set *ht, uint32_t hash, const void *key) { - uint32_t hash_address; - - hash_address = hash % ht->size; + uint32_t size = ht->size; + uint32_t start_address = hash % size; + uint32_t double_hash = hash % ht->rehash + 1; + uint32_t hash_address = start_address; do { - uint32_t double_hash; - struct set_entry *entry = ht->table + hash_address; if (entry_is_free(entry)) { @@ -222,10 +221,10 @@ set_search(const struct set *ht, uint32_t hash, const void *key) } } - double_hash = 1 + hash % ht->rehash; - - hash_address = (hash_address + double_hash) % ht->size; - } while (hash_address != hash % ht->size); + hash_address += double_hash; + if (hash_address >= size) + hash_address -= size; + } while (hash_address != start_address); return NULL; } @@ -304,7 +303,6 @@ _mesa_set_resize(struct set *set, uint32_t entries) static struct set_entry * set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found) { - uint32_t hash_address; struct set_entry *available_entry = NULL; if (ht->entries >= ht->max_entries) { @@ -313,10 +311,12 @@ set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found) set_rehash(ht, ht->size_index); } - hash_address = hash % ht->size; + uint32_t size = ht->size; + uint32_t start_address = hash % size; + uint32_t double_hash = hash % ht->rehash + 1; + uint32_t hash_address = start_address; do { struct set_entry *entry = ht->table + hash_address; - uint32_t double_hash; if (!entry_is_present(entry)) { /* Stash the first available entry we find */ @@ -334,10 +334,10 @@ set_search_or_add(struct set *ht, uint32_t hash, const void *key, bool *found) return entry; } - double_hash = 1 + hash % ht->rehash; - - hash_address = (hash_address + double_hash) % ht->size; - } while (hash_address != hash % ht->size); + hash_address = hash_address + double_hash; + if (hash_address >= size) + hash_address -= size; + } while (hash_address != start_address); if (available_entry) { /* There is no matching entry, create it. */ -- 2.30.2