This series came about when I saw a talk online, while simultaneously being annoyd about the needless waste of memory in our set as reported by pahole. I have previously made some patches that changed our hash table from a reprobing one to a quadratic probing one, in the name of lower overhead and better cache locality, but I was not quite satisfied.
I'm sending this series out now, as it seems like an ideal time since Timothy is working at reducing our compile times. Further details about the implementation and its advantages are described in the patches. I've found this to give a reduction in shader-db runtime of about 2%, but I have to do some more testing on my main computer, as my laptop is showing its age with some terrible thermal issues. This special cases on pointers, as that is a very common usecase. This allows us to drop some comparisons, and reduce the total size of our hash table to 70% or our current and the set to 50%. It uses linear probing and power-of-two table sizes to get good cache locality. In the pointer_map caes it moves the stored hashes out into it's own array for even better cache locality. I'm not sure if we want another set and map amongst our utils, but the patch series is simple enough, and complete enough, that I thought I could share it for some inital comments. CC: Timothy Arceri <tarc...@itsqueeze.com> Thomas Helland (18): util: Add initial pointer map implementation glsl: Use pointer map in constant propagation util: Add a pointer map clone function glsl: Port copy propagation elements to pointer map glsl: Move ir_variable_refcount to using the pointer map nir: Change lower_vars_to_ssa to use pointer map glsl: Use pointer map in copy propagation glsl: Use pointer map in opt_constant_variable glsl: Change glsl_to_nir to user pointer map util: Add a call_foreach function to the pointer map glsl: Use the pointer map in the glsl linker nir: Use pointer map in nir_from_ssa util: Add a pointer set implementation nir: Migrate lower_vars_to_ssa to use pointer set glsl: Use pointer set in opt_copy_propagation nir: Use pointer set in remove_dead_variable nir: Use pointer_set in nir_propagate_invariant util: Just cut the hash in the pointer table src/compiler/glsl/glsl_to_nir.cpp | 31 +- src/compiler/glsl/ir_variable_refcount.cpp | 13 +- src/compiler/glsl/ir_variable_refcount.h | 4 +- src/compiler/glsl/linker.cpp | 40 ++- src/compiler/glsl/opt_constant_propagation.cpp | 47 ++-- src/compiler/glsl/opt_constant_variable.cpp | 34 +-- src/compiler/glsl/opt_copy_propagation.cpp | 95 +++---- .../glsl/opt_copy_propagation_elements.cpp | 96 ++++--- src/compiler/glsl/opt_dead_code.cpp | 6 +- src/compiler/nir/nir_from_ssa.c | 18 +- src/compiler/nir/nir_lower_vars_to_ssa.c | 48 ++-- src/compiler/nir/nir_propagate_invariant.c | 33 +-- src/compiler/nir/nir_remove_dead_variables.c | 37 +-- src/util/meson.build | 4 + src/util/pointer_map.c | 313 +++++++++++++++++++++ src/util/pointer_map.h | 110 ++++++++ src/util/pointer_set.c | 266 +++++++++++++++++ src/util/pointer_set.h | 90 ++++++ 18 files changed, 1026 insertions(+), 259 deletions(-) create mode 100644 src/util/pointer_map.c create mode 100644 src/util/pointer_map.h create mode 100644 src/util/pointer_set.c create mode 100644 src/util/pointer_set.h -- 2.16.2 _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev