From ee02a5e330151630be871decde563ddbf192465c Mon Sep 17 00:00:00 2001 From: Eric Anholt Date: Tue, 9 Aug 2016 00:11:13 -0700 Subject: [PATCH] prog_hash_table: Convert to using util/hash_table.h. 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. v2: Add UNUSED to the now-unused parameter. Reviewed-by: Ian Romanick Reviewed-by: Timothy Arceri --- 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 aba5282..91fc11e 100644 --- a/src/mesa/program/hash_table.h +++ b/src/mesa/program/hash_table.h @@ -37,6 +37,7 @@ #include #include #include +#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(UNUSED 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 f8a7107..cbea74c 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.7.4