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

[Thomas Helland]

2017-02-08 21:35 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
> 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 stats are wrong. I recompiled stuff, so the symbols got
mangled in the libraries. So here is the correct data (after increasing
the initial size of the set and hash table to 8, so not perfectly comparable):
hash_table_search: 3.88% -> 1.84%
hash_table_insert: 2.26% -> 1.16%
_mesa_hash_data is unchanged (which is kinda obvious).
set_add: 0.70% -> 0.35%
set_search: 0.59% -> 0.27%

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