<div dir="auto"><div>Oh, and an important disclaimer.</div><div dir="auto">I have not ran this through picking, nor have I done a complete </div><div dir="auto">run of shader-db for performance comparisons on more realistic workloads.</div><div dir="auto">I'll see what time I can find this evening, or some time tomorrow. <div class="gmail_extra" dir="auto"> <div class="gmail_quote">On Jan 1, 2017 19:38, "Thomas Helland" <<a href="mailto:thomashelland90@gmail.com">thomashelland90@gmail.com</a>> wrote: <blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all. This is a series I've put together to lower the overhead of the copy propagation pass in glsl. The series is not refined, so please treat it as a proof of concept / RFC. The first five patches might be merge-ready, but their benefit is quite low compared to the actual major change here. The series goes on to copy our existing hash table implementation, and modify it in steps to allow insertion of multiple data entries with the same key. I've kept the series in steps corresponding to the way I worked when modifying it, as I found it nice for clarity. There is some obvious cleanups and squashing that will need to happen before this can be considered for merging. The major change is the last patch. This uses the new hash table in our copy propagation pass. This effectively makes the algorithm O(2n) instead of O(n^2), which is a big win. I tested with the shader mentioned in [1] but took the shaders and made a shader_test that I used in conjunction with shader-db to do testing. I cut down on the ridiculous amount of expression some, to make it even compile in a reasonable time on my poor laptop. So, on to the results. Compilation of the aforementioned shader went from 98 to 75 seconds. Perf shows that previously we spent 19% of the time walking the acp-table with _mesa_hash_table_next_entry. After this series, the hash table is practically gone from the profile. This is a major win, and I'm guite happy with the results. There is obviously a lot more work to be done though. Please leave critical feedback and ideas. This was merely a test from my part, but it seems there is some opportunities here. <a href="https://bugs.freedesktop.org/show_bug.cgi?id=94477" rel="noreferrer" target="_blank">https://bugs.freedesktop.org/show_bug.cgi?id=94477</a> Thomas Helland (14): glsl: Don't rehash the values when copying to new table glsl: Don't compute the hash when we already have it available nir: Remove unused include of nir_array nir: Move nir_array to util, and rename to dyn_array glsl: Use dyn_array instead of the exec_list util: Make a copy of the existing hash table implementation util: Add field for pointing to next data util: Implement the insertion functionality util: Implement deletion of entries util: Add a comment about ordering of entries with matching keys util: Implement returning the last added entry on search util: Rename functions and structs util: Use hashing functions from hash_table.h glsl: Restructure copy propagation to use the non replacing hash table src/compiler/Makefile.sources | 1 - src/compiler/glsl/opt_copy_propagation.cpp | 112 +++-- .../glsl/opt_copy_propagation_elements.cpp | 6 +- src/compiler/nir/nir_lower_locals_to_regs.c | 1 - src/compiler/spirv/vtn_cfg.c | 6 +- src/compiler/spirv/vtn_private.h | 4 +- src/util/Makefile.sources | 3 + src/{compiler/nir/nir_array.h => util/dyn_array.h} | 18 +- src/util/non_replacing_hash_table.c | 513 +++++++++++++++++++++ src/util/non_replacing_hash_table.h | 135 ++++++ 10 files changed, 743 insertions(+), 56 deletions(-) rename src/{compiler/nir/nir_array.h => util/dyn_array.h} (86%) create mode 100644 src/util/non_replacing_hash_table.c create mode 100644 src/util/non_replacing_hash_table.h -- 2.11.0 </blockquote></div> </div></div></div>