On 09/02/17 18:31, Thomas Helland wrote:
2017-02-09 1:57 GMT+01:00 Timothy Arceri <[email protected]>:
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.
Ok cool. Do you have a branch I can take a peek at somewhere?
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.
From what I remember when profiling this back in 2014 (and from the
emails I sent) was that in applications the majority of time was spent
resolving collisions, which usually involved some kind of memcmp.
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
[email protected]
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
_______________________________________________
mesa-dev mailing list
[email protected]
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
