[Mesa-dev] [PATCH 0/3] Hash-table and hash-set, V4

[Thomas Helland]

2015-04-16 21:16 GMT+02:00 Eric Anholt <eric at anholt.net>:
> Eric Anholt <eric at anholt.net> writes:
>
>> Jason Ekstrand <jason at jlekstrand.net> writes:
>>
>>> On Sat, Apr 11, 2015 at 4:25 PM, Thomas Helland
>>> <thomashelland90 at gmail.com> wrote:
>>>> The performance numbers (shader-db runtime) are:
>>>>
>>>> Difference at 95.0% confidence
>>>>       -14.7608 +/- 3.36786
>>>>      -9.05064% +/- 2.06501%
>>>> (Original runtime was 160 seconds)
>>>
>>> Good Work!
>>>
>>> I had one comment on the hash set patch.  With that fixed, the series is
>>>
>>> Reviewed-by: Jason Ekstrand <jason.ekstrand at intel.com>
>>>
>>> Probably want to give Eric a a couple of days to look at it too.
>>
>> Yeah, I'm splitting the series up into each individual change (resizing
>> cutoff, linear probing, power-of-two, then quadratic probing) so that we
>> can make sure that they're all good for both the compiler and GL object
>> lookup.
>
> OK, I've got a split out series on hash-quadratic of my tree.  Here's be
> bad news from the last commit:
>
>     However, over the course of this series, INTEL_NO_HW=1 minecraft is still
>     down by -0.615582% +/- 0.514508% (n=55).  If we drop 2 low outliers each
>     from before/after of that dataset, the image is more clear: -0.538901% +/-
>     0.381768% (n=53).
>
> It looks like the collision reprobe changes are hurting too much.  The
> fact that collision is that big of a deal is bad -- I thought we should
> be having basically no collision in Mesa's GL hash tables, but I guess a
> lot of objects have been deleted before new ones are genned (and this
> probably also means that our benchmarking, which tends to execute a
> timedemo once instead of doing level loads multiple times, is
> underestimating the problems we have in our GL name hash tables).  This
> probably means we should be looking into making GL gen its handles from
> the lowest unused number when possible, and using an array for most of
> the hash table.  Until we do, I don't think we want to change our hash
> table to improve compiler performance at the expense of runtime
> performance.

Well, that's rather unfortunate.
Thanks for giving this a thorough review.
Decreasing the load factor of the table should decrease
lookup cost, and while that did not do much for the run-time
of shader-db, it might improve your test case.

Robin-Hood hashing is also a possibility. It apparently works
well for hash tables with a load factor up to 0.9.
The average reprobe length is then approximately 6 reprobes.
Reducing the load factor should lower it even more.
Robin-Hood because you "steal" from the entries with a
short reprobe length and "give" to those with a long one
by swapping entries when inserting in the table.
I've only seen it used with linear probing, but I don't see why it
couldn't be done with a quadratic probing implementation.
It's a bit more complicated, as one also needs to handle
deletion smarter by  "back-shifting", or else performance
will degrade as a lot deletes are performed.
However, lookup-speed is very good since clusters of entries
will be sorted by hash, and therefore we can exit early when
doing a lookup if the hash we are searching for is less than
the hash we are now checking against.
If there's interest I can take a shot at that too.

-Thomas