[Mesa-dev] [PATCH 05/11] glsl: Replace the linear search in get_intrinsic_opcode with a radix trie
Jason Ekstrand
jason at jlekstrand.net
Fri Jul 8 00:02:31 UTC 2016
On Thu, Jul 7, 2016 at 10:36 AM, Ian Romanick <idr at freedesktop.org> wrote:
> On 07/07/2016 04:15 AM, Jason Ekstrand wrote:
> > I can't help but think that we keep solving this problem... We have a
> > low-collision hash table for vkGetProcAddress, something for
> > glxGetProcAddress and eglGetProcAddress (hopefully the same?) and now
> > this. Can we pick a method, make it a little Python helper, and use it
> > everywhere?
> >
> > Not being critical; this is probably a fine solution for compile-time
> > string -> int mappings and possibly the best to date. It just seems
> > like kind of a big hammer especially if glsl_to_nir is its only user.
>
> Well... I went to this extreme partially for fun. :) I think there are
> other places that could use this, and I mentioned one in the intro
> message. I haven't gone looking through the code to find others, but I
> suspect there may be. That might even be a cool newbie project.
>
I wondered about that... This kind of smelled like show-off code. :-) Not
that there's anything wrong with that...
> I don't think this particular solution is useful for GetProcAddress
> kinds of things because (by the end) it depends on callers only ever
> querying things that are in the set. The other problem with
> glXGetProcAddress and eglGetProcAddress is the driver can add new things
> to the set. I'm not sure if anything can add functions to the set used
> by vkGetProcAddress.
>
Right. I hadn't considered implementations adding things to the list. For
vkGetProcAddress, we don't do anything dynamic with it yet. That may
change in the future. I don't know.
>
> > On Jul 5, 2016 5:46 PM, "Ian Romanick" <idr at freedesktop.org
> > <mailto:idr at freedesktop.org>> wrote:
> >
> > From: Ian Romanick <ian.d.romanick at intel.com
> > <mailto:ian.d.romanick at intel.com>>
> >
> > If there is a way to do this cleanly in mako, I'm very interested to
> > hear about it.
> >
> > text data bss dec hex filename
> > 7529003 273096 28584 7830683 777c9b /tmp/i965_dri-64bit-before.so
> > 7528883 273096 28584 7830563 777c23 /tmp/i965_dri-64bit-after.so
> >
> > Signed-off-by: Ian Romanick <ian.d.romanick at intel.com
> > <mailto:ian.d.romanick at intel.com>>
> > ---
> > src/compiler/glsl/nir_intrinsic_map.py | 131
> > ++++++++++++++++++++++++++++++---
> > 1 file changed, 119 insertions(+), 12 deletions(-)
> >
> > diff --git a/src/compiler/glsl/nir_intrinsic_map.py
> > b/src/compiler/glsl/nir_intrinsic_map.py
> > index 7f13c6c..5962d4b 100644
> > --- a/src/compiler/glsl/nir_intrinsic_map.py
> > +++ b/src/compiler/glsl/nir_intrinsic_map.py
> > @@ -66,6 +66,123 @@ intrinsics = [("__intrinsic_atomic_read",
> > ("nir_intrinsic_atomic_counter_read_va
> > ("__intrinsic_atomic_exchange_shared",
> > ("nir_intrinsic_shared_atomic_exchange", None)),
> > ("__intrinsic_atomic_comp_swap_shared",
> > ("nir_intrinsic_shared_atomic_comp_swap", None))]
> >
> > +def remove_prefix(table, prefix_length):
> > + """Strip prefix_length characters off the name of each entry in
> > table."""
> > +
> > + return [(s[prefix_length:], d) for (s, d) in table]
> > +
> > +
> > +def generate_trie(table):
> > + """table is a list of (string, data) tuples. It is assumed to
> > be sorted by
> > + string.
> > +
> > + A radix trie (or compact prefix trie) is recursively generated
> > from the
> > + list of names. Names are paritioned into groups that have at
> least
> > + prefix_thresh (tunable parameter) common prefix characters.
> > Each of these
> > + groups becomes the branches at the current level of the tree.
> The
> > + matching prefix characters from each group is removed, and the
> > group is
> > + recursively operated on in the same fashion.
> > +
> > + The recursion terminates when no groups can be formed with at
> least
> > + prefix_thresh matching characters.
> > +
> > + Each node in the trie is a 3-element tuple:
> > +
> > + (prefix_string, [child_nodes], client_data)
> > +
> > + One of [child_nodes] or client_data will be None.
> > +
> > + See https://en.wikipedia.org/wiki/Radix_tree for more
> > background details
> > + on the data structure.
> > +
> > + """
> > +
> > + # Threshold for considering two strings to have the same prefix.
> > + prefix_thresh = 1
> > +
> > + if len(table) == 1 and table[0][0] == "":
> > + return [("", None, table[0][1])]
> > +
> > + trie_level = []
> > +
> > + (s, d) = table[0]
> > + candidates = [(s, d)]
> > + base = s
> > + prefix_length = len(s)
> > +
> > + for (s, d) in table[1:]:
> > + if s[:prefix_thresh] == base[:prefix_thresh]:
> > + candidates.append((s, d))
> > +
> > + l = len(s[:([x[0]==x[1] for x in zip(s,
> > base)]+[0]).index(0)])
> > + if l < prefix_length:
> > + prefix_length = l
> > + else:
> > + trie_level.append((base[:prefix_length],
> > generate_trie(remove_prefix(candidates, prefix_length)), None))
> > +
> > + candidates = [(s, d)]
> > + base = s
> > + prefix_length = len(s)
> > +
> > + trie_level.append((base[:prefix_length],
> > generate_trie(remove_prefix(candidates, prefix_length)), None))
> > +
> > + return trie_level
> > +
> > +
> > +def emit_trie_leaf(indent, d):
> > + if d[1] is None:
> > + return "{}return {};\n".format(indent, d[0])
> > + else:
> > + c_code = "{}int_op = {};\n".format(indent, d[0])
> > + c_code += "{}uint_op = {};\n".format(indent, d[1])
> > + return c_code
> > +
> > +
> > +def trie_as_C_code(trie, indent=" ",
> prefix_string="__intrinsic_"):
> > + conditional = "if"
> > +
> > + c_code = ""
> > + for (s, t, d) in trie:
> > + if d is not None:
> > + c_code += "{}{} (name[0] == '\\0')
> > {{\n".format(indent, conditional)
> > + c_code += "{} /* {} */\n".format(indent,
> prefix_string)
> > + c_code += emit_trie_leaf(indent + " ", d);
> > +
> > + else:
> > + # Before emitting the string comparison, check to see
> > of the
> > + # subtree has a single element with an empty string.
> > In that
> > + # case, use strcmp() instead of strncmp() and don't
> > advance the
> > + # name pointer.
> > +
> > + if len(t) == 1 and t[0][2] is not None:
> > + if s == "":
> > + c_code += "{}{} (name[0] == '\\0')
> > {{\n".format(indent, conditional, s)
> > + else:
> > + c_code += "{}{} (strcmp(name, \"{}\") == 0)
> > {{\n".format(indent, conditional, s)
> > +
> > + c_code += "{} /* {} */\n".format(indent,
> > prefix_string + s)
> > + c_code += emit_trie_leaf(indent + " ", t[0][2]);
> > + else:
> > + c_code += "{}{} (strncmp(name, \"{}\", {}) == 0)
> > {{\n".format(indent, conditional, s, len(s))
> > + c_code += "{} name += {};\n\n".format(indent,
> len(s))
> > +
> > + c_code += trie_as_C_code(t, indent + " ",
> > prefix_string + s)
> > +
> > + conditional = "} else if"
> > +
> > + c_code += "{}}} else\n".format(indent)
> > + c_code += "{} unreachable(\"Invalid intrinsic
> > name\");\n\n".format(indent)
> > + return c_code
> > +
> > +
> > +intrinsics.sort(key=lambda tup: tup[0])
> > +
> > +trimmed_name_intrinsics = []
> > +for (s, d) in intrinsics:
> > + trimmed_name_intrinsics.append((s[12:], d))
> > +
> > +trie_search = trie_as_C_code(generate_trie(trimmed_name_intrinsics))
> > +
> > template = """
> > namespace _glsl_to_nir {
> >
> > @@ -80,17 +197,7 @@ get_intrinsic_opcode(const char *name, const
> > ir_dereference *return_deref)
> > nir_intrinsic_op int_op;
> > nir_intrinsic_op uint_op;
> >
> > - % for (name, ops) in intrinsics:
> > - if (strcmp(name, "${name[12:]}") == 0) {
> > - % if ops[1] is None:
> > - return ${ops[0]};
> > - % else:
> > - int_op = ${ops[0]};
> > - uint_op = ${ops[1]};
> > - % endif
> > - } else
> > - % endfor
> > - unreachable("Unknown intrinsic name");
> > +${trie_search}
> >
> > assert(return_deref);
> > if (return_deref->type == glsl_type::int_type)
> > @@ -103,4 +210,4 @@ get_intrinsic_opcode(const char *name, const
> > ir_dereference *return_deref)
> > }
> > """
> >
> > -print(Template(template).render(intrinsics=intrinsics))
> > +print(Template(template).render(trie_search=trie_search))
> > --
> > 2.5.5
> >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev at lists.freedesktop.org <mailto:
> mesa-dev at lists.freedesktop.org>
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20160707/4352b520/attachment-0001.html>
More information about the mesa-dev
mailing list