[Mesa-dev] [PATCH 26/26] glsl: Add Bloom filter to get_static_name

[Ian Romanick]

From: Ian Romanick <ian.d.romanick at intel.com>

The use of the Bloom filter rejects the vast majority of strings that
are not in the table before expensive comparisons are performed.  This
Bloom filter uses two hashes.  One is explicit (calculate_hash in the
code), and the other is implicit.  The implicit hash is just the length
of the name, and the filter is the switch-statement in
get_static_name_do_not_call that rejects name with lengths that are not
in the table.

No change Valgrind massif results for a trimmed apitrace of dota2.

NOTE: This patch could probably get squashed into the previous patch.  I
kept it separate because I thought it would make things easier to
review.

Signed-off-by: Ian Romanick <ian.d.romanick at intel.com>
---
 src/glsl/common_variable_names.py | 113 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 112 insertions(+), 1 deletion(-)

diff --git a/src/glsl/common_variable_names.py b/src/glsl/common_variable_names.py
index 7435a12..ee5571c 100644
--- a/src/glsl/common_variable_names.py
+++ b/src/glsl/common_variable_names.py
@@ -119,6 +119,46 @@ name_really_is_not_in_static_names(const char *name)
 }
 #endif /* DEBUG */
 
+static uint32_t
+calculate_hash(const char *str)
+{
+    uint32_t hash = 5381;
+
+    while (*str != '\\0') {
+        hash = (hash * 33) + *str;
+        str++;
+    }
+
+    return hash;
+}
+
+/**
+ * Check the Bloom filter for the name
+ */
+static bool
+name_is_in_Bloom_filter(const char *name)
+{
+   static const uint32_t filter[${len(filter)}] = {
+    % for i in range(0,len(filter), 4):
+      ${"{:#010x}".format(filter[i+0])}, ${"{:#010x}".format(filter[i+1])}, ${"{:#010x}".format(filter[i+2])}, ${"{:#010x}".format(filter[i+3])},
+    % endfor
+   };
+
+   const uint32_t h = calculate_hash(name);
+
+   if (h < ${min(all_hash)})
+      return false;
+
+   if (h > ${max(all_hash)})
+      return false;
+
+   const unsigned bit = (h - ${min(all_hash)}) % ${len(filter) * 32};
+   const unsigned i = bit / 32;
+   const unsigned j = bit % 32;
+
+   return (filter[i] & (1U << j)) != 0;
+}
+
 /**
  * Search the static name table for the specified name
  *
@@ -129,6 +169,11 @@ name_really_is_not_in_static_names(const char *name)
 static const char *
 get_static_name_do_not_call(const char *name)
 {
+   /* Do the trivial rejection test before anything.
+    */
+   if (!name_is_in_Bloom_filter(name))
+      return NULL;
+
    const unsigned len = strlen(name);
    const ${index_type} *table = NULL;
    unsigned table_size = 0;
@@ -188,6 +233,14 @@ get_static_name(const char *name)
 }
 """
 
+def calculate_hash(str):
+    hash = 5381
+
+    for c in str:
+        hash = ((hash * 33) + ord(c)) & 0x0ffffffff
+
+    return hash
+
 common_names.sort()
 
 # Partiation the list of names into sublists of names with the same length
@@ -213,8 +266,66 @@ elif base < (1 << 16):
 else:
    index_type = "uint32_t"
 
+all_hash = []
+for name in common_names:
+   all_hash.append(calculate_hash(name))
+
+# Experimentally determined that 8,192 bits is sufficient for this dataset.
+# This was determined by:
+#
+# 1. Modify the generated code to log a message on entry to get_static_name.
+#
+# 2. Modify the generated code to log a message when name_is_in_Bloom_filter
+# returns true.
+#
+# 3. Modifiy the generated code to log a message each time a name is rejected
+# due to its length.  This is the 'default' case in the switch-statement.
+# This is an implicit hash that is part of the Bloom filter.
+#
+# 4. Modify the generated code to log a message each time a name has actually
+# been tested (using strcmp) and was not in the table.  This means logging at
+# the end of get_static_name_do_not_call and inside the switch-statement where
+# "lonely" names are handled.
+#
+# 5. Run a ton of shaders through (e.g., shader-db) and collect the output.
+# Count the number of times each message occurred.
+#
+# Two hash functions were tried.  The current one and Murmur2.  Exhaustive
+# testing over shader-db produced the following results.  There were a total
+# of 6,749,837 calls to get_static_name in each run.  The # in the column
+# header refers messages mentioned in the list above.
+#
+#    Bits          Current hash                       Murmur2
+#                #2 /     #3 /      #4           #2 /     #3 /     #4
+#     128   5249223 / 262597 / 4826172       763090 / 285531 / 317105
+#     256   4955982 / 162087 / 4633441       508512 / 152491 / 195567
+#     512    334736 / 111152 /   63130       381691 /  98277 / 122960
+#    1024    236521 /  43809 /   32258       326657 /  69346 /  96857
+#    2048    174275 /   1533 /   12288       258885 /  49537 /  48894
+#    4096    171153 /    341 /   10358       185632 /    682 /  24496
+#    8192    161649 /    264 /     931       163035 /    142 /   2439
+#   16384    160782 /      0 /     328       162764 /     15 /   2295
+#
+# Past 512 bits, the current hash was clearly superior to Murmur2.  8,192 bits
+# seems to be a sweet spot of a very small table size (1KiB) and a less than
+# 1% false-positive rate (931/161649).
+
+filter_bits = 8192
+m = min(all_hash)
+filter = []
+for i in range(0, filter_bits / 32):
+    filter.append(0)
+
+for h in all_hash:
+    idx = ((h - m) % filter_bits) / 32
+    bit = ((h - m) % filter_bits) % 32
+
+    filter[idx] = filter[idx] | (1 << bit)
+
 from mako.template import Template
 print Template(template).render(location_dict = location_dict,
                                 sized_lists = sized_lists,
                                 common_names = common_names,
-                                index_type = index_type)
+                                index_type = index_type,
+                                filter = filter,
+                                all_hash = all_hash)
-- 
1.8.1.4