[Mesa-dev] [PATCH 05/11] glsl: Replace the linear search in get_intrinsic_opcode with a radix trie
Ian Romanick
idr at freedesktop.org
Fri Jul 8 01:47:48 UTC 2016
On 07/07/2016 04:03 PM, Dylan Baker wrote:
> 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])))
trie_search = trie_as_C_code(generate_trie(
[(s[12:], d) for s, d in sorted(intrinsics, key=lambda t: t[0])]))
Produces the same output as before. Thanks!
I've pushed v2 of this patch and patch 2 to my
ARB_shader_atomic_counter_ops-i965 tree.
>
> 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: 181 bytes
Desc: OpenPGP digital signature
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20160707/a1479ff8/attachment.sig>
More information about the mesa-dev
mailing list