switch() vs elseif benchmarks
Posted on by AJ Ianozi
There was an interesting benchmark on a friend’s blog. He was running a “switch() vs else if” test in php, which yielded some very interesting (and at first, perplexing) results.
I’d just head over there and read his article as a primer, so you know where I’m coming from. Now, after reading his results, I was desperate to find out why this was happening, and I decided to run some benchmarks on my own.
Might want to sit back, this is going to be a long one (you’ll have to click “Read More” for this one).
An overview of switch() and elseif
Before I go into this, I first want to explain what the difference between the switch() statement, and the elseif statement is, as far as performance. If you know the difference between these two on an assembly-level, you can skip this part.
My examples why explaining will be in C, as that’s the language I know best, and what I’m mentioning, applies to C, as I don’t know how PHP implements switch() and elseif, I can only guess what’s going on behind the scenes with php.
Now, consider the following two programs:
int main()
{
int myVar = 0;
int foo;
if(myVar == 1)
++myVar;
else if(myVar == 2)
--myVar;
else if(myVar == 3)
myVar++;
else if(myVar == 4)
myVar--;
else if(myVar == 5)
--myVar;
else if(myVar == 6)
myVar=0x3;
else if(myVar == 7)
myVar=0xff;
else if(myVar == 8)
myVar=0xff;
else if(myVar == 9)
myVar=0x2a;
else if(myVar == 10)
myVar=0x801;
else if(myVar == 11)
myVar=0x6;
else if(myVar == 12)
myVar=0xfa;
else if(myVar == 13)
myVar=0x0354;
else if(myVar == 14)
myVar=myVar+8;
else if(myVar == 15)
myVar=415;
else
myVar=0xF;
foo = myVar;
return 0;
}
And
int main()
{
int myVar = 0;
int foo;
switch(myVar)
{
case 1:
++myVar;
break;
case 2:
--myVar;
break;
case 3:
myVar++;
break;
case 4:
myVar--;
break;
case 5:
--myVar;
break;
case 6:
myVar=0x3;
break;
case 7:
myVar=0xff;
break;
case 8:
myVar=0xff;
break;
case 9:
myVar=0x2a;
break;
case 10:
myVar=0x801;
break;
case 11:
myVar=0x6;
break;
case 12:
myVar=0xfa;
break;
case 13:
myVar=0x0354;
break;
case 14:
myVar=myVar+8;
break;
case 15:
myVar=415;
break;
}
foo = myVar;
return 0;
}
Now, when this is compiled, the first program would end up compiling into a mess of cmp and jmp commands, one-by-one, working its way down.
If myVar happened to be 15, it would end up doing 15 conditionals. The worst-case scenario here, would be that myVar isn’t a number listed, and the result would be a test of every possible condition, until it reaches the else.
As for the switch(), that actually manages to be pretty efficient (well… VERY efficient) because it compiles into a jump table. That means only one test is done.
To make things alittle more clear, I had my compile output the assembly of both versions:
Else-if Statement
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
movq %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl $0, -4(%rbp)
cmpl $1, -4(%rbp)
jne .L2
addl $1, -4(%rbp)
jmp .L3
.L2:
cmpl $2, -4(%rbp)
jne .L4
subl $1, -4(%rbp)
jmp .L3
.L4:
cmpl $3, -4(%rbp)
jne .L5
addl $1, -4(%rbp)
jmp .L3
.L5:
cmpl $4, -4(%rbp)
jne .L6
subl $1, -4(%rbp)
jmp .L3
.L6:
cmpl $5, -4(%rbp)
jne .L7
subl $1, -4(%rbp)
jmp .L3
.L7:
cmpl $6, -4(%rbp)
jne .L8
movl $3, -4(%rbp)
jmp .L3
.L8:
cmpl $7, -4(%rbp)
jne .L9
movl $255, -4(%rbp)
jmp .L3
.L9:
cmpl $8, -4(%rbp)
jne .L10
movl $255, -4(%rbp)
jmp .L3
.L10:
cmpl $9, -4(%rbp)
jne .L11
movl $42, -4(%rbp)
jmp .L3
.L11:
cmpl $10, -4(%rbp)
jne .L12
movl $2049, -4(%rbp)
jmp .L3
.L12:
cmpl $11, -4(%rbp)
jne .L13
movl $6, -4(%rbp)
jmp .L3
.L13:
cmpl $12, -4(%rbp)
jne .L14
movl $250, -4(%rbp)
jmp .L3
.L14:
cmpl $13, -4(%rbp)
jne .L15
movl $852, -4(%rbp)
jmp .L3
.L15:
cmpl $14, -4(%rbp)
jne .L16
addl $8, -4(%rbp)
jmp .L3
.L16:
cmpl $15, -4(%rbp)
jne .L17
movl $415, -4(%rbp)
jmp .L3
.L17:
movl $15, -4(%rbp)
.L3:
movl -4(%rbp), %eax
movl %eax, -8(%rbp)
movl $0, %eax
leave
ret
.cfi_endproc
Switch Statement
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
movq %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl $0, -4(%rbp)
cmpl $15, -4(%rbp)
ja .L2
mov -4(%rbp), %eax
movq .L18(,%rax,8), %rax
jmp *%rax
.section .rodata
.align 8
.align 4
.L18:
.quad .L2
.quad .L3
.quad .L4
.quad .L5
.quad .L6
.quad .L7
.quad .L8
.quad .L9
.quad .L10
.quad .L11
.quad .L12
.quad .L13
.quad .L14
.quad .L15
.quad .L16
.quad .L17
.text
.L3:
addl $1, -4(%rbp)
jmp .L2
.L4:
subl $1, -4(%rbp)
jmp .L2
.L5:
addl $1, -4(%rbp)
jmp .L2
.L6:
subl $1, -4(%rbp)
jmp .L2
.L7:
subl $1, -4(%rbp)
jmp .L2
.L8:
movl $3, -4(%rbp)
jmp .L2
.L9:
movl $255, -4(%rbp)
jmp .L2
.L10:
movl $255, -4(%rbp)
jmp .L2
.L11:
movl $42, -4(%rbp)
jmp .L2
.L12:
movl $2049, -4(%rbp)
jmp .L2
.L13:
movl $6, -4(%rbp)
jmp .L2
.L14:
movl $250, -4(%rbp)
jmp .L2
.L15:
movl $852, -4(%rbp)
jmp .L2
.L16:
addl $8, -4(%rbp)
jmp .L2
.L17:
movl $415, -4(%rbp)
.L2:
movl -4(%rbp), %eax
movl %eax, -8(%rbp)
movl $0, %eax
leave
ret
.cfi_endproc
Don’t be afraid because it’s assembly; it’s very easy to follow. Now, this doesn’t exactly apply to strings as much (and we’ll get to that later while looking at php).
Back to the benchmarks!
If you at Andrew’s benchmarks, I’d assume the latter is faster most of the time due to the nature of PHP using hashmaps to store their arrays.
What I mean is, the second test is essentially using a key for the array as the conditional. This tends to be very fast when looking something up (given the index exists).
I was wondering what would happen if something like this was used:
<?php
function use_ifelse($case)
{
if ($case == 'hello')
{
echo 'world';
}
elseif($case == 'hi')
{
echo 'bye';
}
elseif($case == 'lol')
{
echo 'hax';
}
elseif($case == 'why')
{
echo 'how';
}
elseif($case == 'hehe')
{
echo 'rofl';
}
elseif($case == 'cat')
{
echo 'person';
}
else
{
echo "Default";
}
}
?>
I’m willing to guess that searching use_ifelse("hello") and use_switch("hello") will take the exact same amount of time to do, while the hashmap will be faster; but more on that later. If you were to do something like, have it parse the last key in the conditional, the switch should be faster than the else-if by a long shot, whereas the hashmap and the switch should be about the same (with the hashmap being abit faster).
So, I extended Andrews code to whip out a little program to test that:
Click here to expand
function use_ifelse($case)
{
if ($case == 'hello')
{
echo 'world';
}
elseif($case == 'hi')
{
echo 'bye';
}
elseif($case == 'lol')
{
echo 'hax';
}
elseif($case == 'why')
{
echo 'how';
}
elseif($case == 'hehe')
{
echo 'rofl';
}
elseif($case == 'cat')
{
echo 'person';
}
else
{
echo "Default";
}
}
function use_switch($case)
{
switch ($case) {
case 'hello':
echo 'world';
break;
case 'hi':
echo 'bye';
break;
case 'lol':
echo 'hax';
break;
case 'why':
echo 'how';
break;
case 'hehe':
echo 'rofl';
break;
case 'cat':
echo 'person';
break;
default:
echo "Default";
break;
}
}
$cases = array(
'hello' => 'world',
'hi' => 'bye',
'lol' => 'hax',
'why' => 'how',
'hehe' => 'rofl',
'cat' => 'person'
);
function use_map($case)
{
global $cases;
if (array_key_exists($case, $cases))
{
echo $cases[$case];
}
else
{
echo 'Default';
}
}
/*switch()*/
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_switch('hello');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of switch first key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_switch('cat');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of switch last key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_switch('ujefgojiogej');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of switch non-existing key: %fms.
", (($etimer-$stimer) * 1000) );
/*ifelse*/
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_ifelse('hello');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of if/else existing key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_ifelse('cat');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of if/else last key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_ifelse('ujefgojiogej');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of if/else non-existing key: %fms.
", (($etimer-$stimer) * 1000) );
/*map*/
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_map('hello');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of map existing key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_map('cat');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of map last: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_map('ujefgojiogej');
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of map non-existing key: %fms.
", (($etimer-$stimer) * 1000) );
?>
The results? Surprising.
ianozia@ianozia-desktop ~/Desktop $ php test.php
worldExecution time of switch first key: 0.056028ms.
personExecution time of switch last key: 0.006199ms.
DefaultExecution time of switch non-existing key: 0.005960ms.
worldExecution time of if/else existing key: 0.005007ms.
personExecution time of if/else last key: 0.005960ms.
DefaultExecution time of if/else non-existing key: 0.005007ms.
worldExecution time of map existing key: 0.015974ms.
personExecution time of map last: 0.006914ms.
DefaultExecution time of map non-existing key: 0.005960ms.
ianozia@ianozia-desktop ~/Desktop $
Not exactly the results that I’d expect. According to this, the elseif was faster when the first key was used. When an invalid key is used, it’s about the same as the switch(). The else-if was also the fastest when there was no key – wut?
After some thinking, I had a few theories. The first, is the fact that it’s doing comparisons on strings had a non-desirable outcome (I’ll explain that soon). The second, is that the preprocessor is optimizing the (which could very well explain Andrew’s results as well). The last theory, is that PHP handles the switch() and elseif much differently than compiled languages. This required more tests.
A word on optimizations.
See, when I compiled my C-code for my switch() vs elseif example, I had to turn off all possible optimization, and I’ll tell you why. Remember my first program? While compiling it, the gcc kept realizing that I would set the variable to 0 at the beginning, and it would turn that massive elseif statement into something like: “myVar = 0xF;” Why? Because it realized there’s no possible way that myVal will ever be something different, so gcc set it up so it wouldn’t have to even check.
This can be good for programs, however it’s not good if you’re trying to make an example or trying to understand how something works.
Why does this matter to us right now? Because say for, use_ifelse(“aoeuidhtns”), PHP could have very well turned our elseif statement into something like:
function use_else($case)
{
echo "Default";
}
Of course, this would be because PHP realized that, for this particular case, our variable would never be anything in the if-statement (it saw us declare it earlier!) and optimized.
In gcc, you can turn off all optimizations by using the compiler flag “-O0”. Can’t do this in PHP; I’ll have to make the variable unpredictable.
A word on strings
It’s about time I mentioned strings.
The other reason things could be running slow, is the fact that it’s comparing strings. This is where the hashmap gains an advantage. What a hashmap does, is use a string as an index for something by hashing it into a number, then does some math on it. For instance, say you do:
object['ME'] = 20;
What it does, is hash the string “ME” into some obscure number, such as 52476465. Then, it does some math on that number (usually modular division) to get it in a certain index: 5. Thus, the hashmap stores 20 at: object[5].
This means the only overhead you have (assuming there’s never any collisions, which is beyond the scope of this study) is the amount it takes to turn that string into a number.
The reason why the hash map was slower handling "hello" and faster at handling "cat", was probably because "hello" is a longer string, and it would require more time to process it.
Trying to work out what happened with the switch statement, I can only assume it hashed the string to a number to try and compare them, or the preprocessor created some sort of “nested switch()” statements. This is the only way I could see “hello” taking almost twice as much time to find as say, “cat”.
As far as why elseif managed to be the fastest, I have no idea, I can only assume it has something to do with the way strings are handled in PHP, or the optimizer had done something to it.
A word one implementation
Something I must seriously consider, is how things are handled in PHP as opposed to C. I must remember that PHP is an Interpreted Language, and may not share the benefits of a compiled one (such as a jump table).
Yay more tests!
As I said before, we need to be able to test this objectively, without the optimizations. The only way I could think of doing that, would be without letting the preprocessor know what the variable contains, and setting it at runtime. And that, called for a new program!
Click here to expand
<?php
function use_ifelse($case)
{
if ($case == 'hello')
{
echo 'world';
}
elseif($case == 'hi')
{
echo 'bye';
}
elseif($case == 'lol')
{
echo 'hax';
}
elseif($case == 'why')
{
echo 'how';
}
elseif($case == 'hehe')
{
echo 'rofl';
}
elseif($case == 'cat')
{
echo 'person';
}
else
{
echo "Default";
}
}
function use_switch($case)
{
switch ($case) {
case 'hello':
echo 'world';
break;
case 'hi':
echo 'bye';
break;
case 'lol':
echo 'hax';
break;
case 'why':
echo 'how';
break;
case 'hehe':
echo 'rofl';
break;
case 'cat':
echo 'person';
break;
default:
echo "Default";
break;
}
}
$cases = array(
'hello' => 'world',
'hi' => 'bye',
'lol' => 'hax',
'why' => 'how',
'hehe' => 'rofl',
'cat' => 'person'
);
function use_map($case)
{
global $cases;
if (array_key_exists($case, $cases))
{
echo $cases[$case];
}
else
{
echo 'Default';
}
}
/*switch()*/
/*
$argv[1] should be "hello"
$argv[2] should be "cat"
$argv[3] should be "ujefgojiogej"
*/
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_switch($argv[1]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of switch first key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_switch($argv[2]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of switch last key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_switch($argv[3]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of switch non-existing key: %fms.
", (($etimer-$stimer) * 1000) );
/*ifelse*/
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_ifelse($argv[1]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of if/else existing key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_ifelse($argv[2]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of if/else last key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_ifelse($argv[3]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of if/else non-existing key: %fms.
", (($etimer-$stimer) * 1000) );
/*map*/
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_map($argv[1]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of map existing key: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_map($argv[2]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of map last: %fms.
", (($etimer-$stimer) * 1000) );
$stimer = explode( ' ', microtime() );
$stimer = $stimer[1] + $stimer[0];
use_map($argv[3]);
$etimer = explode( ' ', microtime() );
$etimer = $etimer[1] + $etimer[0];
printf( "Execution time of map non-existing key: %fms.
", (($etimer-$stimer) * 1000) );
?>
Unfortunately, the results were not changed:
ianozia@ianozia-desktop ~/Desktop $ php test.php hello cat aoeuidhtns
worldExecution time of switch first key: 0.056982ms.
personExecution time of switch last key: 0.007153ms.
DefaultExecution time of switch non-existing key: 0.005007ms.
worldExecution time of if/else existing key: 0.005007ms.
personExecution time of if/else last key: 0.005007ms.
DefaultExecution time of if/else non-existing key: 0.005007ms.
worldExecution time of map existing key: 0.014782ms.
personExecution time of map last: 0.005960ms.
DefaultExecution time of map non-existing key: 0.005007ms.
As before, the longer strings took longer to parse; there wasn’t much of a change between the switch and the hashmap. The elseif remained faster in most cases.
After this, I decided to stop messing around with strings, and decided to try something else – integers. This way, I remove the overhead of having to hash a string, and can focus on the offsets.
My last approach – the big finish
The last test I can do, will contain a switch table and elseif statement that has 65536 cases! This will allow me to not only see how all methods manage under pressure, but it will also allow me to test it against C.
As a note, the last item in a dataset is about 65000-something. I choose 50000-something to pick an item near the end. You’ll see this with afew of the tests, I just didn’t change the text.
ianozia@ianozia-desktop ~/Desktop $ php test.php 0 57664 90500
value is 0Execution time of switch first key: 0.088930ms.
value is 57664Execution time of switch last key: 7.657051ms.
noneExecution time of switch non-existing key: 8.169889ms.
value is 0Execution time of if/else existing key: 0.015974ms.
value is 57664Execution time of if/else last key: 8.311987ms.
noneExecution time of if/else non-existing key: 7.666111ms.
value is 0Execution time of map existing key: 15.012980ms.
value is 57664Execution time of map last: 14.298916ms.
DefaultExecution time of map non-existing key: 13.615131ms.
ianozia@ianozia-desktop ~/Desktop $
It appears that with a much bigger dataset, the results are similar, but it can be noticed that the method with the array is much, much, slower for some reason, being several ms slower than anything else. You may notice that it takes about 1ms longer if the key is somewhere in the index, when using elseif; once again, I have no idea how PHP implements it; it may be nothing like my assembly examples in that language.
And with that, just for the heck of it, I wrote the same program in C, and tested it:
ianozia@ianozia-desktop ~/Desktop $ ./test.elf 0 57664 90500
value is 0Execution time of switch first key: 0.21962ms.
value is 57664Execution time of switch last key: 0.04930ms.
noneExecution time of switch non-existing key: 0.01267ms.
value is 0Execution time of of if/else first key: 0.001374ms.
value is 57664Execution time of of if/else last key: 0.641709ms.
noneExecution time of of if/else non-existing key: 0.321692ms.
ianozia@ianozia-desktop ~/Desktop $
Let’s see what happens here. Unlike PHP, there was a significant difference between finding the data in an elseif, and looking up the data in a switch(). You will notice that the if-statement takes much less time if the item we’re looking for is the first item in the statement, but it will take much more time if it’s say, in the middle. This is the results I was expecting in PHP, but couldn’t exactly get – I’m going to assume that the preprocessor manages them differently.
There was also something to be noticed, and I ran into it when trying to compile my program: chained else if statements in C KILL the stack. This is because:
if()
else if(){}
else if(){}
else if(){}
else {}
Actually is seen as something like:
if()
{
}
else
{
if()
{
}
else
{
if()
{
}
else
{
if()
{
}
else
{
}
}
}
}
That mean the stack that keeps tabs on where the program is executing would have to grow about 6-times deep – in my C program, my stack grew to the size of 0xFFFF pointers – VERY large. But explaining why is beyond the scope of this.
Conclusions
- It seems that using a hashmap for conditionals doesn’t seem like that bad of an idea until it starts to get large, then it becomes a very bad idea.
- In PHP, a chain of elseif statements seem to be slightly faster for shorter datasets (or when the key is not found) and slightly longer in large datasets (but still shorter when there’s no key for some reason), than in a compiled language such as C. I’m guessing that’s probably because PHP cannot take advantage of lookup tables in assembly, being interpreted.
- In C, a chain of elseif statements are a bad idea, atleast when considering performance; the switch is much faster, as expected.
It should also be noted, the C program was able to handle the data much faster than PHP, with C’s switch for the middle being around 0.04 ms, while PHP’s switch was a little over 7. But this is expected, considering C is compiled and PHP is interpreted.
Comments (& Webmentions coming soon)
Mickcy on
While testing PHP, did you keep latency in mind?
Replies
A.J. on
Good question, and yes I did keep latency in mind.
When I ran these tests, I did so on my local machine, in my terminal; that is, to run a php script, I'd type:
$>php myfile.php
And my system would execute the script and write any echos to stdout (aka my terminal).