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)
commit064b528c3381d1403f458f4e96f3a6bbe5d2e426
tree06954190c8004979b2532a8d208a3d97ba05ce53
parentd7700b21e1162dff9454ee186cb614a9410baee7
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: https://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