[Mesa-dev] [PATCH 0/4] RFC: Quadratic probing for the win

[Thomas Helland]

I was cleaning up my local git repo, and came across this series.
Last time it was discussed was all the way back in April 2015.
Things looked pretty good back then, but we where seeing a smaller
regression in CPU-bound scenarios as Eric found with forcing software 
rendering while running Minecraft.

I figured I'd do a retest of the series to see how it fares today.
Using perf on shader-db I see:
hash_table_search being cut from 3.88% down to 1.83%.
_mesa_hash_data being cut from 1.47% down to 1.25%
_mesa_hash_table_rehash going from 0.23% up to 1.16%
hash_table_insert being cut from 2.26% down to 0.33%

This yields an approximate 10% reduction in shader-db runtime.

The increase in the rehash function is a bit peculiar.
I'll look into increasing the table one more step, as a four entry
hash table seems a bit on the low side. I'll also work on getting
some more reliable numbers from a real world application, along
with some more runs of shader-db to get better statistical certainty.
I'll pull out my i3-6100 / RX460 combo and give this a spin
with Borderlands 2 I think, as Marek's threaded GL work suggests
this is a title with heavy CPU bottlenecking.

As a side note, Robin Hood hashing was mentioned in the thread from
back in April 2015. I actually have an implementation of that, but
I'm still working out an issue that our make-check tests doesn't
catch that causes corruption in the table when runing shader-db.
I'm not to sure about it's effect though, as it sacrifices insert
speed for lookup speed, but one never knows until one tests.

Let me know if this is something I should persue. If not I'll
mark this series as "junk" in my git repo, and get on with the cleaning.

Thomas Helland (4):
  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

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

-- 
2.11.1