[Mesa-dev] [PATCH 0/7] Another take on the hash table

[Thomas Helland]

I think this should pretty much be the patches in their final form.
A recap of the history as of now: The minecraft tests that Eric Anholt
did was based on a replay of an apitrace. So that is likely not all
that representative of real life workloads. Name lookups was the one
big thing that the minecraft replay abused badly. So if someone
has a favourite testcase for this then I'm all ears.

Some numbers from running shader-db single threaded:
hash_table_search: 3.88% -> 1.84%
hash_table_insert: 2.26% -> 1.16%
set_add: 0.70% -> 0.35%
set_search: 0.59% -> 0.27%
_mesa_hash_data is cut from 1.52% to basically nothing, and is replaced
with _mesa_hash_pointer at 0.11%

Runtime of shader-db, five runs (left is before, right is after)
195.06  -->  187.62
194.39  -->  182.20
194.12  -->  181.79
199.27  -->  182.08
194.18  -->  182.16

There are some outliers here, but I thought the general trend
was clear enough that I didn't persue more runs. Aproximately 7.5%
runtime improvement, which matches quite well with the findings from
years ago, where I actually used ministat to get statistically
significant numbers on this.

I've done some tests on my i3-6100 / RX460 combo running the
metro ll, cs:go, dota2 and talos principle test profiles using the
phoronix test suite. No significant changes where detected.
So if you have a favourite workload that could benefit, let me know,
or give the series a spin yourself =)

New in this version is the last patch, that reworks our pointer hashing.
This patch has been tested on shader-db, but has not been tested on
other workloads, like the above mentioned games. That's on my todo-lsit.

Thomas Helland (7):
  util/tests: Expand collision test for hash table
  util: Change hash_table to use quadratic probing
  util: Change util/set to use quadratic probing
  util: Use set_foreach instead of rolling our own
  util: Increase start size of hash table and set to 8
  util: Use a starting load factor of 7/8 entries
  util: Change the pointer hashing function

 src/util/hash_table.c                 | 102 +++++++++--------------------
 src/util/hash_table.h                 |   6 +-
 src/util/set.c                        | 118 ++++++++++++----------------------
 src/util/set.h                        |   3 +-
 src/util/tests/hash_table/collision.c |  14 ++++
 5 files changed, 91 insertions(+), 152 deletions(-)

-- 
2.11.1