[Mesa-dev] [PATCH 3/4] prog_hash_table: Convert to using util/hash_table.h.
Eric Anholt
eric at anholt.net
Tue Aug 9 17:17:45 UTC 2016
Improves glretrace -b servo.trace (a trace of Mozilla's servo rendering
engine booting, rendering a page, and exiting) from 1.8s to 1.1s. It uses
a large uniform array of structs, making a huge number of separate program
resources, and the fixed-size hash table was killing it. Given how many
times we've improved performance by swapping the hash table to
util/hash_table.h, just do it once and for all.
This just rebases the old hash table API on top of util/, for minimal
diff. Cleaning things up is left for later, particularly because I want
to fix up the new hash table API a little bit.
---
src/mesa/program/hash_table.h | 78 +++++++++++-----
src/mesa/program/prog_hash_table.c | 181 -------------------------------------
2 files changed, 54 insertions(+), 205 deletions(-)
diff --git a/src/mesa/program/hash_table.h b/src/mesa/program/hash_table.h
index aba5282fe9e5..362eb2ee0a78 100644
--- a/src/mesa/program/hash_table.h
+++ b/src/mesa/program/hash_table.h
@@ -37,6 +37,7 @@
#include <stdint.h>
#include <limits.h>
#include <assert.h>
+#include "util/hash_table.h"
struct string_to_uint_map;
@@ -44,8 +45,6 @@ struct string_to_uint_map;
extern "C" {
#endif
-struct hash_table;
-
typedef unsigned (*hash_func_t)(const void *key);
typedef bool (*hash_compare_func_t)(const void *key1, const void *key2);
@@ -60,26 +59,32 @@ typedef bool (*hash_compare_func_t)(const void *key1, const void *key2);
* \param hash Function used to compute hash value of input keys.
* \param compare Function used to compare keys.
*/
-extern struct hash_table *hash_table_ctor(unsigned num_buckets,
- hash_func_t hash, hash_compare_func_t compare);
-
+static inline struct hash_table *hash_table_ctor(unsigned num_buckets,
+ hash_func_t hash, hash_compare_func_t compare)
+{
+ return _mesa_hash_table_create(NULL, hash, compare);
+}
/**
* Release all memory associated with a hash table
*
* \warning
- * This function cannot release memory occupied either by keys or data.
+ * This function does not release memory occupied either by keys or data.
*/
-extern void hash_table_dtor(struct hash_table *ht);
-
+static inline void hash_table_dtor(struct hash_table *ht)
+{
+ return _mesa_hash_table_destroy(ht, NULL);
+}
/**
* Flush all entries from a hash table
*
* \param ht Table to be cleared of its entries.
*/
-extern void hash_table_clear(struct hash_table *ht);
-
+static inline void hash_table_clear(struct hash_table *ht)
+{
+ return _mesa_hash_table_clear(ht, NULL);
+}
/**
* Search a hash table for a specific element
@@ -92,25 +97,28 @@ extern void hash_table_clear(struct hash_table *ht);
* the matching key was added. If no matching key exists in the table,
* \c NULL is returned.
*/
-extern void *hash_table_find(struct hash_table *ht, const void *key);
-
+static inline void *hash_table_find(struct hash_table *ht, const void *key)
+{
+ struct hash_entry *entry = _mesa_hash_table_search(ht, key);
+ if (!entry)
+ return NULL;
+ return entry->data;
+}
/**
* Add an element to a hash table
*
* \warning
- * If \c key is already in the hash table, it will be added again. Future
- * calls to \c hash_table_find and \c hash_table_remove will return or remove,
- * repsectively, the most recently added instance of \c key.
- *
- * \warning
* The value passed by \c key is kept in the hash table and is used by later
* calls to \c hash_table_find.
*
* \sa hash_table_replace
*/
-extern void hash_table_insert(struct hash_table *ht, void *data,
- const void *key);
+static inline void hash_table_insert(struct hash_table *ht, void *data,
+ const void *key)
+{
+ _mesa_hash_table_insert(ht, key, data);
+}
/**
* Add an element to a hash table with replacement
@@ -126,13 +134,29 @@ extern void hash_table_insert(struct hash_table *ht, void *data,
*
* \sa hash_table_insert
*/
-extern bool hash_table_replace(struct hash_table *ht, void *data,
- const void *key);
+static inline bool hash_table_replace(struct hash_table *ht, void *data,
+ const void *key)
+{
+ struct hash_entry *entry = _mesa_hash_table_search(ht, key);
+ if (entry) {
+ entry->data = data;
+ return true;
+ } else {
+ _mesa_hash_table_insert(ht, key, data);
+ return false;
+ }
+}
/**
* Remove a specific element from a hash table.
*/
-extern void hash_table_remove(struct hash_table *ht, const void *key);
+static inline void hash_table_remove(struct hash_table *ht, const void *key)
+{
+ struct hash_entry *entry = _mesa_hash_table_search(ht, key);
+
+ if (entry)
+ _mesa_hash_table_remove(ht, entry);
+}
/**
* Compute hash value of a string
@@ -180,12 +204,18 @@ hash_table_pointer_hash(const void *key);
bool
hash_table_pointer_compare(const void *key1, const void *key2);
-void
+static inline void
hash_table_call_foreach(struct hash_table *ht,
void (*callback)(const void *key,
void *data,
void *closure),
- void *closure);
+ void *closure)
+{
+ struct hash_entry *entry;
+
+ hash_table_foreach(ht, entry)
+ callback(entry->key, entry->data, closure);
+}
struct string_to_uint_map *
string_to_uint_map_ctor();
diff --git a/src/mesa/program/prog_hash_table.c b/src/mesa/program/prog_hash_table.c
index f8a7107eb5bd..cbea74c05ab2 100644
--- a/src/mesa/program/prog_hash_table.c
+++ b/src/mesa/program/prog_hash_table.c
@@ -32,187 +32,6 @@
#include "util/simple_list.h"
#include "hash_table.h"
-struct node {
- struct node *next;
- struct node *prev;
-};
-
-struct hash_table {
- hash_func_t hash;
- hash_compare_func_t compare;
-
- unsigned num_buckets;
- struct node buckets[1];
-};
-
-
-struct hash_node {
- struct node link;
- const void *key;
- void *data;
-};
-
-
-struct hash_table *
-hash_table_ctor(unsigned num_buckets, hash_func_t hash,
- hash_compare_func_t compare)
-{
- struct hash_table *ht;
- unsigned i;
-
-
- if (num_buckets < 16) {
- num_buckets = 16;
- }
-
- ht = malloc(sizeof(*ht) + ((num_buckets - 1)
- * sizeof(ht->buckets[0])));
- if (ht != NULL) {
- ht->hash = hash;
- ht->compare = compare;
- ht->num_buckets = num_buckets;
-
- for (i = 0; i < num_buckets; i++) {
- make_empty_list(& ht->buckets[i]);
- }
- }
-
- return ht;
-}
-
-
-void
-hash_table_dtor(struct hash_table *ht)
-{
- hash_table_clear(ht);
- free(ht);
-}
-
-
-void
-hash_table_clear(struct hash_table *ht)
-{
- struct node *node;
- struct node *temp;
- unsigned i;
-
-
- for (i = 0; i < ht->num_buckets; i++) {
- foreach_s(node, temp, & ht->buckets[i]) {
- remove_from_list(node);
- free(node);
- }
-
- assert(is_empty_list(& ht->buckets[i]));
- }
-}
-
-
-static struct hash_node *
-get_node(struct hash_table *ht, const void *key)
-{
- const unsigned hash_value = (*ht->hash)(key);
- const unsigned bucket = hash_value % ht->num_buckets;
- struct node *node;
-
- foreach(node, & ht->buckets[bucket]) {
- struct hash_node *hn = (struct hash_node *) node;
-
- if ((*ht->compare)(hn->key, key) == 0) {
- return hn;
- }
- }
-
- return NULL;
-}
-
-void *
-hash_table_find(struct hash_table *ht, const void *key)
-{
- struct hash_node *hn = get_node(ht, key);
-
- return (hn == NULL) ? NULL : hn->data;
-}
-
-void
-hash_table_insert(struct hash_table *ht, void *data, const void *key)
-{
- const unsigned hash_value = (*ht->hash)(key);
- const unsigned bucket = hash_value % ht->num_buckets;
- struct hash_node *node;
-
- node = calloc(1, sizeof(*node));
- if (node == NULL) {
- _mesa_error_no_memory(__func__);
- return;
- }
-
- node->data = data;
- node->key = key;
-
- insert_at_head(& ht->buckets[bucket], & node->link);
-}
-
-bool
-hash_table_replace(struct hash_table *ht, void *data, const void *key)
-{
- const unsigned hash_value = (*ht->hash)(key);
- const unsigned bucket = hash_value % ht->num_buckets;
- struct node *node;
- struct hash_node *hn;
-
- foreach(node, & ht->buckets[bucket]) {
- hn = (struct hash_node *) node;
-
- if ((*ht->compare)(hn->key, key) == 0) {
- hn->data = data;
- return true;
- }
- }
-
- hn = calloc(1, sizeof(*hn));
- if (hn == NULL) {
- _mesa_error_no_memory(__func__);
- return false;
- }
-
- hn->data = data;
- hn->key = key;
-
- insert_at_head(& ht->buckets[bucket], & hn->link);
- return false;
-}
-
-void
-hash_table_remove(struct hash_table *ht, const void *key)
-{
- struct node *node = (struct node *) get_node(ht, key);
- if (node != NULL) {
- remove_from_list(node);
- free(node);
- return;
- }
-}
-
-void
-hash_table_call_foreach(struct hash_table *ht,
- void (*callback)(const void *key,
- void *data,
- void *closure),
- void *closure)
-{
- unsigned bucket;
-
- for (bucket = 0; bucket < ht->num_buckets; bucket++) {
- struct node *node, *temp;
- foreach_s(node, temp, &ht->buckets[bucket]) {
- struct hash_node *hn = (struct hash_node *) node;
-
- callback(hn->key, hn->data, closure);
- }
- }
-}
-
unsigned
hash_table_string_hash(const void *key)
{
--
2.8.1
More information about the mesa-dev
mailing list