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

[Timothy Arceri]

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.

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

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.

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

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