Mesa (master): util/set: 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: 5f3f128088ae45734723071ec4af340488ece741
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=5f3f128088ae45734723071ec4af340488ece741
Author: Mike Blumenkrantz <michael.blumenkrantz at gmail.com>
Date: Tue Jan 12 12:20:41 2021 -0500
util/set: 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/set.c | 32 ++++++++++++++++++++++++--------
src/util/tests/set/set_test.cpp | 7 +++++++
2 files changed, 31 insertions(+), 8 deletions(-)
diff --git a/src/util/set.c b/src/util/set.c
index f10694537c1..f071aca24fe 100644
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -211,6 +211,14 @@ _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entr
ralloc_free(ht);
}
+
+static void
+set_clear_fast(struct set *ht)
+{
+ memset(ht->table, 0, sizeof(struct set_entry) * hash_sizes[ht->size_index].size);
+ ht->entries = ht->deleted_entries = 0;
+}
+
/**
* Clears all values from the given set.
*
@@ -225,15 +233,17 @@ _mesa_set_clear(struct set *set, void (*delete_function)(struct set_entry *entry
struct set_entry *entry;
- for (entry = set->table; entry != set->table + set->size; entry++) {
- if (entry_is_present(entry) && delete_function != NULL)
- delete_function(entry);
-
- entry->key = NULL;
- }
+ if (delete_function) {
+ for (entry = set->table; entry != set->table + set->size; entry++) {
+ if (entry_is_present(entry))
+ delete_function(entry);
- set->entries = 0;
- set->deleted_entries = 0;
+ entry->key = NULL;
+ }
+ set->entries = 0;
+ set->deleted_entries = 0;
+ } else
+ set_clear_fast(set);
}
/**
@@ -314,6 +324,12 @@ set_rehash(struct set *ht, unsigned new_size_index)
struct set old_ht;
struct set_entry *table;
+ if (ht->size_index == new_size_index && ht->deleted_entries == ht->max_entries) {
+ set_clear_fast(ht);
+ assert(!ht->entries);
+ return;
+ }
+
if (new_size_index >= ARRAY_SIZE(hash_sizes))
return;
diff --git a/src/util/tests/set/set_test.cpp b/src/util/tests/set/set_test.cpp
index 0b4355af128..6eda08de698 100644
--- a/src/util/tests/set/set_test.cpp
+++ b/src/util/tests/set/set_test.cpp
@@ -51,6 +51,13 @@ TEST(set, basic)
entry = _mesa_set_search(s, a);
EXPECT_FALSE(entry);
+ _mesa_set_clear(s, NULL);
+ EXPECT_EQ(s->entries, 0);
+ EXPECT_EQ(s->deleted_entries, 0);
+ set_foreach(s, he) {
+ GTEST_FAIL();
+ }
+
_mesa_set_destroy(s, NULL);
}
More information about the mesa-commit
mailing list