Re: [Mesa-dev] [PATCH 0/3] Hash-table and hash-set, V4
On Thu, 2015-04-16 at 12:16 -0700, Eric Anholt wrote: Eric Anholt e...@anholt.net writes: Jason Ekstrand ja...@jlekstrand.net writes: On Sat, Apr 11, 2015 at 4:25 PM, Thomas Helland thomashellan...@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.ekstr...@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/ ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 0/3] Hash-table and hash-set, V4
Eric Anholt e...@anholt.net writes: Jason Ekstrand ja...@jlekstrand.net writes: On Sat, Apr 11, 2015 at 4:25 PM, Thomas Helland thomashellan...@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.ekstr...@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. signature.asc Description: PGP signature ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
[Mesa-dev] [PATCH 0/3] Hash-table and hash-set, V4
2015-04-16 21:16 GMT+02:00 Eric Anholt e...@anholt.net: Eric Anholt e...@anholt.net writes: Jason Ekstrand ja...@jlekstrand.net writes: On Sat, Apr 11, 2015 at 4:25 PM, Thomas Helland thomashellan...@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.ekstr...@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 ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 0/3] Hash-table and hash-set, V4
Jason Ekstrand ja...@jlekstrand.net writes: On Sat, Apr 11, 2015 at 4:25 PM, Thomas Helland thomashellan...@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.ekstr...@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. signature.asc Description: PGP signature ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 0/3] Hash-table and hash-set, V4
On Sat, Apr 11, 2015 at 4:25 PM, Thomas Helland thomashellan...@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.ekstr...@intel.com Probably want to give Eric a a couple of days to look at it too. While the profile data looked promising for increasing the table size we start with, decreasing load factor, and integer hashing, there seems to be no benefit to shader-db runtime. Therefore I have dropped these from the series. Thomas Helland (3): util/tests: Expand collision test for hash table util: Change hash_table to use quadratic probing util: Change util/set to use quadratic probing 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.3.4 ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
[Mesa-dev] [PATCH 0/3] Hash-table and hash-set, V4
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) While the profile data looked promising for increasing the table size we start with, decreasing load factor, and integer hashing, there seems to be no benefit to shader-db runtime. Therefore I have dropped these from the series. Thomas Helland (3): util/tests: Expand collision test for hash table util: Change hash_table to use quadratic probing util: Change util/set to use quadratic probing 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.3.4 ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
