Switch Performance in JavaScript

Recently, I've been running the Mozilla Rhino JavaScript interpreter as a JavaScript program in a web browser, and the performance has been awful. I haven't really dug too deeply into the performance yet, but one thing I've been curious about is the effect of the giant switch statement in the middle of the interpreter.

When writing a bytecode interpreter in C or C++, the switch statement is usually the way to go because you can rely on the compiler to use perfect hashing to make the best lookup tables, and switches in general are very light-weight structures that have performance similar to hand-coding a bunch of goto instructions. Since JavaScript optimizations are done at runtime, it's possible that using a giant switch statement with multiple cases handling the different bytecode instructions might not be optimized correctly.

switch(instruction) {   case jump: ...   case add: ...}

So, to test things out, I created a bunch of different test cases inside jsperf, and I tested them out. Here are the results:

The larger the number, the better. The bars represent:

1. dense array
2. dense switch
3. giant sparse array with negative values
4. giant switch with negative values and common paths at the end of the switch
5. giant switch with negative values
6. giant all positive sparse array
7. giant all positive sparse switch and common paths at the end of the switch
8. sparse array with negative values (and lots of lookups of negative values)
9. switch with sparse negative values  (and lots of lookups of negative values)
10. sparse array
11. sparse switch

It's a little bit worrisome that #4 has worse performance than #5 for all the browsers. The difference between the two is that you have a giant switch where usually only 16 cases of the switch are used. In #5, those 16 cases are at the head of the switch while in #4, those 16 cases come at the end of the switch. If the JavaScript engine were using lookup tables properly, then those two cases should have similar performance. Instead, #4 has worse performance than #5, suggesting that the JavaScript engines are actually encoding the switch statement as a series of if..else blocks, which can be slow if you have a lot of cases (which is definitely the case in a bytecode interpreter).

Chrome seems like it doesn't like it when you do lookups of negative values in arrays. It's possible that Chrome is using strings for negative numbers in arrays since the performance is so poor.

Overall, the numbers seem to suggest to me that if you've got hundreds of cases inside a switch statement, then using a lookup table of functions would probably be a better design though you've got to be careful not to use negative indices.