Mesa (master): util/hash_table: optimize rehash for empty table and no-func clears
GitLab Mirror
gitlab-mirror at kemper.freedesktop.org
Thu Jan 14 14:41:22 UTC 2021
Module: Mesa
Branch: master
Commit: 41042f7fa29787347a4844a06a60b0c83fc916c1
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=41042f7fa29787347a4844a06a60b0c83fc916c1
Author: Mike Blumenkrantz <michael.blumenkrantz at gmail.com>
Date: Tue Jan 12 12:20:41 2021 -0500
util/hash_table: optimize rehash for empty table and no-func clears
if the table is filled with deleted entries, we don't need to rzalloc+free an identical
block of memory for the table, we can just memset the existing one
the same applies to table clears without a function passed in that the table
doesn't need to be iterated and can just be memset
Reviewed-by: Eric Anholt <eric at anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/8450>
---
src/util/hash_table.c | 31 +++++++++++++++++++++++--------
src/util/tests/hash_table/clear.c | 6 ++++++
2 files changed, 29 insertions(+), 8 deletions(-)
diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 9ca0d5e2d64..92897c1bc83 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -234,6 +234,13 @@ _mesa_hash_table_destroy(struct hash_table *ht,
ralloc_free(ht);
}
+static void
+hash_table_clear_fast(struct hash_table *ht)
+{
+ memset(ht->table, 0, sizeof(struct hash_entry) * hash_sizes[ht->size_index].size);
+ ht->entries = ht->deleted_entries = 0;
+}
+
/**
* Deletes all entries of the given hash table without deleting the table
* itself or changing its structure.
@@ -249,15 +256,17 @@ _mesa_hash_table_clear(struct hash_table *ht,
struct hash_entry *entry;
- for (entry = ht->table; entry != ht->table + ht->size; entry++) {
- if (entry_is_present(ht, entry) && delete_function != NULL)
- delete_function(entry);
-
- entry->key = NULL;
- }
+ if (delete_function) {
+ for (entry = ht->table; entry != ht->table + ht->size; entry++) {
+ if (entry_is_present(ht, entry))
+ delete_function(entry);
- ht->entries = 0;
- ht->deleted_entries = 0;
+ entry->key = NULL;
+ }
+ ht->entries = 0;
+ ht->deleted_entries = 0;
+ } else
+ hash_table_clear_fast(ht);
}
/** Sets the value of the key pointer used for deleted entries in the table.
@@ -362,6 +371,12 @@ _mesa_hash_table_rehash(struct hash_table *ht, unsigned new_size_index)
struct hash_table old_ht;
struct hash_entry *table;
+ if (ht->size_index == new_size_index && ht->deleted_entries == ht->max_entries) {
+ hash_table_clear_fast(ht);
+ assert(!ht->entries);
+ return;
+ }
+
if (new_size_index >= ARRAY_SIZE(hash_sizes))
return;
diff --git a/src/util/tests/hash_table/clear.c b/src/util/tests/hash_table/clear.c
index e61f60ece1b..90ca30e3a1c 100644
--- a/src/util/tests/hash_table/clear.c
+++ b/src/util/tests/hash_table/clear.c
@@ -86,6 +86,12 @@ int main()
hash_table_foreach(ht, entry) {
assert(key_id(entry->key) < SIZE);
}
+ _mesa_hash_table_clear(ht, NULL);
+ assert(!ht->entries);
+ assert(!ht->deleted_entries);
+ hash_table_foreach(ht, entry) {
+ assert(0);
+ }
_mesa_hash_table_destroy(ht, NULL);
More information about the mesa-commit
mailing list