[Mesa-dev] [PATCH 00/18] [RFC] Pointer specific data structures

[Thomas Helland]

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 <tarceri at 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