[Mesa-dev] [PATCH 05/12] glsl: Replace the linear search in get_intrinsic_opcode with a radix trie

[Ian Romanick]

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

v2: Replace list.sort() with sorted() for a pretty dramatic code clean
up.  Suggested by Dylan.

Signed-off-by: Ian Romanick <ian.d.romanick at intel.com>
---
 src/compiler/glsl/nir_intrinsic_map.py | 126 +++++++++++++++++++++++++++++----
 1 file changed, 114 insertions(+), 12 deletions(-)

diff --git a/src/compiler/glsl/nir_intrinsic_map.py b/src/compiler/glsl/nir_intrinsic_map.py
index f6e9241..337f1e9 100644
--- a/src/compiler/glsl/nir_intrinsic_map.py
+++ b/src/compiler/glsl/nir_intrinsic_map.py
@@ -67,6 +67,115 @@ 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
+
+
 template = """
 namespace _glsl_to_nir {
 
@@ -81,17 +190,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)
@@ -105,4 +204,7 @@ get_intrinsic_opcode(const char *name, const ir_dereference *return_deref)
 """
 
 if __name__ == "__main__":
-    print(Template(template).render(intrinsics=intrinsics))
+    trie_search = trie_as_C_code(generate_trie(
+        [(s[12:], d) for s, d in sorted(intrinsics, key=lambda t: t[0])]))
+
+    print(Template(template).render(trie_search=trie_search))
-- 
2.5.5