2017-02-09 1:57 GMT+01:00 Timothy Arceri <tar...@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. > >> 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. > 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@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev
