BinarySwitch should be faster on average
[WebKit.git] / Source / JavaScriptCore / jit / BinarySwitch.cpp
index 82876d3feeeed74e5576f77225fd55b260c39e49..a24d72cb9eb61889cdabb8fbe58c41377bf15e84 100644 (file)
 
 namespace JSC {
 
+static unsigned globalCounter; // We use a different seed every time we are invoked.
+
 BinarySwitch::BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type type)
     : m_value(value)
+    , m_weakRandom(globalCounter++)
     , m_index(0)
     , m_caseIndex(UINT_MAX)
-    , m_medianBias(0)
     , m_type(type)
 {
     if (cases.isEmpty())
@@ -45,7 +47,11 @@ BinarySwitch::BinarySwitch(GPRReg value, const Vector<int64_t>& cases, Type type
     for (unsigned i = 0; i < cases.size(); ++i)
         m_cases.append(Case(cases[i], i));
     std::sort(m_cases.begin(), m_cases.end());
-    build(0, m_cases.size());
+    build(0, false, m_cases.size());
+}
+
+BinarySwitch::~BinarySwitch()
+{
 }
 
 bool BinarySwitch::advance(MacroAssembler& jit)
@@ -115,81 +121,201 @@ bool BinarySwitch::advance(MacroAssembler& jit)
     }
 }
 
