[Mesa-dev] [PATCH 05/11] glsl: Replace the linear search in get_intrinsic_opcode with a radix trie
Ian Romanick
idr at freedesktop.org
Thu Jul 7 17:36:56 UTC 2016
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 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.
> 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
>
More information about the mesa-dev
mailing list