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

[Thomas Helland]

2017-02-09 1:57 GMT+01:00 Timothy Arceri <tarcer at itsqueeze.com>:
> On Wed, 2017-02-08 at 21:35 +0100, Thomas Helland wrote:
>> 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.
>
> Yes Robin Hood hashing looked very interesting, since most of our time
> is spent dealing with collisions I think it would be very interesting
> to explore.
>
>>  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.
>
> Not sure what you mean here.

Yeah, that was a shitty explanation. A bit to tired there, I believe.
What I meant was that we currently have some make-check tests
for the hash table. All of these pass with my robin-hood implementation.
However, when testing it on real life workloads like shader-db,
something bad happens. I suddenly got a hunch yesterday of
what could be the cause; a simple case of == and  >=.
I'll look into it this evening and see if I can get it on the list.

>
>> 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.
>
> Rearranging the table should be faster than doing strcmp and other
> complex key matching 100's? 1000's? 1,000,000's? of times more than is
> needed.
>

As far as I can see from my profiles, string comparisons is actually
not that high on our list in perf. (On a shader-db run that is, it might
be on a game in full running operation, for example). I thought about
it some more yesterday, and the insertion is actually not that bad.
So the speedup on search is probably worth it.

> Also I would hope that most uses of the hash table are not 1:1
> insert/lookup. They certainly won't be for uses outside the compiler,
> e.g Minecraft and reductions in collisions would bring big
> improvements.
>

I don't think they're that bad, but I think that in a lot of cases we
are actually not all that far off, which is kinda bad.

> If you are interested in working on it I'd be very interested to see
> the result :)
>

I'll see what I can do. It's mostly debugging the one issue.
Hopefully that will be something silly that's quick to fix.

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