[Webkit-unassigned] [Bug 141046] BinarySwitch should be faster on average

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=141046

Filip Pizlo <fpizlo at apple.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|webkit-unassigned at lists.web |fpizlo at apple.com
                   |kit.org                     |

--- Comment #1 from Filip Pizlo <fpizlo at apple.com> ---
Created attachment 245643
  --> https://bugs.webkit.org/attachment.cgi?id=245643&action=review
average binary switch performance

This plots the average number of branches that will be taken to get to the code for some case, assuming that cases are sparse and each case is taken with equal probability.  The X axis is the total number of cases.

The top blue line is our current algorithm, which special-cases 1 and 2 cases (just branches on each of them in turn, which I say is a linear branch cascade) and handles all other cases by finding the median (choosing one of the two median candidates at random for odd inputs) and then saying something like:

if (value < median)
    recurse left
else if (value == median)
    handle median
else
    recurse right

The red line just below it shows the performance if we also special-cases 3 cases with a linear branch cascade.  This is indeed faster.  Here's an example of 3 cases with the old algorithm for case values (left, middle, right):

if (value < middle) {
    if (value == left)
        handle left
} else if (value == middle) {
    handle middle
} else {
    if (value == right)
        handle right
}

This requires 2 branches for left, 2 branches for middle, and three branches for right.  If we do a linear branch cascade:

if (value == left)
    handle left
else if (value == middle)
    handle middle
else if (value == right)
    handle right

then we get 1 branch for left, 2 branches for middle, and three branches for right.  So, on average, we have 2 branches instead of 2.33.

The lowest line represents an additional optimization, where we handle even numbers of cases totally differently.  Instead of picking one of the two median candidates and using the left-median-right approach where the median is directly compared against, we just branch to determine whether we lie in the left half of the cases or the right half.  Let rightMedian be the value in an even-sized array that is just to the right of the formal median (i.e. it's the larger of the two median candidates).  Then for even numbers of cases we do:

if (value < rightMedian)
    recurse left
else
    recurse right

And for odd numbers of cases we still do as before:

if (value < median)
    recurse left
else if (value == median)
    handle median
else
    recurse right

This will sometimes save us a dramatic number of branches.  I'm still exploring ways of improving this even further.  The noisiness of this algorithm's performance suggests that maybe we can do even better.

-- 
You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20150129/3b7fa7a6/attachment-0002.html>