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

[Timothy Arceri]

On Wed, 8 Feb 2017 15:59:55 -0800
Jason Ekstrand <jason at jlekstrand.net> wrote:

> On Wed, Feb 8, 2017 at 3:01 PM, Marek Olšák <maraeo at gmail.com> wrote:
> 
> > I think this is good stuff. I'd gladly take it just for the
> > shader-db improvement.
> >  
> 
> Agreed.  If it really did hurt minecraft before, we should try that
> again just to be sure, but I like faster shader compilation.
> 

Maybe someone should do a quick test with a larger shader-db
collection. Not that the results don't look good but I believe Thomas
has a smaller collection that the one used by Marek and Intel.

> 
> > Marek
> >
> > On Wed, Feb 8, 2017 at 11:35 PM, Thomas Helland
> > <thomashelland90 at gmail.com> wrote:  
> > > 2017-02-08 22:07 GMT+01:00 Thomas Helland
> > > <thomashelland90 at gmail.com>:  
> > >> 2017-02-08 21:35 GMT+01:00 Thomas Helland
> > >> <thomashelland90 at gmail.com>:  
> > >>> 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 stats are wrong. I recompiled stuff, so the symbols got
> > >> mangled in the libraries. So here is the correct data (after
> > >> increasing the initial size of the set and hash table to 8, so
> > >> not perfectly  
> > comparable):  
> > >> hash_table_search: 3.88% -> 1.84%
> > >> hash_table_insert: 2.26% -> 1.16%
> > >> _mesa_hash_data is unchanged (which is kinda obvious).
> > >> set_add: 0.70% -> 0.35%
> > >> set_search: 0.59% -> 0.27%
> > >>  
> > >>> 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. 
> > >
> > > Using this hardware I ran the Metro LL Redux benchmark mode
> > > through phoronix-test-suite as a quick test. Average fps improved
> > > from 43,97 to 45.23. So not insane, but a decent gain of 2-3%.
> > > I'll come back with some more numbers from in-game play of
> > > some other games in my possession. Likely CS:GO, portal,
> > > TF2, dota2, borderlands 2, or some other games I have.
> > >  
> > >>> As a side note, Robin Hood hashing was mentioned in the thread
> > >>> from back in April 2015. 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. 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.
> > >>>
> > >>> 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(-)
> > >>>
> > >>> --
> > >>> 2.11.1
> > >>>  
> > > _______________________________________________
> > > mesa-dev mailing list
> > > mesa-dev at lists.freedesktop.org
> > > https://lists.freedesktop.org/mailman/listinfo/mesa-dev  
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev at lists.freedesktop.org
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
> >