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

[Timothy Arceri]

On 09/02/17 18:31, Thomas Helland wrote:
> 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.

Ok cool. Do you have a branch I can take a peek at somewhere?

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

 From what I remember when profiling this back in 2014 (and from the 
emails I sent) was that in applications the majority of time was spent 
resolving collisions, which usually involved some kind of memcmp.

>
>> 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(-)
>>>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev