Bug 1171842 - Use jump table instead of nested if statements for peeking compute function of style struct. r=dbaron
authorXidorn Quan <quanxunzhen@gmail.com>
Fri, 12 Jun 2015 14:32:46 +1200
changeset 279328 2b37fea15848ab8491e2df488c19c650b0595cd5
parent 279327 7b49caef100aa96f0ad0506b83c2fd124b3fb8d4
child 279329 53ea4904898e33a94de318fa451da324e81d7ab2
push id4932
push userjlund@mozilla.com
push dateMon, 10 Aug 2015 18:23:06 +0000
treeherdermozilla-beta@6dd5a4f5f745 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdbaron
bugs1171842
milestone41.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1171842 - Use jump table instead of nested if statements for peeking compute function of style struct. r=dbaron
layout/style/generate-stylestructlist.py
layout/style/nsRuleNode.cpp
--- a/layout/style/generate-stylestructlist.py
+++ b/layout/style/generate-stylestructlist.py
@@ -4,43 +4,17 @@
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 # This script generates nsStyleStructList.h, which contains macro invocations
 # that can be used for three things:
 #
 # 1. To generate code for each inherited style struct.
 # 2. To generate code for each reset style struct.
-# 3. To generate a tree of nested if statements that can be used to run
-#    some code on each style struct.
-#
-# As an example, if we assume that we have only four style structs, the
-# generated tree of nested if statements looks like this:
-#
-#   if (STYLE_STRUCT_TEST < 4) {
-#     if (STYLE_STRUCT_TEST < 2) {
-#       if (STYLE_STRUCT_TEST == 0) {
-#         ... code for style struct with id 0 ...
-#       } else {
-#         ... code for style struct with id 1 ...
-#       }
-#     } else {
-#       if (STYLE_STRUCT_TEST == 2) {
-#         ... code for style struct with id 2 ...
-#       } else {
-#         ... code for style struct with id 3 ...
-#       }
-#     }
-#   }
-#
-# The TOPLEVELBRANCHES variable controls how widely we branch on the outermost
-# if statement.  In the example above, it splits the search space in 2, but with
-# a larger number of style structs to test -- particularly when the number is
-# closer to one power of two than the next higher one -- the average number of
-# comparisons can be reduced by splitting the top level check into more than 2.
+# 3. To generate the dependency of each style struct.
 
 from __future__ import print_function
 
 import math
 
 NORMAL_DEP = ["Variables"]
 COLOR_DEP = ["Color"]
 LENGTH_DEP = ["Font", "Visibility"]
@@ -72,19 +46,16 @@ STYLE_STRUCTS = [("INHERITED",) + x for 
     ("Padding",        "nullptr",   NORMAL_DEP + LENGTH_DEP),
     ("Border",         "nullptr",   NORMAL_DEP + LENGTH_DEP + COLOR_DEP),
     ("Outline",        "nullptr",   NORMAL_DEP + LENGTH_DEP + COLOR_DEP),
     ("XUL",            "nullptr",   NORMAL_DEP),
     ("SVGReset",       "nullptr",   NORMAL_DEP + LENGTH_DEP + COLOR_DEP),
     ("Column",         "nullptr",   NORMAL_DEP + LENGTH_DEP + COLOR_DEP),
 ]]
 
-# How widely to branch on the outermost if statement.
-TOPLEVELBRANCHES = 4
-
 
 # ---- Generate nsStyleStructList.h ----
 
 count = len(STYLE_STRUCTS)
 
 # Check for problems with style struct dependencies
 resolved_items = []
 # This whole loop tries to sort the style structs in topological order
@@ -111,52 +82,22 @@ for i in range(count):
         print("ERROR: Cannot resolve style struct dependencies", file=sys.stderr)
         print("Resolved items:", " ".join(resolved_items), file=sys.stderr)
         unsolved_items = [name for _, name, _, _ in STYLE_STRUCTS
                           if name not in resolved_items]
         print("There exist cyclic dependencies between " +
                   "the following structs:", " ".join(unsolved_items), file=sys.stderr)
         exit(1)
 
-def nextPowerOf2(x):
-    return int(pow(2, math.ceil(math.log(x, 2))))
-
 def printEntry(header, i):
     print("STYLE_STRUCT_%s(%s, %s)" % STYLE_STRUCTS[i][:3], file=header)
     for dep in STYLE_STRUCTS[i][3]:
         print("STYLE_STRUCT_DEP(%s)" % (dep,), file=header)
     print("STYLE_STRUCT_END()", file=header)
 