-void BinarySwitch::build(unsigned start, unsigned end)
+void BinarySwitch::build(unsigned start, bool hardStart, unsigned end)
 {
     unsigned size = end - start;
     
-    switch (size) {
-    case 0: {
-        RELEASE_ASSERT_NOT_REACHED();
-        break;
-    }
+    RELEASE_ASSERT(size);
+    
+    // This code uses some random numbers to keep things balanced. It's important to keep in mind
+    // that this does not improve average-case throughput under the assumption that all cases fire
+    // with equal probability. It just ensures that there will not be some switch structure that
+    // when combined with some input will always produce pathologically good or pathologically bad
+    // performance.
+    
+    const unsigned leafThreshold = 3;
+    
+    if (size <= leafThreshold) {
+        // It turns out that for exactly three cases or less, it's better to just compare each
+        // case individually. This saves 1/6 of a branch on average, and up to 1/3 of a branch in
+        // extreme cases where the divide-and-conquer bottoms out in a lot of 3-case subswitches.
+        //
+        // This assumes that we care about the cost of hitting some case more than we care about
+        // bottoming out in a default case. I believe that in most places where we use switch
+        // statements, we are more likely to hit one of the cases than we are to fall through to
+        // default. Intuitively, if we wanted to improve the performance of default, we would
+        // reduce the value of leafThreshold to 2 or even to 1. See below for a deeper discussion.
         
-    case 1: {
-        if (start
-            && m_cases[start - 1].value == m_cases[start].value - 1
-            && start + 1 < m_cases.size()
-            && m_cases[start + 1].value == m_cases[start].value + 1) {
-            m_branches.append(BranchCode(ExecuteCase, start));
-            break;
+        bool allConsecutive = false;
+        
+        if ((hardStart || (start && m_cases[start - 1].value == m_cases[start].value - 1))
+            && start + size < m_cases.size()
+            && m_cases[start + size - 1].value == m_cases[start + size].value - 1) {
+            allConsecutive = true;
+            for (unsigned i = 0; i < size - 1; ++i) {
+                if (m_cases[i].value + 1 != m_cases[i + 1].value) {
+                    allConsecutive = false;
+                    break;
+                }
+            }
         }
         
-        m_branches.append(BranchCode(NotEqualToFallThrough, start));
-        m_branches.append(BranchCode(ExecuteCase, start));
-        break;
-    }
+        Vector<unsigned, 3> localCaseIndices;
+        for (unsigned i = 0; i < size; ++i)
+            localCaseIndices.append(start + i);
         
-    case 2: {
-        if (m_cases[start].value + 1 == m_cases[start + 1].value
-            && start
-            && m_cases[start - 1].value == m_cases[start].value - 1
-            && start + 2 < m_cases.size()
-            && m_cases[start + 2].value == m_cases[start + 1].value + 1) {
-            m_branches.append(BranchCode(NotEqualToPush, start));
-            m_branches.append(BranchCode(ExecuteCase, start));
+        std::random_shuffle(
+            localCaseIndices.begin(), localCaseIndices.end(),
+            [this] (unsigned n) {
+                // We use modulo to get a random number in the range we want fully knowing that
+                // this introduces a tiny amount of bias, but we're fine with such tiny bias.
+                return m_weakRandom.getUint32() % n;
+            });
+        
+        for (unsigned i = 0; i < size - 1; ++i) {
+            m_branches.append(BranchCode(NotEqualToPush, localCaseIndices[i]));
+            m_branches.append(BranchCode(ExecuteCase, localCaseIndices[i]));
             m_branches.append(BranchCode(Pop));
-            m_branches.append(BranchCode(ExecuteCase, start + 1));
-            break;
         }
         
-        unsigned firstCase = start;
-        unsigned secondCase = start + 1;
-        if (m_medianBias)
-            std::swap(firstCase, secondCase);
-        m_medianBias ^= 1;
+        if (!allConsecutive)
+            m_branches.append(BranchCode(NotEqualToFallThrough, localCaseIndices.last()));
         
-        m_branches.append(BranchCode(NotEqualToPush, firstCase));
-        m_branches.append(BranchCode(ExecuteCase, firstCase));
-        m_branches.append(BranchCode(Pop));
-        m_branches.append(BranchCode(NotEqualToFallThrough, secondCase));
-        m_branches.append(BranchCode(ExecuteCase, secondCase));
-        break;
+        m_branches.append(BranchCode(ExecuteCase, localCaseIndices.last()));
+        return;
     }
         
-    default: {
-        unsigned medianIndex = (start + end) / 2;
-        if (!(size & 1)) {
-            // Because end is exclusive, in the even case, this rounds up by
-            // default. Hence median bias sometimes flips to subtracing one
-            // in order to get round-down behavior.
-            medianIndex -= m_medianBias;
-            m_medianBias ^= 1;
-        }
+    // There are two different strategies we could consider here:
+    //
+    // Isolate median and split: pick a median and check if the comparison value is equal to it;
+    // if so, execute the median case. Otherwise check if the value is less than the median, and
+    // recurse left or right based on this. This has two subvariants: we could either first test
+    // equality for the median and then do the less-than, or we could first do the less-than and
+    // then check equality on the not-less-than path.
+    //
+    // Ignore median and split: do a less-than comparison on a value that splits the cases in two
+    // equal-sized halves. Recurse left or right based on the comparison. Do not test for equality
+    // against the median (or anything else); let the recursion handle those equality comparisons
+    // once we bottom out in a list that case 3 cases or less (see above).
+    //
+    // I'll refer to these strategies as Isolate and Ignore. I initially believed that Isolate
+    // would be faster since it leads to less branching for some lucky cases. It turns out that
+    // Isolate is almost a total fail in the average, assuming all cases are equally likely. How
+    // bad Isolate is depends on whether you believe that doing two consecutive branches based on
+    // the same comparison is cheaper than doing the compare/branches separately. This is
+    // difficult to evaluate. For small immediates that aren't blinded, we just care about
+    // avoiding a second compare instruction. For large immediates or when blinding is in play, we
+    // also care about the instructions used to materialize the immediate a second time. Isolate
+    // can help with both costs since it involves first doing a < compare+branch on some value,
+    // followed by a == compare+branch on the same exact value (or vice-versa). Ignore will do a <
+    // compare+branch on some value, and then the == compare+branch on that same value will happen
+    // much later.
+    //
+    // To evaluate these costs, I wrote the recurrence relation for Isolate and Ignore, assuming
+    // that ComparisonCost is the cost of a compare+branch and ChainedComparisonCost is the cost
+    // of a compare+branch on some value that you've just done another compare+branch for. These
+    // recurrence relations compute the total cost incurred if you executed the switch statement
+    // on each matching value. So the average cost of hitting some case can be computed as
+    // Isolate[n]/n or Ignore[n]/n, respectively for the two relations.
+    //
+    // Isolate[1] = ComparisonCost
+    // Isolate[2] = (2 + 1) * ComparisonCost
+    // Isolate[3] = (3 + 2 + 1) * ComparisonCost
+    // Isolate[n_] := With[
+    //     {medianIndex = Floor[n/2] + If[EvenQ[n], RandomInteger[], 1]},
+    //     ComparisonCost + ChainedComparisonCost +
+    //     (ComparisonCost * (medianIndex - 1) + Isolate[medianIndex - 1]) +
+    //     (2 * ComparisonCost * (n - medianIndex) + Isolate[n - medianIndex])]
+    //
+    // Ignore[1] = ComparisonCost
+    // Ignore[2] = (2 + 1) * ComparisonCost
+    // Ignore[3] = (3 + 2 + 1) * ComparisonCost
+    // Ignore[n_] := With[
+    //     {medianIndex = If[EvenQ[n], n/2, Floor[n/2] + RandomInteger[]]},
+    //     (medianIndex * ComparisonCost + Ignore[medianIndex]) +
+    //     ((n - medianIndex) * ComparisonCost + Ignore[n - medianIndex])]
+    //
+    // This does not account for the average cost of hitting the default case. See further below
+    // for a discussion of that.
+    //
+    // It turns out that for ComparisonCost = 1 and ChainedComparisonCost = 1, Ignore is always
+    // better than Isolate. If we assume that ChainedComparisonCost = 0, then Isolate wins for
+    // switch statements that have 20 cases or fewer, though the margin of victory is never large
+    // - it might sometimes save an average of 0.3 ComparisonCost. For larger switch statements,
+    // we see divergence between the two with Ignore winning. This is of course rather
+    // unrealistic since the chained comparison is never free. For ChainedComparisonCost = 0.5, we
+    // see Isolate winning for 10 cases or fewer, by maybe 0.2 ComparisonCost. Again we see
+    // divergence for large switches with Ignore winning, for example if a switch statement has
+    // 100 cases then Ignore saves one branch on average.
+    //
+    // Our current JIT backends don't provide for optimization for chained comparisons, except for
+    // reducing the code for materializing the immediate if the immediates are large or blinding
+    // comes into play. Probably our JIT backends live somewhere north of
+    // ChainedComparisonCost = 0.5.
+    //
+    // This implies that using the Ignore strategy is likely better. If we wanted to incorporate
+    // the Isolate strategy, we'd want to determine the switch size threshold at which the two
+    // cross over and then use Isolate for switches that are smaller than that size.
+    //
+    // The average cost of hitting the default case is similar, but involves a different cost for
+    // the base cases: you have to assume that you will always fail each branch. For the Ignore
+    // strategy we would get this recurrence relation; the same kind of thing happens to the
+    // Isolate strategy:
+    //
+    // Ignore[1] = ComparisonCost
+    // Ignore[2] = (2 + 2) * ComparisonCost
+    // Ignore[3] = (3 + 3 + 3) * ComparisonCost
+    // Ignore[n_] := With[
+    //     {medianIndex = If[EvenQ[n], n/2, Floor[n/2] + RandomInteger[]]},
+    //     (medianIndex * ComparisonCost + Ignore[medianIndex]) +
+    //     ((n - medianIndex) * ComparisonCost + Ignore[n - medianIndex])]
+    //
+    // This means that if we cared about the default case more, we would likely reduce
+    // leafThreshold. Reducing it to 2 would reduce the average cost of the default case by 1/3
+    // in the most extreme cases (num switch cases = 3, 6, 12, 24, ...). But it would also
+    // increase the average cost of taking one of the non-default cases by 1/3. Typically the
+    // difference is 1/6 in either direction. This makes it a very simple trade-off: if we believe
+    // that the default case is more important then we would want leafThreshold to be 2, and the
+    // default case would become 1/6 faster on average. But we believe that most switch statements
+    // are more likely to take one of the cases than the default, so we use leafThreshold = 3
+    // and get a 1/6 speed-up on average for taking an explicit case.
         
-        RELEASE_ASSERT(medianIndex > start);
-        RELEASE_ASSERT(medianIndex + 1 < end);
+    unsigned medianIndex = (start + end) / 2;
         
-        m_branches.append(BranchCode(LessThanToPush, medianIndex));
-        m_branches.append(BranchCode(NotEqualToPush, medianIndex));
-        m_branches.append(BranchCode(ExecuteCase, medianIndex));
+    // We want medianIndex to point to the thing we will do a less-than compare against. We want
+    // this less-than compare to split the current sublist into equal-sized sublists, or
+    // nearly-equal-sized with some randomness if we're in the odd case. With the above
+    // calculation, in the odd case we will have medianIndex pointing at either the element we
+    // want or the element to the left of the one we want. Consider the case of five elements:
+    //
+    //     0 1 2 3 4
+    //
+    // start will be 0, end will be 5. The average is 2.5, which rounds down to 2. If we do
+    // value < 2, then we will split the list into 2 elements on the left and three on the right.
+    // That's pretty good, but in this odd case we'd like to at random choose 3 instead to ensure
+    // that we don't become unbalanced on the right. This does not improve throughput since one
+    // side will always get shafted, and that side might still be odd, in which case it will also
+    // have two sides and one of them will get shafted - and so on. We just want to avoid
+    // deterministic pathologies.
+    //
+    // In the even case, we will always end up pointing at the element we want:
+    //
+    //     0 1 2 3
+    //
+    // start will be 0, end will be 4. So, the average is 2, which is what we'd like.
+    if (size & 1) {
+        RELEASE_ASSERT(medianIndex - start + 1 == end - medianIndex);
+        medianIndex += m_weakRandom.getUint32() & 1;
+    } else
+        RELEASE_ASSERT(medianIndex - start == end - medianIndex);
         
-        m_branches.append(BranchCode(Pop));
-        build(medianIndex + 1, end);
+    RELEASE_ASSERT(medianIndex > start);
+    RELEASE_ASSERT(medianIndex + 1 < end);
         
-        m_branches.append(BranchCode(Pop));
-        build(start, medianIndex);
-        break;
-    } }
+    m_branches.append(BranchCode(LessThanToPush, medianIndex));
+    build(medianIndex, true, end);
+    m_branches.append(BranchCode(Pop));
+    build(start, hardStart, medianIndex);
 }
 
 } // namespace JSC