18. okt. 2016 00.07 skrev "Jan Ziak" <<a href="mailto:0xe2.0x9a.0x9b@gmail.com">0xe2.0x9a.0x9b@gmail.com</a>>: > > This patch replaces the ir_variable_refcount_entry's linked-list > with an array-list. > > The array-list has local storage which does not require ANY additional > allocations if the list has small number of elements. The size of this > storage is configurable for each variable. > > Benchmark results for "./run -1 shaders" from shader-db[1]: > > - The total number of executed instructions goes down from 64.184 to 63.797 > Â giga-instructions when Mesa is compiled with "gcc -O0 ..." > - In the call tree starting at function do_dead_code(): > Â - the number of calls to malloc() is reduced by about 10% > Â - the number of calls to free() is reduced by about 30% > > [1] git://<a href="http://anongit.freedesktop.org/mesa/shader-db">anongit.freedesktop.org/mesa/shader-db</a> Nice find. I would not be surprised if there are more cases of inappropriate data structures being used, causing overhead. I can't quite tell, as Gmail tends to mangle whitespace stuff, but it looks like there might be some style issues with not everything following the three-space indent, no tabs policy that mesa tries to stick to. On the subject of this patch, some thoughts that came to mind: I think it would be preferred if the implementation was in C. Using this in NIR, which tries to be C only, might be a possibility? I also seem to recall that I reviewed some patches that Jason wrote back a good while ago for NIR that implemented a dynamically resizing array of sorts that might be of interest. Just some random thoughts. -Thomas > > 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>> > --- > Â src/compiler/glsl/ir_variable_refcount.cpp |Â 14 +-- > Â src/compiler/glsl/ir_variable_refcount.hÂ Â |Â Â 8 +- > Â src/compiler/glsl/opt_dead_code.cppÂ Â Â Â |Â 19 ++-- > Â src/util/fast_list.hÂ Â Â Â Â Â Â Â Â Â Â Â | 167 +++++++++++++++++++++++++++++ > Â 4 files changed, 176 insertions(+), 32 deletions(-) > > diff --git a/src/compiler/glsl/ir_variable_refcount.cpp b/src/compiler/glsl/ir_variable_refcount.cpp > index 8306be1..94d6edc 100644 > --- a/src/compiler/glsl/ir_variable_refcount.cpp > +++ b/src/compiler/glsl/ir_variable_refcount.cpp > @@ -46,15 +46,6 @@ static void > Â free_entry(struct hash_entry *entry) > Â { > Â Â ir_variable_refcount_entry *ivre = (ir_variable_refcount_entry *) entry->data; > - > -Â Â /* Free assignment list */ > -Â Â exec_node *n; > -Â Â while ((n = ivre->assign_list.pop_head()) != NULL) { > -Â Â Â struct assignment_entry *assignment_entry = > -Â Â Â Â Â exec_node_data(struct assignment_entry, n, link); > -Â Â Â free(assignment_entry); > -Â Â } > - > Â Â delete ivre; > Â } > > @@ -142,10 +133,7 @@ ir_variable_refcount_visitor::visit_leave(ir_assignment *ir) > Â Â Â Â */ > Â Â Â Â assert(entry->referenced_count >= entry->assigned_count); > Â Â Â Â if (entry->referenced_count == entry->assigned_count) { > -Â Â Â Â Â struct assignment_entry *assignment_entry = > -Â Â Â Â Â Â (struct assignment_entry *)calloc(1, sizeof(*assignment_entry)); > -Â Â Â Â Â assignment_entry->assign = ir; > -Â Â Â Â Â entry->assign_list.push_head(&assignment_entry->link); > +Â Â Â Â Â entry->assign_list.add(ir); > Â Â Â Â } > Â Â } > > diff --git a/src/compiler/glsl/ir_variable_refcount.h b/src/compiler/glsl/ir_variable_refcount.h > index 08a11c0..c3ec5fe 100644 > --- a/src/compiler/glsl/ir_variable_refcount.h > +++ b/src/compiler/glsl/ir_variable_refcount.h > @@ -32,11 +32,7 @@ > Â #include "ir.h" > Â #include "ir_visitor.h" > Â #include "compiler/glsl_types.h" > - > -struct assignment_entry { > -Â Â exec_node link; > -Â Â ir_assignment *assign; > -}; > +#include "util/fast_list.h" > > Â class ir_variable_refcount_entry > Â { > @@ -50,7 +46,7 @@ public: > Â Â Â * This is intended to be used for dead code optimisation and may > Â Â Â * not be a complete list. > Â Â Â */ > -Â Â exec_list assign_list; > +Â Â arraylist<ir_assignment*,4> assign_list; > > Â Â /** Number of times the variable is referenced, including assignments. */ > Â Â unsigned referenced_count; > diff --git a/src/compiler/glsl/opt_dead_code.cpp b/src/compiler/glsl/opt_dead_code.cpp > index 75e668a..06e8c3d 100644 > --- a/src/compiler/glsl/opt_dead_code.cpp > +++ b/src/compiler/glsl/opt_dead_code.cpp > @@ -52,7 +52,7 @@ do_dead_code(exec_list *instructions, bool uniform_locations_assigned) > > Â Â struct hash_entry *e; > Â Â hash_table_foreach(<a href="http://v.ht">v.ht</a>, e) { > -Â Â Â ir_variable_refcount_entry *entry = (ir_variable_refcount_entry *)e->data; > +Â Â Â ir_variable_refcount_entry *const entry = (ir_variable_refcount_entry *)e->data; > > Â Â Â Â /* Since each assignment is a reference, the refereneced count must be > Â Â Â Â * greater than or equal to the assignment count.Â If they are equal, > @@ -89,7 +89,7 @@ do_dead_code(exec_list *instructions, bool uniform_locations_assigned) > Â Â Â Â if (entry->var->data.always_active_io) > Â Â Â Â Â continue; > > -Â Â Â if (!entry->assign_list.is_empty()) { > +Â Â Â if (!entry->assign_list.empty()) { > Â Â Â Â Â /* Remove all the dead assignments to the variable we found. > Â Â Â Â Â * Don't do so if it's a shader or function output, though. > Â Â Â Â Â */ > @@ -98,26 +98,19 @@ do_dead_code(exec_list *instructions, bool uniform_locations_assigned) > Â Â Â Â Â Â Â entry->var->data.mode != ir_var_shader_out && > Â Â Â Â Â Â Â entry->var->data.mode != ir_var_shader_storage) { > > -Â Â Â Â Â Â while (!entry->assign_list.is_empty()) { > -Â Â Â Â Â Â Â Â struct assignment_entry *assignment_entry = > -Â Â Â Â Â Â Â Â Â exec_node_data(struct assignment_entry, > -Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â entry->assign_list.get_head_raw(), link); > - > -Â Â Â Â Â Â Â assignment_entry->assign->remove(); > - > +Â Â Â Â Â Â for(ir_assignment *assign : entry->assign_list) { > +Â Â Â Â Â Â Â assign->remove(); > Â Â Â Â Â Â Â Â if (debug) { > Â Â Â Â Â Â Â Â Â printf("Removed assignment to %s@%p\n", > Â Â Â Â Â Â Â Â Â Â Â Â Â entry->var->name, (void *) entry->var); > Â Â Â Â Â Â Â Â } > - > -Â Â Â Â Â Â Â Â assignment_entry->link.remove(); > -Â Â Â Â Â Â Â Â free(assignment_entry); > Â Â Â Â Â Â Â } > +Â Â Â Â Â Â entry->assign_list.clear(); > Â Â Â Â Â Â Â progress = true; > Â Â Â Â Â } > Â Â Â Â } > > -Â Â Â if (entry->assign_list.is_empty()) { > +Â Â Â if (entry->assign_list.empty()) { > Â Â Â Â Â /* If there are no assignments or references to the variable left, > Â Â Â Â Â * then we can remove its declaration. > Â Â Â Â Â */ > diff --git a/src/util/fast_list.h b/src/util/fast_list.h > new file mode 100644 > index 0000000..4abd965 > --- /dev/null > +++ b/src/util/fast_list.h > @@ -0,0 +1,167 @@ > +/* > + * Copyright Â© 2016 Jan Ziak > + * > + * Permission is hereby granted, free of charge, to any person obtaining a > + * copy of this software and associated documentation files (the "Software"), > + * to deal in the Software without restriction, including without limitation > + * the rights to use, copy, modify, merge, publish, distribute, sublicense, > + * and/or sell copies of the Software, and to permit persons to whom the > + * Software is furnished to do so, subject to the following conditions: > + * > + * The above copyright notice and this permission notice (including the next > + * paragraph) shall be included in all copies or substantial portions of the > + * Software. > + * > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR > + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, > + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.Â IN NO EVENT SHALL > + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER > + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING > + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS > + * IN THE SOFTWARE. > + * > + * Authors: > + *Â Â 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>> > + */ > + > +/** > + * @file fast_list.h > + * > + * High-performance C++ list implementation. > + */ > + > +#ifndef _UTIL_FAST_LIST_H > +#define _UTIL_FAST_LIST_H > + > +#include <new> > +#include <stdlib.h> > +#include <string.h> > + > +/** > + * A high-performance array list. > + * > + * The list doesn't support elements whose behavior depends on the memory address of the element. > + * > + * @param TÂ List element type. > + * > + * @param NÂ The number of statically allocated elements to achieve the highest overall performance. > + *Â Â Â Â Â Â N is typically 0, 2, 4 or 8 depending on the runtime usage pattern of a particular list > + *Â Â Â Â Â Â variable in the source code. > + */ > +template<typename T, size_t N> > +struct arraylist > +{ > +Â Â size_t len;Â // Length > +Â Â size_t cap;Â // Capacity (size of memory allocated to 'elem') > +Â Â T *elem;Â Â Â // List elements > +Â Â uint8_t local[N*sizeof(T)];Â // Fast local preallocated storage for lists with length 0..N > + > +Â Â arraylist() { > +Â Â Â len = 0; > +Â Â Â cap = N; > +Â Â Â elem = (N ? (T*)local : NULL); > +Â Â } > + > +Â Â ~arraylist() { > +Â Â Â if(!__has_trivial_destructor(T)) { > +Â Â Â Â Â for(size_t i=0; i<len; i++) { > +Â Â Â Â Â Â elem[i].~T(); > +Â Â Â Â Â } > +Â Â Â } > +Â Â Â if((N && elem != (T*)local) && elem) { > +Â Â Â Â Â free(elem); > +Â Â Â } > +Â Â } > + > +Â Â arraylist(const arraylist<T,N> &a) = delete; > +Â Â void operator=(const arraylist<T,N> &a) = delete; > + > +Â Â bool empty() const { > +Â Â Â return len==0; > +Â Â } > + > +Â Â void clear() { > +Â Â Â if(!__has_trivial_destructor(T)) { > +Â Â Â Â Â for(size_t i=0; i<len; i++) { > +Â Â Â Â Â Â elem[i].~T(); > +Â Â Â Â Â } > +Â Â Â } > +Â Â Â len = 0; > +Â Â } > + > +Â Â arraylist<T,N>& add(const T &e) { > +Â Â Â if(len == cap) { > +Â Â Â Â Â enlarge1(); > +Â Â Â } > +Â Â Â new (&elem[len++]) T(e); > +Â Â Â return *this; > +Â Â } > + > +Â Â T& operator[](size_t i) { return elem[i]; } > +Â Â const T& operator[](size_t i) const { return elem[i]; } > + > +Â Â /* > +Â Â * C++ iterators: > +Â Â */ > + > +Â Â struct const_iterator_t { > +Â Â Â const T *const elem; > +Â Â Â size_t i; > +Â Â Â const_iterator_t(const T *_elem, size_t _i) : elem(_elem), i(_i) {} > +Â Â Â const T& operator*() const { return elem[i]; } > +Â Â Â void operator++() { i++; } > +Â Â Â bool operator!=(const const_iterator_t &b) const { return i < b.i; } > +Â Â }; > +Â Â struct iterator_t { > +Â Â Â T *const elem; > +Â Â Â size_t i; > +Â Â Â iterator_t(T *_elem, size_t _i) : elem(_elem), i(_i) {} > +Â Â Â T& operator*() const { return elem[i]; } > +Â Â Â void operator++() { i++; } > +Â Â Â bool operator!=(const iterator_t &b) const { return i < b.i; } > +Â Â }; > + > +Â Â const_iterator_t const_begin() const { return const_iterator_t(elem, 0); } > +Â Â const_iterator_t const_end() const { return const_iterator_t(elem, len); } > + > +Â Â const_iterator_t begin() const { return const_iterator_t(elem, 0); } > +Â Â const_iterator_t end() const { return const_iterator_t(elem, len); } > + > +Â Â iterator_t begin() { return iterator_t(elem, 0); } > +Â Â iterator_t end() { return iterator_t(elem, len); } > + > +Â Â /* > +Â Â * Methods for std::vector<T> compatibility: > +Â Â */ > + > +Â Â arraylist<T,N>& push_back(const T &e) { return add(e); } > + > +private: > +Â Â void enlarge1() { > +Â Â Â if(N) { > +Â Â Â Â Â cap *= 2; > +Â Â Â Â Â if(elem == (T*)local) { > +Â Â Â Â Â Â elem = (T*)malloc(cap*sizeof(T)); > +Â Â Â Â Â Â if(!elem) { > +Â Â Â Â Â Â Â Â abort(); > +Â Â Â Â Â Â } > +Â Â Â Â Â Â memcpy(elem, local, len*sizeof(T)); > +Â Â Â Â Â } > +Â Â Â Â Â else { > +Â Â Â Â Â Â elem = (T*)realloc(elem, cap*sizeof(T)); > +Â Â Â Â Â Â if(!elem) { > +Â Â Â Â Â Â Â Â abort(); > +Â Â Â Â Â Â } > +Â Â Â Â Â } > +Â Â Â } > +Â Â Â else { > +Â Â Â Â Â cap = (cap ? 2*cap : 4); > +Â Â Â Â Â elem = (T*)realloc(elem, cap*sizeof(T)); > +Â Â Â Â Â if(!elem) { > +Â Â Â Â Â Â abort(); > +Â Â Â Â Â } > +Â Â Â } > +Â Â } > +}; > + > +#endif /* _UTIL_FAST_LIST_H */ > \ No newline at end of file > _______________________________________________ > mesa-dev mailing list > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> > <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a>