I stumbled across this concept recently and I thought I’d share it, because I don’t generally see this pattern being used. More importantly, I also share test results that show that maybe it’s not always a good idea to use this pattern…
The problem with Switch statements
The basic switch statement in JavaScript looks something like this:
var foo = 'c';
switch(foo) {
case 'a':
break;
case 'b':
break;
case 'c':
break;
default:
}
So what’s wrong with this? The JS engine has to examine a bunch of unrelated cases until it finds the relevant one, executes the code, then breaks out of the switch because the job is done (this is why it’s important to break!). In the above example we had to go through case A and case B until finally reaching case C. What’s worse is that if it didn’t match any of these cases, the JS engine has to jump through ALL of the cases before it reaches Default, the fall-through case.
Actually it’s not so bad, as long as there are a limited number of cases. It’s probably no big deal if you only have a few cases to jump through. The problem gets bigger as your number of cases increases (some of you may know this as O(n)). What happens when there’s 10 cases? Then there’s potentially 10 checks on cases (assuming what ended up being executed was the default). 100 cases? Then potentially 100 checks.
What would be better is if there were a way to reduce the number of checks. One way would be to put the most frequently used cases at the top. This would alleviate some of the pain, but you still end up with extra processing while the JS checks each case. It would be ideal to avoid this extra processing altogether.
An alternative: The hash table
There is a way to avoid this extra processing! It’s by leading the code directly where it needs to go, without unnecessary checking of unrelated cases.
You can do this using a hash. In JavaScript we accomplish this with an object:
var foo = 'c';
var cases = {};
cases['a'] = function() {
alert('I am A!');
};
cases['b'] = function() {
alert('I am B!');
};
cases['c'] = function() {
alert('I am C!');
}
if(typeof cases[foo] == 'function') {
// only executes if we've defined it above
cases[foo](); // I am C!
} else {
// default (the fallthrough)
}
There we go! No extra case checking here. We’ve led the JS straight to the code we want to execute!
Performance improvement…?
So.. this hash lookup seems faster in theory, but what about in practice? Unfortunately I ended up with some mixed results…
I created a simple performance test on jsperf.com and got these results:
| Browser | Switch ops/sec | Hash table ops/sec | % Difference |
| Chrome 6.0.490.1 dev | 34,606,469 | 43,329,587 | 25% faster |
| Safari 5.0 | 16,777,216 | 10,854,824 | 35% slower |
| Opera 10.61 | 4,405,782 | 2,719,336 | 38% slower |
| Firefox 3.6.3 | 2,785,802 | 2,400,586 | 14% slower |
| IE6 | 147,870 | 206,869 | 40% faster |
| IE7 | 144,735 | 191,179 | 32% faster |
| IE8 | 350,085 | 472,417 | 35% faster |
| Mobile Safari (iOS4 on iPhone 3GS) | 668,053 | 416,366 | 37% slower |
| Android (2.2 on Nexus One) | 605,693 | 864,591 | 42% faster |
* Ops/sec = Operations per second. Higher is better
** Chrome, Safari, Opera, and Firefox were tested on Mac OSX 10.6.4 2.53GHz Intel Core i5. IE tests were run on Windows 7 64bit 2.4GHz Quad Core
The Results
From the results, it looks like the hash optimization is only a benefit for Chrome, IE6-IE8, and Android. That’s quite a specific sampling. My guess is that the other browsers have implemented some sort of Switch statement optimizations that actually turn the hash optimization into an antipattern.
More info
Although I first read about this online, by no surprise this trick also appears in Nicholas Zakas’s High Performance JavaScript in a section on “Lookup Tables” (p. 72).
good one, not sure about javascript engine, but some compilers might have optimizations for these kinda cases. there is one similar performance benchmark for php i found quite interesting: http://www.phpbench.com/
gzge
This is one of the interesting things you can do in languages where functions are first class members. For example, Python doesn’t have a native switch statement, and a hashmap to simulate it is the closest you can get. However, as the interpreters evolve, they’re often able to optimize for this. In Java, I stick to an if/else structure as the JVM does optimize for this.
@gzge Interesting test results. It seems to show that while loops are slightly faster, and I think that’s generally the case in JS engines too. JS engines definitely optimize for some things. They used to be slow at string concatenation (‘a’ + ‘b’ + ‘c’ in JS or ‘a’ . ‘b’ . ‘c’ in PHP) but they’ve all optimized it now.
@Karan yeah I guess when you refactor the code it becomes a matter of how it gets optimized. In the case of JS it’s so frustrating because there’s so many JS engines out there.. it makes me (almost) want to write some tool that rewrites everything at “compile” time (when the JS is minified) and optimizes everything for each browser.
David,
for readability I would probably still fall back on the switch statement, however, a very nice technique indeed, never thought about using functions this way.
Thanks for sharing.
Juergen
In cases where the values of each case statement are sequential, the switch statement is intended to treat this using what is known as a branch or jump table. So a properly designed compiler or in the case of javascript the just in time compiler should create a jump table in these cases. So a switch statement should be the most efficient method of handling large numbers of sequential cases.
The one problem with your example is some compilers may not recognize sequential string values. If the values had been 1, 2, 3 instead of ‘a’, ‘b’, ‘c’, then it is more likely a jump table will be used. However, a well written compiler will recognize the string case as well.
The problem with the hash table of function pointers is the fact there is overhead with calling functions. I had used this many times before myself as I too thought the switch method would be implemented using value testing. Having finally gotten around to reading the design reasons behind the switch statement, I realized it was actually meant to be the most efficient method of doing these types of tasks.
So the switch method should normally be faster. I was surprised the hash method was faster on an up to date browser like Chrome as I would have expected it to recognize the ability to use a jump table.
Thanks for the table as I just happen to be in the process of writing some code using extremely large switch statements. I found your site as I was trying to find some benchmarks specifically related to this very method on both desktop and mobile browsers. So this is very useful to me.
I was wondering if you would be able to try this benchmark in the case where the case values are sequential numeric values. It would be interesting to see the results.
Brian
Having looked at source for several of the VMs, I questioned the mixed findings and wrote another test case on jsperf. The oddly-named test at http://jsperf.com/casevsswitch would seem to imply that switches are in fact extremely slow compared to a pure object lookup on most major browsers. Two differences between your test case and mine that I noticed :
1) I used a javascript object, not an array.
2) Your test case for evaluating the switch statement uses the lookup-by-key within the switch, essentially decoding the key twice (once by the switch, then again as an index into the array); my test decodes the key only once.
What do you think?