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

[Thomas Helland]

2017-02-08 22:07 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
> 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.
>>

Using this hardware I ran the Metro LL Redux benchmark mode
through phoronix-test-suite as a quick test. Average fps improved
from 43,97 to 45.23. So not insane, but a decent gain of 2-3%.
I'll come back with some more numbers from in-game play of
some other games in my possession. Likely CS:GO, portal,
TF2, dota2, borderlands 2, or some other games I have.

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