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

[Timothy Arceri]

On Thu, 2015-04-16 at 12:16 -0700, Eric Anholt wrote:
> 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,

Hi guys,

This is consistent with what I reported back in November "most time is
spent doing the hash and resolving collisions" [1], in the game
benchmarks I profiled most time was spent doing the hash and resolving
collisions. The harder thing to determine at the time was if this was
actually a bottle neck or not.

I also found that there was a large difference between what oprofile and
callgrind reported, oprofile seemed to give large varying results when
it came to the hash table.

Anyway as I've stated before I was able to observe a nice boost using a
simple implementation of the crc32 intrinsic for hashing. I also read
somewhere that crc32 could be better for avoiding collisions but I
didn't notice any difference in my testing they were both equally bad.

I never submitted my patch as I couldn't measure any frame rate
difference caused by the change however I'm happy to recreate it if Eric
would like to test it out, it seems Minecraft is a good test.

Not useful for the current Raspberry Pi but ARMv8 also has a crc
intrinsic maybe useful Raspberry Pi 3? Or for the other ARM devices
using Mesa.

>From what I saw previously I agree that Robin Hood hashing looks like a
good fit for the mesa hash table, the resource I pointed to previously
has a good deal of information on it [2].

[1]
http://lists.freedesktop.org/archives/mesa-dev/2014-November/071512.html
[2] http://codecapsule.com/2013/11/11/robin-hood-hashing/