[Mesa-dev] [PATCH 1/8] util: Change hash_table to use quadratic probing.
Thomas Helland
thomashelland90 at gmail.com
Sat Feb 28 04:53:47 PST 2015
This should give better cache locality, less memory consumption,
less code, and should also be faster since we avoid a modulo operation.
This is not the quadratic probing function you see most places.
They do not accumulate, so you try hash +1, +4, +9, etc.
My code accumulates; so it becomes hash +1, +5, +14, etc.
It felt more natural to do it like this.
However, it causes an assertion failure.
The search function is apparently returning null when it shouldn't.
This does not get caught by make-check.
This gets fixed by the next patch.
---
src/util/hash_table.c | 91 ++++++++++++++++++++++++---------------------------
src/util/hash_table.h | 1 -
2 files changed, 43 insertions(+), 49 deletions(-)
diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 3247593..542f583 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -33,7 +33,7 @@
*/
/**
- * Implements an open-addressing, linear-reprobing hash table.
+ * Implements an open-addressing, quadratic probing hash table.
*
* For more information, see:
*
@@ -51,44 +51,44 @@
static const uint32_t deleted_key_value;
/**
- * From Knuth -- a good choice for hash/rehash values is p, p-2 where
- * p and p-2 are both prime. These tables are sized to have an extra 10%
- * free to avoid exponential performance degradation as the hash table fills
+ * From Knuth -- a good choice for hash values is p, where is prime.
+ * 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, rehash;
+ uint32_t max_entries, size;
} hash_sizes[] = {
- { 2, 5, 3 },
- { 4, 7, 5 },
- { 8, 13, 11 },
- { 16, 19, 17 },
- { 32, 43, 41 },
- { 64, 73, 71 },
- { 128, 151, 149 },
- { 256, 283, 281 },
- { 512, 571, 569 },
- { 1024, 1153, 1151 },
- { 2048, 2269, 2267 },
- { 4096, 4519, 4517 },
- { 8192, 9013, 9011 },
- { 16384, 18043, 18041 },
- { 32768, 36109, 36107 },
- { 65536, 72091, 72089 },
- { 131072, 144409, 144407 },
- { 262144, 288361, 288359 },
- { 524288, 576883, 576881 },
- { 1048576, 1153459, 1153457 },
- { 2097152, 2307163, 2307161 },
- { 4194304, 4613893, 4613891 },
- { 8388608, 9227641, 9227639 },
- { 16777216, 18455029, 18455027 },
- { 33554432, 36911011, 36911009 },
- { 67108864, 73819861, 73819859 },
- { 134217728, 147639589, 147639587 },
- { 268435456, 295279081, 295279079 },
- { 536870912, 590559793, 590559791 },
- { 1073741824, 1181116273, 1181116271},
- { 2147483648ul, 2362232233ul, 2362232231ul}
+ { 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}
};
static int
@@ -123,7 +123,6 @@ _mesa_hash_table_create(void *mem_ctx,
ht->size_index = 0;
ht->size = hash_sizes[ht->size_index].size;
- ht->rehash = hash_sizes[ht->size_index].rehash;
ht->max_entries = hash_sizes[ht->size_index].max_entries;
ht->key_hash_function = key_hash_function;
ht->key_equals_function = key_equals_function;
@@ -184,10 +183,9 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
{
uint32_t start_hash_address = hash % ht->size;
uint32_t hash_address = start_hash_address;
+ uint32_t quad_hash = 1;
do {
- uint32_t double_hash;
-
struct hash_entry *entry = ht->table + hash_address;
if (entry_is_free(entry)) {
@@ -198,9 +196,8 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key)
}
}
- double_hash = 1 + hash % ht->rehash;
-
- hash_address = (hash_address + double_hash) % ht->size;
+ hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
+ quad_hash++;
} while (hash_address != start_hash_address);
return NULL;
@@ -250,7 +247,6 @@ _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
ht->table = table;
ht->size_index = new_size_index;
ht->size = hash_sizes[ht->size_index].size;
- ht->rehash = hash_sizes[ht->size_index].rehash;
ht->max_entries = hash_sizes[ht->size_index].max_entries;
ht->entries = 0;
ht->deleted_entries = 0;
@@ -267,6 +263,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
const void *key, void *data)
{
uint32_t start_hash_address, hash_address;
+ uint32_t quad_hash = 1;
struct hash_entry *available_entry = NULL;
if (ht->entries >= ht->max_entries) {
@@ -277,9 +274,9 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
start_hash_address = hash % ht->size;
hash_address = start_hash_address;
+
do {
struct hash_entry *entry = ht->table + hash_address;
- uint32_t double_hash;
if (!entry_is_present(ht, entry)) {
/* Stash the first available entry we find */
@@ -307,10 +304,8 @@ hash_table_insert(struct hash_table *ht, uint32_t hash,
return entry;
}
-
- double_hash = 1 + hash % ht->rehash;
-
- hash_address = (hash_address + double_hash) % ht->size;
+ hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
+ quad_hash++;
} while (hash_address != start_hash_address);
if (available_entry) {
diff --git a/src/util/hash_table.h b/src/util/hash_table.h
index eb9dbc3..6d41338 100644
--- a/src/util/hash_table.h
+++ b/src/util/hash_table.h
@@ -50,7 +50,6 @@ struct hash_table {
bool (*key_equals_function)(const void *a, const void *b);
const void *deleted_key;
uint32_t size;
- uint32_t rehash;
uint32_t max_entries;
uint32_t size_index;
uint32_t entries;
--
2.2.1
More information about the mesa-dev
mailing list