[Mesa-dev] [PATCH 00/14] [RFC] Optimizations on copy propagation

[Thomas Helland]

Darn it. There appears to be a functional change with patch 14.
My changes where meant to make no functional change,
so something is fishy. An example from the public shader-db:

cycles HURT:   ./shaders/tesseract/205.shader_test VS vec4:      54 ->
100 (85.19%)

I'll see if I can find some time to debug this during the week.
If anyone immediately sees the issue, please let me know.

I guess I should write some make-check tests for the new
hash table, as I suspect that that is where the issue is.

- Thomas
2017-01-01 20:41 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
> Oh, and an important disclaimer.
> I have not ran this through picking, nor have I done a complete
> run of shader-db for performance comparisons on more realistic workloads.
> I'll see what time I can find this evening, or some time tomorrow.
>
>
> On Jan 1, 2017 19:38, "Thomas Helland" <thomashelland90 at gmail.com> wrote:
>
> 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.
>
> https://bugs.freedesktop.org/show_bug.cgi?id=94477
>
> 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
>
>