[Mesa-dev] [RFC 1/2] glsl: Use hash tables for opt_constant_propagation() acp sets.

[Rhys Kidd]

On 7 October 2015 at 04:00, Kenneth Graunke <kenneth at whitecape.org> wrote:

> 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.
>

Hello Kenneth,

Thank you for your feedback. I'll review and then resubmit a v2 patchset
addressing these comments.

Regards,
Rhys
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20151007/75c3d997/attachment.html>