BinarySwitch should be faster on average
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 2 Feb 2015 20:52:01 +0000 (20:52 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 2 Feb 2015 20:52:01 +0000 (20:52 +0000)
commita4c898240fccdba16a6cbd04624831693be8a05d
tree06954190c8004979b2532a8d208a3d97ba05ce53
parent41d2d70279b3aa1d33bb7cb77e033973f3723671
BinarySwitch should be faster on average
https://bugs.webkit.org/show_bug.cgi?id=141046

Reviewed by Anders Carlsson.

This optimizes our binary switch using math. It's strictly better than what we had before
assuming we bottom out in some case (rather than fall through), assuming all cases get
hit with equal probability. The difference is particularly large for large switch
statements. For example, a switch statement with 1000 cases would previously require on
average 13.207 branches to get to some case, while now it just requires 10.464.

This is also a progression for the fall-through case, though we could shave off another
1/6 branch on average if we wanted to - though it would regress taking a case (not falling
through) by 1/6 branch. I believe it's better to bias the BinarySwitch for not falling
through.

This also adds some randomness to the algorithm to minimize the likelihood of us
generating a switch statement that is always particularly bad for some input. Note that
the randomness has no effect on average-case performance assuming all cases are equally
likely.

This ought to have no actual performance change because we don't rely on binary switches
that much. The main reason why this change is interesting is that I'm finding myself
increasingly relying on BinarySwitch, and I'd like to know that it's optimal.

* jit/BinarySwitch.cpp:
(JSC::BinarySwitch::BinarySwitch):
(JSC::BinarySwitch::~BinarySwitch):
(JSC::BinarySwitch::build):
* jit/BinarySwitch.h:

git-svn-id: http://svn.webkit.org/repository/webkit/trunk@179490 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Makefile.shared
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/jit/BinarySwitch.cpp
Source/JavaScriptCore/jit/BinarySwitch.h
Source/WebKit2/WebProcess/com.apple.WebProcess.sb.in