<div dir="ltr"><div>On wtorek, 18 października 2016 00:07:18 CEST Jan Ziak wrote:</div><div>> This patch replaces the ir_variable_refcount_entry's linked-list</div><div>> with an array-list.</div><div>> </div><div>> The array-list has local storage which does not require ANY additional</div><div>> allocations if the list has small number of elements. The size of this</div><div>> storage is configurable for each variable.</div><div>> </div><div>> Benchmark results for "./run -1 shaders" from shader-db[1]:</div><div>> </div><div>> - The total number of executed instructions goes down from 64.184 to 63.797</div><div>>   giga-instructions when Mesa is compiled with "gcc -O0 ..."</div><div><br></div><div>Hi,</div><div><br></div><div>A total number of instructions in -O0 is not a good indicator of whether this change is beneficial from performance POV.</div><div>You should check it with -O2 or whatever is the default in mesa release builds.</div><div><br></div><div>> - In the call tree starting at function do_dead_code():</div><div>>   - the number of calls to malloc() is reduced by about 10%</div><div>>   - the number of calls to free() is reduced by about 30%</div><div><br></div><div>These are certainly a win.</div><div><br></div><div>> </div><div>> [1] git://<a href="http://anongit.freedesktop.org/mesa/shader-db">anongit.freedesktop.org/mesa/shader-db</a></div><div>> </div><div>> Signed-off-by: Jan Ziak (<a href="http://atom-symbol.net">http://atom-symbol.net</a>) <<a href="mailto:0xe2.0x9a.0x9b@gmail.com">0xe2.0x9a.0x9b@gmail.com</a>></div><div>> ---</div><div>>  src/compiler/glsl/ir_variable_refcount.cpp |  14 +--</div><div>>  src/compiler/glsl/ir_variable_refcount.h   |   8 +-</div><div>>  src/compiler/glsl/opt_dead_code.cpp        |  19 ++--</div><div>>  src/util/fast_list.h                       | 167 +++++++++++++++++++++++++++++</div><div>>  4 files changed, 176 insertions(+), 32 deletions(-)</div><div>> </div><div>> diff --git a/src/compiler/glsl/ir_variable_refcount.cpp b/src/compiler/glsl/ir_variable_refcount.cpp</div><div>> index 8306be1..94d6edc 100644</div><div>> --- a/src/compiler/glsl/ir_variable_refcount.cpp</div><div>> +++ b/src/compiler/glsl/ir_variable_refcount.cpp</div><div>> @@ -46,15 +46,6 @@ static void</div><div>>  free_entry(struct hash_entry *entry)</div><div>>  {</div><div>>     ir_variable_refcount_entry *ivre = (ir_variable_refcount_entry *) entry->data;</div><div>> -</div><div>> -   /* Free assignment list */</div><div>> -   exec_node *n;</div><div>> -   while ((n = ivre->assign_list.pop_head()) != NULL) {</div><div>> -      struct assignment_entry *assignment_entry =</div><div>> -         exec_node_data(struct assignment_entry, n, link);</div><div>> -      free(assignment_entry);</div><div>> -   }</div><div>> -</div><div>>     delete ivre;</div><div>>  }</div><div>>  </div><div>> @@ -142,10 +133,7 @@ ir_variable_refcount_visitor::visit_leave(ir_assignment *ir)</div><div>>         */</div><div>>        assert(entry->referenced_count >= entry->assigned_count);</div><div>>        if (entry->referenced_count == entry->assigned_count) {</div><div>> -         struct assignment_entry *assignment_entry =</div><div>> -            (struct assignment_entry *)calloc(1, sizeof(*assignment_entry));</div><div>> -         assignment_entry->assign = ir;</div><div>> -         entry->assign_list.push_head(&assignment_entry->link);</div><div>> +         entry->assign_list.add(ir);</div><div>>        }</div><div>>     }</div><div>>  </div><div>> diff --git a/src/compiler/glsl/ir_variable_refcount.h b/src/compiler/glsl/ir_variable_refcount.h</div><div>> index 08a11c0..c3ec5fe 100644</div><div>> --- a/src/compiler/glsl/ir_variable_refcount.h</div><div>> +++ b/src/compiler/glsl/ir_variable_refcount.h</div><div>> @@ -32,11 +32,7 @@</div><div>>  #include "ir.h"</div><div>>  #include "ir_visitor.h"</div><div>>  #include "compiler/glsl_types.h"</div><div>> -</div><div>> -struct assignment_entry {</div><div>> -   exec_node link;</div><div>> -   ir_assignment *assign;</div><div>> -};</div><div>> +#include "util/fast_list.h"</div><div>>  </div><div>>  class ir_variable_refcount_entry</div><div>>  {</div><div>> @@ -50,7 +46,7 @@ public:</div><div>>      * This is intended to be used for dead code optimisation and may</div><div>>      * not be a complete list.</div><div>>      */</div><div>> -   exec_list assign_list;</div><div>> +   arraylist<ir_assignment*,4> assign_list;</div><div>>  </div><div>>     /** Number of times the variable is referenced, including assignments. */</div><div>>     unsigned referenced_count;</div><div>> diff --git a/src/compiler/glsl/opt_dead_code.cpp b/src/compiler/glsl/opt_dead_code.cpp</div><div>> index 75e668a..06e8c3d 100644</div><div>> --- a/src/compiler/glsl/opt_dead_code.cpp</div><div>> +++ b/src/compiler/glsl/opt_dead_code.cpp</div><div>> @@ -52,7 +52,7 @@ do_dead_code(exec_list *instructions, bool uniform_locations_assigned)</div><div>>  </div><div>>     struct hash_entry *e;</div><div>>     hash_table_foreach(<a href="http://v.ht">v.ht</a>, e) {</div><div>> -      ir_variable_refcount_entry *entry = (ir_variable_refcount_entry *)e->data;</div><div>> +      ir_variable_refcount_entry *const entry = (ir_variable_refcount_entry *)e->data;</div><div>>  </div><div>>        /* Since each assignment is a reference, the refereneced count must be</div><div>>         * greater than or equal to the assignment count.  If they are equal,</div><div>> @@ -89,7 +89,7 @@ do_dead_code(exec_list *instructions, bool uniform_locations_assigned)</div><div>>        if (entry->var->data.always_active_io)</div><div>>           continue;</div><div>>  </div><div>> -      if (!entry->assign_list.is_empty()) {</div><div>> +      if (!entry->assign_list.empty()) {</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">   </span> /* Remove all the dead assignments to the variable we found.</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">   </span>  * Don't do so if it's a shader or function output, though.</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">   </span>  */</div><div>> @@ -98,26 +98,19 @@ do_dead_code(exec_list *instructions, bool uniform_locations_assigned)</div><div>>               entry->var->data.mode != ir_var_shader_out &&</div><div>>               entry->var->data.mode != ir_var_shader_storage) {</div><div>>  </div><div>> -            while (!entry->assign_list.is_empty()) {</div><div>> -               struct assignment_entry *assignment_entry =</div><div>> -                  exec_node_data(struct assignment_entry,</div><div>> -                                 entry->assign_list.get_head_raw(), link);</div><div>> -</div><div>> -<span class="gmail-Apple-tab-span" style="white-space:pre">      </span>       assignment_entry->assign->remove();</div><div>> -</div><div>> +            for(ir_assignment *assign : entry->assign_list) {</div><div>> +<span class="gmail-Apple-tab-span" style="white-space:pre">      </span>       assign->remove();</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">  </span>       if (debug) {</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">  </span>          printf("Removed assignment to %s@%p\n",</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">                </span>         entry->var->name, (void *) entry->var);</div><div>>                 }</div><div>> -</div><div>> -               assignment_entry->link.remove();</div><div>> -               free(assignment_entry);</div><div>>              }</div><div>> +            entry->assign_list.clear();</div><div>>              progress = true;</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">   </span> }</div><div>>        }</div><div>>  </div><div>> -      if (entry->assign_list.is_empty()) {</div><div>> +      if (entry->assign_list.empty()) {</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre"> </span> /* If there are no assignments or references to the variable left,</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">     </span>  * then we can remove its declaration.</div><div>>  <span class="gmail-Apple-tab-span" style="white-space:pre">        </span>  */</div><div>> diff --git a/src/util/fast_list.h b/src/util/fast_list.h</div><div>> new file mode 100644</div><div>> index 0000000..4abd965</div><div>> --- /dev/null</div><div>> +++ b/src/util/fast_list.h</div><div>> @@ -0,0 +1,167 @@</div><div>> +/*</div><div>> + * Copyright Â© 2016 Jan Ziak</div><div>> + *</div><div>> + * Permission is hereby granted, free of charge, to any person obtaining a</div><div>> + * copy of this software and associated documentation files (the "Software"),</div><div>> + * to deal in the Software without restriction, including without limitation</div><div>> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,</div><div>> + * and/or sell copies of the Software, and to permit persons to whom the</div><div>> + * Software is furnished to do so, subject to the following conditions:</div><div>> + *</div><div>> + * The above copyright notice and this permission notice (including the next</div><div>> + * paragraph) shall be included in all copies or substantial portions of the</div><div>> + * Software.</div><div>> + *</div><div>> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR</div><div>> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,</div><div>> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL</div><div>> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER</div><div>> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING</div><div>> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS</div><div>> + * IN THE SOFTWARE.</div><div>> + *</div><div>> + * Authors:</div><div>> + *    Jan Ziak (<a href="http://atom-symbol.net">http://atom-symbol.net</a>) <<a href="mailto:0xe2.0x9x.0a9b@gmail.com">0xe2.0x9x.0a9b@gmail.com</a>></div><div>> + */</div><div>> +</div><div>> +/**</div><div>> + * @file fast_list.h</div><div>> + *</div><div>> + * High-performance C++ list implementation.</div><div>> + */</div><div>> +</div><div>> +#ifndef _UTIL_FAST_LIST_H</div><div>> +#define _UTIL_FAST_LIST_H</div><div>> +</div><div>> +#include <new></div><div>> +#include <stdlib.h></div><div>> +#include <string.h></div><div>> +</div><div>> +/**</div><div>> + * A high-performance array list.</div><div><br></div><div>Please rename it. Its not a list since it doesn't fullfil list requirement (O(1) insertion, iterators are not invalidated on insertion or removal, etc...).</div><div><br></div><div>> + *</div><div>> + * The list doesn't support elements whose behavior depends on the memory address of the element.</div><div>> + *</div><div>> + * @param T  List element type.</div><div>> + *</div><div>> + * @param N  The number of statically allocated elements to achieve the highest overall performance.</div><div>> + *           N is typically 0, 2, 4 or 8 depending on the runtime usage pattern of a particular list</div><div>> + *           variable in the source code.</div><div>> + */</div><div>> +template<typename T, size_t N></div><div>> +struct arraylist</div><div>> +{</div><div>> +   size_t len;  // Length</div><div>> +   size_t cap;  // Capacity (size of memory allocated to 'elem')</div><div>> +   T *elem;     // List elements</div><div><br></div><div>elem data member is not necessary. You can derive this information from len.</div><div><br></div><div>> +   uint8_t local[N*sizeof(T)];  // Fast local preallocated storage for lists with length 0..N</div><div><br></div><div>With current design minimum number of elements in internal storage cannot be 0 - zero-sized array are not supported in C++</div><div>I suggest increasing the minimum to 1, as it will simplify code (a couple of conditionals can be removed).</div><div><br></div><div>Also you should use std::aligned_storage to get properly aligned buffer.</div><div><br></div><div>> +</div><div>> +   arraylist() {</div><div>> +      len = 0;</div><div>> +      cap = N;</div><div>> +      elem = (N ? (T*)local : NULL);</div><div>> +   }</div><div>> +</div><div>> +   ~arraylist() {</div><div>> +      if(!__has_trivial_destructor(T)) {</div><div><br></div><div>__has_trivial_destructor is gcc specific, use std::is_trivially_destructible<T></div><div><br></div><div>> +         for(size_t i=0; i<len; i++) {</div><div>> +            elem[i].~T();</div><div>> +         }</div><div>> +      }</div><div>> +      if((N && elem != (T*)local) && elem) {</div><div>> +         free(elem);</div><div>> +      }</div><div>> +   }</div><div>> +</div><div>> +   arraylist(const arraylist<T,N> &a) = delete;</div><div>> +   void operator=(const arraylist<T,N> &a) = delete;</div><div>> +</div><div>> +   bool empty() const {</div><div>> +      return len==0;</div><div>> +   }</div><div>> +</div><div>> +   void clear() {</div><div>> +      if(!__has_trivial_destructor(T)) {</div><div>> +         for(size_t i=0; i<len; i++) {</div><div>> +            elem[i].~T();</div><div>> +         }</div><div>> +      }</div><div>> +      len = 0;</div><div>> +   }</div><div>> +</div><div>> +   arraylist<T,N>& add(const T &e) {</div><div>> +      if(len == cap) {</div><div>> +         enlarge1();</div><div>> +      }</div><div>> +      new (&elem[len++]) T(e);</div><div>> +      return *this;</div><div>> +   }</div><div><br></div><div>Why return *this? I see no use for call chaining of add().</div><div><br></div><div>> +</div><div>> +   T& operator[](size_t i) { return elem[i]; }</div><div>> +   const T& operator[](size_t i) const { return elem[i]; }</div><div>> +</div><div>> +   /*</div><div>> +    * C++ iterators:</div><div>> +    */</div><div>> +</div><div>> +   struct const_iterator_t {</div><div>> +      const T *const elem;</div><div>> +      size_t i;</div><div>> +      const_iterator_t(const T *_elem, size_t _i) : elem(_elem), i(_i) {}</div><div>> +      const T& operator*() const { return elem[i]; }</div><div>> +      void operator++() { i++; }</div><div>> +      bool operator!=(const const_iterator_t &b) const { return i < b.i; }</div><div><br></div><div>Shouldn't this be 'return i != b.i'?</div><div>Same for iterator_t.</div><div><br></div><div>> +   };</div><div>> +   struct iterator_t {</div><div>> +      T *const elem;</div><div>> +      size_t i;</div><div>> +      iterator_t(T *_elem, size_t _i) : elem(_elem), i(_i) {}</div><div>> +      T& operator*() const { return elem[i]; }</div><div>> +      void operator++() { i++; }</div><div>> +      bool operator!=(const iterator_t &b) const { return i < b.i; }</div><div>> +   };</div><div>> +</div><div>> +   const_iterator_t const_begin() const { return const_iterator_t(elem, 0); }</div><div>> +   const_iterator_t const_end() const { return const_iterator_t(elem, len); }</div><div>> +</div><div>> +   const_iterator_t begin() const { return const_iterator_t(elem, 0); }</div><div>> +   const_iterator_t end() const { return const_iterator_t(elem, len); }</div><div>> +</div><div>> +   iterator_t begin() { return iterator_t(elem, 0); }</div><div>> +   iterator_t end() { return iterator_t(elem, len); }</div><div>> +</div><div>> +   /*</div><div>> +    * Methods for std::vector<T> compatibility:</div><div>> +    */</div><div>> +</div><div>> +   arraylist<T,N>& push_back(const T &e) { return add(e); }</div><div><br></div><div>std::vector<T>::push_back return type is void</div><div><br></div><div>> +</div><div>> +private:</div><div>> +   void enlarge1() {</div><div>> +      if(N) {</div><div>> +         cap *= 2;</div><div>> +         if(elem == (T*)local) {</div><div>> +            elem = (T*)malloc(cap*sizeof(T));</div><div>> +            if(!elem) {</div><div>> +               abort();</div><div>> +            }</div><div>> +            memcpy(elem, local, len*sizeof(T));</div><div><br></div><div>This works only for trivially copyable types. If that was intentional, then please add a comment at the top,</div><div>and a proper static_assert so it doesn't blow up in someone's face later.</div><div><br></div><div>PS. Please keep my e-mail address in a loop since I'm not subscribed to this list.</div><div><br></div><div>Regards,</div><div>Maciej</div><div><br></div><div>> +         }</div><div>> +         else {</div><div>> +            elem = (T*)realloc(elem, cap*sizeof(T));</div><div>> +            if(!elem) {</div><div>> +               abort();</div><div>> +            }</div><div>> +         }</div><div>> +      }</div><div>> +      else {</div><div>> +         cap = (cap ? 2*cap : 4);</div><div>> +         elem = (T*)realloc(elem, cap*sizeof(T));</div><div>> +         if(!elem) {</div><div>> +            abort();</div><div>> +         }</div><div>> +      }</div><div>> +   }</div><div>> +};</div><div>> +</div><div>> +#endif /* _UTIL_FAST_LIST_H */</div><div>> \ No newline at end of file</div><div>> </div><div><br></div></div>