[Mesa-dev] [RFC 1/2] glsl: Use hash tables for opt_constant_propagation() acp sets.
Kenneth Graunke
kenneth at whitecape.org
Tue Oct 6 10:00:54 PDT 2015
On Sunday, September 20, 2015 07:54:56 PM Rhys Kidd wrote:
> ---
> src/glsl/opt_constant_propagation.cpp | 63 +++++++++++++++++++++--------------
> 1 file changed, 38 insertions(+), 25 deletions(-)
Hi Rhys!
Thanks for looking into this :) A couple of comments...
Now that acp_entry isn't used in any lists, you can make it stop
inheriting from exec_node, which will remove the prev/next pointers.
Do you have any data on whether this speeds up compile times at all?
I was just running 'time glslparsertest' (or 'time shader_runner') on
the shader from [ https://bugs.freedesktop.org/show_bug.cgi?id=91857 ].
It should be pretty easy to measure (earlier patches shaved whole
seconds off the compile time); it'd be nice to include that in the
commit message.
> diff --git a/src/glsl/opt_constant_propagation.cpp b/src/glsl/opt_constant_propagation.cpp
> index 184aaa1..b6cbf61 100644
> --- a/src/glsl/opt_constant_propagation.cpp
> +++ b/src/glsl/opt_constant_propagation.cpp
> @@ -95,7 +95,8 @@ public:
> progress = false;
> killed_all = false;
> mem_ctx = ralloc_context(0);
> - this->acp = new(mem_ctx) exec_list;
> + this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> + _mesa_key_pointer_equal);
> this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> _mesa_key_pointer_equal);
> }
> @@ -118,8 +119,8 @@ public:
> void handle_if_block(exec_list *instructions);
> void handle_rvalue(ir_rvalue **rvalue);
>
> - /** List of acp_entry: The available constants to propagate */
> - exec_list *acp;
> + /** Hash table of acp_entry: The available constants to propagate */
> + hash_table *acp;
>
> /**
> * List of kill_entry: The masks of variables whose values were
> @@ -206,11 +207,13 @@ ir_constant_propagation_visitor::constant_propagation(ir_rvalue **rvalue) {
> channel = i;
> }
>
> - foreach_in_list(acp_entry, entry, this->acp) {
> - if (entry->var == deref->var && entry->write_mask & (1 << channel)) {
> + hash_entry *acp_hash_entry;
> + hash_table_foreach(this->acp, acp_hash_entry) {
> + acp_entry *entry = (acp_entry *) acp_hash_entry->data;
> + if (entry->var == deref->var && entry->write_mask & (1 << channel)) {
> found = entry;
> break;
> - }
> + }
This seems a bit strange...here, we're still walking over the entire
hash table, manually checking if each entry's var matches. In fact, I
don't see any calls to _mesa_hash_table_search in this patch.
The point of using a hash table is that it provides constant-time / O(1)
lookups of data, compared to a linked list's linear-time / O(n) lookups.
Generally, hash tables have a bit more overhead than a linked list...so
if we're not gaining constant time lookup, I'm not sure it's worth it.
Perhaps we need to include the write mask in the key somehow? Or, hash
on variable, but instead of a single entry, get a list of entries back?
> }
>
> if (!found)
> @@ -264,11 +267,12 @@ ir_constant_propagation_visitor::visit_enter(ir_function_signature *ir)
> * block. Any instructions at global scope will be shuffled into
> * main() at link time, so they're irrelevant to us.
> */
> - exec_list *orig_acp = this->acp;
> + hash_table *orig_acp = this->acp;
> hash_table *orig_kills = this->kills;
> bool orig_killed_all = this->killed_all;
>
> - this->acp = new(mem_ctx) exec_list;
> + this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> + _mesa_key_pointer_equal);
> this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> _mesa_key_pointer_equal);
> this->killed_all = false;
> @@ -345,7 +349,8 @@ ir_constant_propagation_visitor::visit_enter(ir_call *ir)
> /* Since we're unlinked, we don't (necssarily) know the side effects of
> * this call. So kill all copies.
> */
> - acp->make_empty();
> + acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> + _mesa_key_pointer_equal);
> this->killed_all = true;
>
> return visit_continue_with_parent;
> @@ -354,24 +359,29 @@ ir_constant_propagation_visitor::visit_enter(ir_call *ir)
> void
> ir_constant_propagation_visitor::handle_if_block(exec_list *instructions)
> {
> - exec_list *orig_acp = this->acp;
> + hash_table *orig_acp = this->acp;
> hash_table *orig_kills = this->kills;
> bool orig_killed_all = this->killed_all;
>
> - this->acp = new(mem_ctx) exec_list;
> + this->acp = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> + _mesa_key_pointer_equal);
> this->kills = _mesa_hash_table_create(mem_ctx, _mesa_hash_pointer,
> _mesa_key_pointer_equal);
> this->killed_all = false;
>
> /* Populate the initial acp with a constant of the original */
> - foreach_in_list(acp_entry, a, orig_acp) {
> - this->acp->push_tail(new(this->mem_ctx) acp_entry(a));
> + hash_entry *htk;
> + hash_table_foreach(orig_acp, htk) {
> + acp_entry *a = (acp_entry *) htk->data;
> + _mesa_hash_table_insert(this->acp, a,
> + new(this->mem_ctx) acp_entry(a));
You might consider doing:
_mesa_hash_table_insert_pre_hashed(this->acp, htk->hash, a,
new(mem_ctx) acp_entry(a));
This avoids having to re-hash every entry in the table when creating a
new hash table. Since both tables use the same hash function, and the
same key, you may as well use the value you already have.
I do wonder if it would make sense to add a _mesa_hash_table_copy()
function that memcpy's the contents...since that would be even cheaper
still...but here you're actually inserting a new copy of acp_entry, so
I guess that wouldn't work.
We might be able to get away with not copying the ACP entry...one reason
for doing so was because it contained prev/next pointers, and so could
only be present in one linked list at a time. Now that we're using hash
tables, we don't have that restriction. However, it looks like kill()
actually modifies ACP entries, so it's probably easier to continue
copying them for now.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20151006/705fead6/attachment.sig>
More information about the mesa-dev
mailing list