glsl: Add Bloom filter to get_static_nameglsl-diet-v4

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.

v2: Apply many Python suggestions from Dylan.

Signed-off-by: Ian Romanick <ian.d.romanick@intel.com>

1 files changed, 114 insertions, 2 deletions

diff --git a/src/glsl/common_variable_names.py b/src/glsl/common_variable_names.py
index cd37a3d441f..03264a12ca9 100644
--- a/src/glsl/common_variable_names.py
+++ b/src/glsl/common_variable_names.py
@@ -19,7 +19,7 @@
 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 # DEALINGS IN THE SOFTWARE.
 
-from __future__ import print_function
+from __future__ import print_function, division
 from mako.template import Template
 
 COMMON_NAMES = sorted([
@@ -122,6 +122,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
  *
@@ -132,6 +172,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;
@@ -191,6 +236,19 @@ get_static_name(const char *name)
 }
 """
 
+def calculate_hash(str):
+    """The djb2 string hash algorithm from the old comp.lang.c days.
+
+    The hash used in the Python code and the generated C code must produce
+    identical results.
+    """
+    hash = 5381
+
+    for c in str:
+        hash = ((hash * 33) + ord(c)) & 0x0ffffffff
+
+    return hash
+
 # Partiation the list of names into sublists of names with the same length
 sized_lists = {}
 for name in COMMON_NAMES:
@@ -211,7 +269,61 @@ elif base < (1 << 16):
 else:
    index_type = "uint32_t"
 
+all_hash = [calculate_hash(name) for name in COMMON_NAMES]
+
+# 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 = [0] * (filter_bits // 32)
+
+for h in all_hash:
+    idx = ((h - m) % filter_bits) // 32
+    bit = ((h - m) % filter_bits) % 32
+
+    filter[idx] = filter[idx] | (1 << bit)
+
 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))