[Mesa-dev] [PATCH 3/4] prog_hash_table: Convert to using util/hash_table.h.
Ian Romanick
idr at freedesktop.org
Tue Aug 9 23:06:15 UTC 2016
On 08/09/2016 10:17 AM, Eric Anholt wrote:
> 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,
^
Add UNUSED here to avoid piles of unused parameter warnings in my build.
> + 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)
> {
>
More information about the mesa-dev
mailing list