[Mesa-dev] [PATCH 05/11] glsl: Replace the linear search in get_intrinsic_opcode with a radix trie
Dylan Baker
dylan at pnwbakers.com
Thu Jul 7 23:03:42 UTC 2016
Quoting Ian Romanick (2016-07-05 17:46:13)
> From: Ian Romanick <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>
> ---
> 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])
I would avoid using list.sort() here and use the sorted() iterator.
list.sort is useful when you need to walk the sorted list multiple
times, but is more expensive than using sorted(). I would implement
this something like (I didn't test this, it might not be quite right):
trie_search = trie_as_C_code(generate_trie(
(s[12:], d) for s, d in sorted(intrinsics, lambda t: t[0])))
You should also wrap this up in the if __name__ == "__main__" block like
the previous patch.
> +
> +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
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: signature
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20160707/f16f2359/attachment.sig>
More information about the mesa-dev
mailing list