-def printTestTree(header, min, max, depth, branches):
-    indent = "  " * depth
-    if min == count - 1 and max >= count:
-        print("  STYLE_STRUCT_TEST_CODE(%sNS_ASSERTION(STYLE_STRUCT_TEST == %d, \"out of range\");)" % (indent, min), file=header)
-        printEntry(header, min)
-    elif max - min == 2:
-        print("  STYLE_STRUCT_TEST_CODE(%sif (STYLE_STRUCT_TEST == %d) {)" % (indent, min), file=header)
-        printEntry(header, min)
-        print("  STYLE_STRUCT_TEST_CODE(%s} else {)" % indent, file=header)
-        printEntry(header, min + 1)
-        print("  STYLE_STRUCT_TEST_CODE(%s})" % indent, file=header)
-    elif min < count:
-        mid = min + (max - min) / branches
-        print("  STYLE_STRUCT_TEST_CODE(%sif (STYLE_STRUCT_TEST < %d) {)" % (indent, mid), file=header)
-        printTestTree(header, min, mid, depth + 1, 2)
-        for branch in range(1, branches):
-            lo = min + branch * (max - min) / branches
-            hi = min + (branch + 1) * (max - min) / branches
-            if lo >= count:
-                break
-            if branch == branches - 1 or hi >= count:
-                print("  STYLE_STRUCT_TEST_CODE(%s} else {)" % indent, file=header)
-            else:
-                print("  STYLE_STRUCT_TEST_CODE(%s} else if (STYLE_STRUCT_TEST < %d) {)" % (indent, hi), file=header)
-            printTestTree(header, lo, hi, depth + 1, 2)
-        print("  STYLE_STRUCT_TEST_CODE(%s})" % indent, file=header)
-
 HEADER = """/* THIS FILE IS AUTOGENERATED BY generate-stylestructlist.py - DO NOT EDIT */
 
 // IWYU pragma: private, include "nsStyleStructFwd.h"
 
 /*
  * list of structs that contain the data provided by nsStyleContext, the
  * internal API for computed style data for an element
  */
@@ -184,22 +125,16 @@ HEADER = """/* THIS FILE IS AUTOGENERATE
 #define UNDEF_STYLE_STRUCT_DEP
 #endif
 
 #ifndef STYLE_STRUCT_END
 #define STYLE_STRUCT_END()
 #define UNDEF_STYLE_STRUCT_END
 #endif
 
-#ifdef STYLE_STRUCT_TEST
-#define STYLE_STRUCT_TEST_CODE(c) c
-#else
-#define STYLE_STRUCT_TEST_CODE(c)
-#endif
-
 // The inherited structs are listed before the Reset structs.
 // nsStyleStructID assumes this is the case, and callers other than
 // nsStyleStructFwd.h that want the structs in id-order just define
 // STYLE_STRUCT rather than including the file twice.
 
 """
 FOOTER = """
 #ifdef UNDEF_STYLE_STRUCT_INHERITED
@@ -216,16 +151,15 @@ FOOTER = """
 #undef STYLE_STRUCT_DEP
 #undef UNDEF_STYLE_STRUCT_DEP
 #endif
 
 #ifdef UNDEF_STYLE_STRUCT_END
 #undef STYLE_STRUCT_END
 #undef UNDEF_STYLE_STRUCT_END
 #endif
-
-#undef STYLE_STRUCT_TEST_CODE
 """
 
 def main(header):
     print(HEADER, file=header)
-    printTestTree(header, 0, nextPowerOf2(count), 0, TOPLEVELBRANCHES)
+    for i in range(count):
+        printEntry(header, i)
     print(FOOTER, file=header)
--- a/layout/style/nsRuleNode.cpp
+++ b/layout/style/nsRuleNode.cpp
@@ -2382,28 +2382,29 @@ nsRuleNode::WalkRuleTree(const nsStyleSt
       return parentStruct;
     }
     else
       // We are the root.  In the case of fonts, the default values just
       // come from the pres context.
       return SetDefaultOnRoot(aSID, aContext);
   }
 
-  // We need to compute the data from the information that the rules specified.
-  const void* res;
-#define STYLE_STRUCT_TEST aSID
-#define STYLE_STRUCT(name, checkdata_cb)                                      \
-  res = Compute##name##Data(startStruct, &ruleData, aContext,                 \
-                            highestNode, detail, ruleData.mCanStoreInRuleTree);
+  typedef const void* (nsRuleNode::*ComputeFunc)(void*, const nsRuleData*,
+                                                 nsStyleContext*, nsRuleNode*,
+                                                 RuleDetail, const bool);
+  static const ComputeFunc sComputeFuncs[] = {
+#define STYLE_STRUCT(name, checkdata_cb) &nsRuleNode::Compute##name##Data,
 #include "nsStyleStructList.h"
 #undef STYLE_STRUCT
-#undef STYLE_STRUCT_TEST
-
-  // Now return the result.
-  return res;
+  };
+
+  // We need to compute the data from the information that the rules specified.
+  return (this->*sComputeFuncs[aSID])(startStruct, &ruleData, aContext,
+                                      highestNode, detail,
+                                      ruleData.mCanStoreInRuleTree);
 }
 
 const void*
 nsRuleNode::SetDefaultOnRoot(const nsStyleStructID aSID, nsStyleContext* aContext)
 {
   switch (aSID) {
     case eStyleStruct_Font:
     {