From 1496cc92f6f743f10e1f3c9c63787d79febfda40 Mon Sep 17 00:00:00 2001 From: Anthony Pesch Date: Sat, 18 Jan 2020 01:38:31 -0500 Subject: [PATCH] util/hash_table: added hash functions for integer types A few hash_table users roll their own integer hash functions which call _mesa_hash_data to perform the hashing which ultimately calls into XXH32 with a dynamic key length. When using small keys with a constant size the hash rate can be greatly improved by inlining XXH32 and providing it a constant key length, see: https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html Additionally, this patch removes calls to _mesa_key_hash_string and makes them instead call _mesa_has_string directly, matching the new integer hash functions. Reviewed-by: Eric Anholt Reviewed-by: Iago Toral Quiroga Part-of: --- .../glsl/gl_nir_lower_samplers_as_deref.c | 4 +- src/compiler/glsl/glcpp/glcpp-parse.y | 2 +- src/compiler/glsl/link_interface_blocks.cpp | 2 +- src/compiler/glsl/link_uniform_blocks.cpp | 2 +- src/compiler/glsl/link_varyings.cpp | 6 +-- src/compiler/glsl/lower_int64.cpp | 2 +- .../glsl/lower_named_interface_blocks.cpp | 2 +- src/compiler/glsl/lower_output_reads.cpp | 2 +- src/compiler/glsl/string_to_uint_map.h | 2 +- src/compiler/glsl/tests/varyings_test.cpp | 4 +- src/compiler/glsl_types.cpp | 4 +- src/compiler/nir/nir_print.c | 2 +- src/intel/perf/gen_perf.c | 2 +- src/mesa/program/symbol_table.c | 2 +- src/util/hash_table.c | 44 +++++++++++++++++++ src/util/hash_table.h | 20 ++++----- src/util/tests/hash_table/destroy_callback.c | 2 +- src/util/tests/hash_table/insert_and_lookup.c | 2 +- src/util/tests/hash_table/remove_key.c | 2 +- src/util/tests/hash_table/replacement.c | 2 +- 20 files changed, 76 insertions(+), 34 deletions(-) diff --git a/src/compiler/glsl/gl_nir_lower_samplers_as_deref.c b/src/compiler/glsl/gl_nir_lower_samplers_as_deref.c index d949e3d78f5..dde858f9cfc 100644 --- a/src/compiler/glsl/gl_nir_lower_samplers_as_deref.c +++ b/src/compiler/glsl/gl_nir_lower_samplers_as_deref.c @@ -168,7 +168,7 @@ lower_deref(nir_builder *b, struct lower_samplers_as_deref_state *state, return deref; } - uint32_t hash = _mesa_key_hash_string(name); + uint32_t hash = _mesa_hash_string(name); struct hash_entry *h = _mesa_hash_table_search_pre_hashed(state->remap_table, hash, name); @@ -325,7 +325,7 @@ gl_nir_lower_samplers_as_deref(nir_shader *shader, state.shader = shader; state.shader_program = shader_program; - state.remap_table = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + state.remap_table = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); nir_foreach_function(function, shader) { diff --git a/src/compiler/glsl/glcpp/glcpp-parse.y b/src/compiler/glsl/glcpp/glcpp-parse.y index 514dbe7a4c4..1e57cccc4d1 100644 --- a/src/compiler/glsl/glcpp/glcpp-parse.y +++ b/src/compiler/glsl/glcpp/glcpp-parse.y @@ -1469,7 +1469,7 @@ glcpp_parser_create(struct gl_context *gl_ctx, parser = ralloc (NULL, glcpp_parser_t); glcpp_lex_init_extra (parser, &parser->scanner); - parser->defines = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + parser->defines = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); parser->linalloc = linear_alloc_parent(parser, 0); parser->active = NULL; diff --git a/src/compiler/glsl/link_interface_blocks.cpp b/src/compiler/glsl/link_interface_blocks.cpp index deb544e3ce6..4471b41cf0e 100644 --- a/src/compiler/glsl/link_interface_blocks.cpp +++ b/src/compiler/glsl/link_interface_blocks.cpp @@ -220,7 +220,7 @@ class interface_block_definitions public: interface_block_definitions() : mem_ctx(ralloc_context(NULL)), - ht(_mesa_hash_table_create(NULL, _mesa_key_hash_string, + ht(_mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal)) { } diff --git a/src/compiler/glsl/link_uniform_blocks.cpp b/src/compiler/glsl/link_uniform_blocks.cpp index 4670a24598a..1603cbd59af 100644 --- a/src/compiler/glsl/link_uniform_blocks.cpp +++ b/src/compiler/glsl/link_uniform_blocks.cpp @@ -409,7 +409,7 @@ link_uniform_blocks(void *mem_ctx, * the hash is organized by block-name. */ struct hash_table *block_hash = - _mesa_hash_table_create(mem_ctx, _mesa_key_hash_string, + _mesa_hash_table_create(mem_ctx, _mesa_hash_string, _mesa_key_string_equal); if (block_hash == NULL) { diff --git a/src/compiler/glsl/link_varyings.cpp b/src/compiler/glsl/link_varyings.cpp index c7774a2531b..0868d1504db 100644 --- a/src/compiler/glsl/link_varyings.cpp +++ b/src/compiler/glsl/link_varyings.cpp @@ -2583,13 +2583,13 @@ assign_varying_locations(struct gl_context *ctx, consumer ? consumer->Stage : MESA_SHADER_NONE); void *hash_table_ctx = ralloc_context(NULL); hash_table *tfeedback_candidates = - _mesa_hash_table_create(hash_table_ctx, _mesa_key_hash_string, + _mesa_hash_table_create(hash_table_ctx, _mesa_hash_string, _mesa_key_string_equal); hash_table *consumer_inputs = - _mesa_hash_table_create(hash_table_ctx, _mesa_key_hash_string, + _mesa_hash_table_create(hash_table_ctx, _mesa_hash_string, _mesa_key_string_equal); hash_table *consumer_interface_inputs = - _mesa_hash_table_create(hash_table_ctx, _mesa_key_hash_string, + _mesa_hash_table_create(hash_table_ctx, _mesa_hash_string, _mesa_key_string_equal); ir_variable *consumer_inputs_with_locations[VARYING_SLOT_TESS_MAX] = { NULL, diff --git a/src/compiler/glsl/lower_int64.cpp b/src/compiler/glsl/lower_int64.cpp index 2d4fdbb1a55..43774d6ab33 100644 --- a/src/compiler/glsl/lower_int64.cpp +++ b/src/compiler/glsl/lower_int64.cpp @@ -73,7 +73,7 @@ public: function_list(), added_functions(&function_list, mem_ctx) { functions = _mesa_hash_table_create(mem_ctx, - _mesa_key_hash_string, + _mesa_hash_string, _mesa_key_string_equal); foreach_in_list(ir_instruction, node, instructions) { diff --git a/src/compiler/glsl/lower_named_interface_blocks.cpp b/src/compiler/glsl/lower_named_interface_blocks.cpp index 498954a33e5..01c50932a9a 100644 --- a/src/compiler/glsl/lower_named_interface_blocks.cpp +++ b/src/compiler/glsl/lower_named_interface_blocks.cpp @@ -125,7 +125,7 @@ public: void flatten_named_interface_blocks_declarations::run(exec_list *instructions) { - interface_namespace = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + interface_namespace = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); /* First pass: adjust instance block variables with an instance name diff --git a/src/compiler/glsl/lower_output_reads.cpp b/src/compiler/glsl/lower_output_reads.cpp index 4f90c7385ad..7a182130b2e 100644 --- a/src/compiler/glsl/lower_output_reads.cpp +++ b/src/compiler/glsl/lower_output_reads.cpp @@ -72,7 +72,7 @@ static unsigned hash_table_var_hash(const void *key) { const ir_variable * var = static_cast(key); - return _mesa_key_hash_string(var->name); + return _mesa_hash_string(var->name); } output_read_remover::output_read_remover(unsigned stage) diff --git a/src/compiler/glsl/string_to_uint_map.h b/src/compiler/glsl/string_to_uint_map.h index e0533ec6ea5..6f9251f90c3 100644 --- a/src/compiler/glsl/string_to_uint_map.h +++ b/src/compiler/glsl/string_to_uint_map.h @@ -61,7 +61,7 @@ struct string_to_uint_map { public: string_to_uint_map() { - this->ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + this->ht = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); } diff --git a/src/compiler/glsl/tests/varyings_test.cpp b/src/compiler/glsl/tests/varyings_test.cpp index 74957734858..4ad73be381e 100644 --- a/src/compiler/glsl/tests/varyings_test.cpp +++ b/src/compiler/glsl/tests/varyings_test.cpp @@ -80,11 +80,11 @@ link_varyings::SetUp() this->ir.make_empty(); this->consumer_inputs = - _mesa_hash_table_create(NULL, _mesa_key_hash_string, + _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); this->consumer_interface_inputs = - _mesa_hash_table_create(NULL, _mesa_key_hash_string, + _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); /* Needs to happen after glsl type initialization */ diff --git a/src/compiler/glsl_types.cpp b/src/compiler/glsl_types.cpp index b357ed0823b..79e2f684fcf 100644 --- a/src/compiler/glsl_types.cpp +++ b/src/compiler/glsl_types.cpp @@ -642,7 +642,7 @@ glsl_type::get_instance(unsigned base_type, unsigned rows, unsigned columns, if (explicit_matrix_types == NULL) { explicit_matrix_types = - _mesa_hash_table_create(NULL, _mesa_key_hash_string, + _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); } @@ -1007,7 +1007,7 @@ glsl_type::get_array_instance(const glsl_type *base, assert(glsl_type_users > 0); if (array_types == NULL) { - array_types = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + array_types = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); } diff --git a/src/compiler/nir/nir_print.c b/src/compiler/nir/nir_print.c index 9a03f6eee70..eaf902b4cd4 100644 --- a/src/compiler/nir/nir_print.c +++ b/src/compiler/nir/nir_print.c @@ -1486,7 +1486,7 @@ init_print_state(print_state *state, nir_shader *shader, FILE *fp) state->fp = fp; state->shader = shader; state->ht = _mesa_pointer_hash_table_create(NULL); - state->syms = _mesa_set_create(NULL, _mesa_key_hash_string, + state->syms = _mesa_set_create(NULL, _mesa_hash_string, _mesa_key_string_equal); state->index = 0; } diff --git a/src/intel/perf/gen_perf.c b/src/intel/perf/gen_perf.c index 38dc0166106..ceb10f5af12 100644 --- a/src/intel/perf/gen_perf.c +++ b/src/intel/perf/gen_perf.c @@ -967,7 +967,7 @@ load_oa_metrics(struct gen_perf_config *perf, int fd, return false; perf->oa_metrics_table = - _mesa_hash_table_create(perf, _mesa_key_hash_string, + _mesa_hash_table_create(perf, _mesa_hash_string, _mesa_key_string_equal); /* Index all the metric sets mesa knows about before looking to see what diff --git a/src/mesa/program/symbol_table.c b/src/mesa/program/symbol_table.c index 0dcb1f292c9..ae7a1175e40 100644 --- a/src/mesa/program/symbol_table.c +++ b/src/mesa/program/symbol_table.c @@ -292,7 +292,7 @@ _mesa_symbol_table_ctor(void) struct _mesa_symbol_table *table = calloc(1, sizeof(*table)); if (table != NULL) { - table->ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + table->ht = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); _mesa_symbol_table_push_scope(table); diff --git a/src/util/hash_table.c b/src/util/hash_table.c index 48d59e48431..6bac4a4f68e 100644 --- a/src/util/hash_table.c +++ b/src/util/hash_table.c @@ -555,6 +555,24 @@ _mesa_hash_data(const void *data, size_t size) return XXH32(data, size, 0); } +uint32_t +_mesa_hash_int(const void *key) +{ + return XXH32(key, sizeof(int), 0); +} + +uint32_t +_mesa_hash_uint(const void *key) +{ + return XXH32(key, sizeof(unsigned), 0); +} + +uint32_t +_mesa_hash_u32(const void *key) +{ + return XXH32(key, 4, 0); +} + /** FNV-1a string hash implementation */ uint32_t _mesa_hash_string(const void *_key) @@ -570,6 +588,32 @@ _mesa_hash_string(const void *_key) return hash; } +uint32_t +_mesa_hash_pointer(const void *pointer) +{ + uintptr_t num = (uintptr_t) pointer; + return (uint32_t) ((num >> 2) ^ (num >> 6) ^ (num >> 10) ^ (num >> 14)); +} + +bool +_mesa_key_int_equal(const void *a, const void *b) +{ + return *((const int *)a) == *((const int *)b); +} + +bool +_mesa_key_uint_equal(const void *a, const void *b) +{ + + return *((const unsigned *)a) == *((const unsigned *)b); +} + +bool +_mesa_key_u32_equal(const void *a, const void *b) +{ + return *((const uint32_t *)a) == *((const uint32_t *)b); +} + /** * String compare function for use as the comparison callback in * _mesa_hash_table_create(). diff --git a/src/util/hash_table.h b/src/util/hash_table.h index e2cd889f6da..b1eb9d4e217 100644 --- a/src/util/hash_table.h +++ b/src/util/hash_table.h @@ -109,21 +109,19 @@ _mesa_hash_table_random_entry(struct hash_table *ht, bool (*predicate)(struct hash_entry *entry)); uint32_t _mesa_hash_data(const void *data, size_t size); + +uint32_t _mesa_hash_int(const void *key); +uint32_t _mesa_hash_uint(const void *key); +uint32_t _mesa_hash_u32(const void *key); uint32_t _mesa_hash_string(const void *key); +uint32_t _mesa_hash_pointer(const void *pointer); + +bool _mesa_key_int_equal(const void *a, const void *b); +bool _mesa_key_uint_equal(const void *a, const void *b); +bool _mesa_key_u32_equal(const void *a, const void *b); bool _mesa_key_string_equal(const void *a, const void *b); bool _mesa_key_pointer_equal(const void *a, const void *b); -static inline uint32_t _mesa_key_hash_string(const void *key) -{ - return _mesa_hash_string((const char *)key); -} - -static inline uint32_t _mesa_hash_pointer(const void *pointer) -{ - uintptr_t num = (uintptr_t) pointer; - return (uint32_t) ((num >> 2) ^ (num >> 6) ^ (num >> 10) ^ (num >> 14)); -} - struct hash_table * _mesa_pointer_hash_table_create(void *mem_ctx); diff --git a/src/util/tests/hash_table/destroy_callback.c b/src/util/tests/hash_table/destroy_callback.c index 3a050ff2ae2..e6c7ac5c16f 100644 --- a/src/util/tests/hash_table/destroy_callback.c +++ b/src/util/tests/hash_table/destroy_callback.c @@ -56,7 +56,7 @@ main(int argc, char **argv) (void) argc; (void) argv; - ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + ht = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); _mesa_hash_table_insert(ht, str1, NULL); diff --git a/src/util/tests/hash_table/insert_and_lookup.c b/src/util/tests/hash_table/insert_and_lookup.c index 1fd7353689f..f1244649053 100644 --- a/src/util/tests/hash_table/insert_and_lookup.c +++ b/src/util/tests/hash_table/insert_and_lookup.c @@ -43,7 +43,7 @@ main(int argc, char **argv) (void) argc; (void) argv; - ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + ht = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); _mesa_hash_table_insert(ht, str1, NULL); diff --git a/src/util/tests/hash_table/remove_key.c b/src/util/tests/hash_table/remove_key.c index 6df6d7d0366..1abc68dfc90 100644 --- a/src/util/tests/hash_table/remove_key.c +++ b/src/util/tests/hash_table/remove_key.c @@ -40,7 +40,7 @@ main(int argc, char **argv) (void) argc; (void) argv; - ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string, _mesa_key_string_equal); + ht = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); _mesa_hash_table_insert(ht, str1, NULL); _mesa_hash_table_insert(ht, str2, NULL); diff --git a/src/util/tests/hash_table/replacement.c b/src/util/tests/hash_table/replacement.c index e74e63453c4..a3759a3c93c 100644 --- a/src/util/tests/hash_table/replacement.c +++ b/src/util/tests/hash_table/replacement.c @@ -45,7 +45,7 @@ main(int argc, char **argv) assert(str1 != str2); - ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string, + ht = _mesa_hash_table_create(NULL, _mesa_hash_string, _mesa_key_string_equal); _mesa_hash_table_insert(ht, str1, str1); -- 2.30.2