Is 'switch' faster than 'if'?

There are several optimizations a compiler can make on a switch. I don't think the oft-mentioned "jump-table" is a very useful one though, as it only works when the input can be bounded some way.

C Pseudocode for a "jump table" would be something like this -- note that the compiler in practice would need to insert some form of if test around the table to ensure that the input was valid in the table. Note also that it only works in the specific case that the input is a run of consecutive numbers.

If the number of branches in a switch is extremely large, a compiler can do things like using binary search on the values of the switch, which (in my mind) would be a much more useful optimization, as it does significantly increase performance in some scenarios, is as general as a switch is, and does not result in greater generated code size. But to see that, your test code would need a LOT more branches to see any difference.

To answer your specific questions:

Clang generates one that looks like this: test_switch(char): # @test_switch(char) movl %edi, %eax cmpl $19, %edi jbe .LBB0_1 retq .LBB0_1: jmpq *.LJTI0_0(,%rax,8) jmp void call<0u>() # TAILCALL jmp void call<1u>() # TAILCALL jmp void call<2u>() # TAILCALL jmp void call<3u>() # TAILCALL jmp void call<4u>() # TAILCALL jmp void call<5u>() # TAILCALL jmp void call<6u>() # TAILCALL jmp void call<7u>() # TAILCALL jmp void call<8u>() # TAILCALL jmp void call<9u>() # TAILCALL jmp void call<10u>() # TAILCALL jmp void call<11u>() # TAILCALL jmp void call<12u>() # TAILCALL jmp void call<13u>() # TAILCALL jmp void call<14u>() # TAILCALL jmp void call<15u>() # TAILCALL jmp void call<16u>() # TAILCALL jmp void call<17u>() # TAILCALL jmp void call<18u>() # TAILCALL jmp void call<19u>() # TAILCALL .LJTI0_0: .quad .LBB0_2 .quad .LBB0_3 .quad .LBB0_4 .quad .LBB0_5 .quad .LBB0_6 .quad .LBB0_7 .quad .LBB0_8 .quad .LBB0_9 .quad .LBB0_10 .quad .LBB0_11 .quad .LBB0_12 .quad .LBB0_13 .quad .LBB0_14 .quad .LBB0_15 .quad .LBB0_16 .quad .LBB0_17 .quad .LBB0_18 .quad .LBB0_19 .quad .LBB0_20 .quad .LBB0_21 I can say that it is not using a jump table -- 4 comparison instructions are clearly visible: 13FE81C51 cmp qword ptr [rsp+30h],1 13FE81C57 je testSwitch+73h (13FE81C73h) 13FE81C59 cmp qword ptr [rsp+30h],2 13FE81C5F je testSwitch+87h (13FE81C87h) 13FE81C61 cmp qword ptr [rsp+30h],3 13FE81C67 je testSwitch+9Bh (13FE81C9Bh) 13FE81C69 cmp qword ptr [rsp+30h],4 13FE81C6F je testSwitch+0AFh (13FE81CAFh) A jump table based solution does not use comparison at all. Either not enough branches to cause the compiler to generate a jump table, or your compiler simply doesn't generate them. I'm not sure which.

EDIT 2014: There has been some discussion elsewhere from people familiar with the LLVM optimizer saying that the jump table optimization can be important in many scenarios; e.g. in cases where there is an enumeration with many values and many cases against values in said enumeration. That said, I stand by what I said above in 2011 -- too often I see people thinking "if I make it a switch, it'll be the same time no matter how many cases I have" -- and that's completely false. Even with a jump table you get the indirect jump cost and you pay for entries in the table for each case; and memory bandwidth is a Big Deal on modern hardware.

Write code for readability. Any compiler worth its salt is going to see an if / else if ladder and transform it into equivalent switch or vice versa if it would be faster to do so.

---

To your question:

1.What would a basic jump table look like, in x86 or x64?

Jump table is memory address that holds pointer to the labels in something like array structure. following example will help you understand how jump tables are laid out

00B14538  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00  Ø.«.Ø.«.Ø.«.Ø.«.
00B14548  D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 00 00 00 00  Ø.«.Ø.«.Ø.«.....
00B14558  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
00B14568  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

https://i.stack.imgur.com/RTTwM.png

Where 00B14538 is the pointer to the Jump table , and value like D8 09 AB 00 represents label pointer.

2.Is this code using a jump table? No in this case.

3.Why is there no performance difference in this example?

There is no performance difference because instruction for both case looks same, no jump table.

4.Is there any situation in which there is a significant performance difference?

If you have very long sequence of if check, in that case using a jump table improves performance (branching/jmp instructions are expensive if they don't predict near-perfectly) but comes with the cost of memory.

The code for all the compare instructions has some size, too, so especially with 32-bit pointers or offsets, a single jump table lookup might not cost a lot more size in an executable.

Conclusion: Compiler is smart enough handle such case and generate appropriate instructions :)

---

The compiler is free to compile the switch statement as a code which is equivalent to if-statement, or to create a jump table. It will likely chose one on the other based on what will execute fastest or generate the smallest code somewhat depending on what you have specified in you compiler options -- so worst case it will be the same speed as if-statements

I would trust the compiler to do the best choice and focus on what makes the code most readable.

If the number of cases becomes very large a jump table will be much faster than a series of if. However if the steps between the values is very large, then the jump table can become large, and the compiler may choose not to generate one.

---

How do you know your computer was not performing some task unrelated to the test during the switch test loop and performing fewer tasks during the if test loop? Your test results do not show anything as:

the difference is very small there is only one result, not a series of results there are too few cases

My results:

I addded:

printf("counter: %u\n", counter);

to the end so that it would not optimise away the loop as counter was never used in your example so why would the compiler perform the loop? Immediately, the switch was always winning even with such a micro-benchmark.

The other problem with your code is:

switch (counter % 4 + 1)

in your switch loop, versus

const size_t c = counter % 4 + 1; 

in your if loop. Very big difference if you fix that. I believe that putting the statement inside the switch statement provokes the compiler into sending the value directly into the CPU registers rather than putting it on the stack first. This is therefore in favour of the switch statement and not a balanced test.

Oh and I think you should also reset counter between tests. In fact, you probably should be using some kind of random number instead of +1, +2, +3 etc, as it will probably optimise something there. By random number, I mean a number based on the current time, for example. Otherwise, the compiler could turn both of your functions into one long math operation and not even bother with any loops.

I have modified Ryan's code just enough to make sure the compiler couldn't figure things out before the code had run:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_COUNT (1 << 26)
size_t counter = 0;

long long testSwitch()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;

        switch (c)
        {
                case 1: counter += 20; break;
                case 2: counter += 33; break;
                case 3: counter += 62; break;
                case 4: counter += 15; break;
                case 5: counter += 416; break;
                case 6: counter += 3545; break;
                case 7: counter += 23; break;
                case 8: counter += 81; break;
                case 9: counter += 256; break;
                case 10: counter += 15865; break;
                case 11: counter += 3234; break;
                case 12: counter += 22345; break;
                case 13: counter += 1242; break;
                case 14: counter += 12341; break;
                case 15: counter += 41; break;
                case 16: counter += 34321; break;
                case 17: counter += 232; break;
                case 18: counter += 144231; break;
                case 19: counter += 32; break;
                case 20: counter += 1231; break;
        }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

long long testIf()
{
    clock_t start = clock();
    size_t i;
    for (i = 0; i < MAX_COUNT; i++)
    {
        const size_t c = rand() % 20 + 1;
        if (c == 1) { counter += 20; }
        else if (c == 2) { counter += 33; }
        else if (c == 3) { counter += 62; }
        else if (c == 4) { counter += 15; }
        else if (c == 5) { counter += 416; }
        else if (c == 6) { counter += 3545; }
        else if (c == 7) { counter += 23; }
        else if (c == 8) { counter += 81; }
        else if (c == 9) { counter += 256; }
        else if (c == 10) { counter += 15865; }
        else if (c == 11) { counter += 3234; }
        else if (c == 12) { counter += 22345; }
        else if (c == 13) { counter += 1242; }
        else if (c == 14) { counter += 12341; }
        else if (c == 15) { counter += 41; }
        else if (c == 16) { counter += 34321; }
        else if (c == 17) { counter += 232; }
        else if (c == 18) { counter += 144231; }
        else if (c == 19) { counter += 32; }
        else if (c == 20) { counter += 1231; }
    }
    return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}

int main()
{
    srand(time(NULL));
    printf("Starting...\n");
    printf("Switch statement: %lld ms\n", testSwitch()); fflush(stdout);
    printf("counter: %d\n", counter);
    counter = 0;
    srand(time(NULL));
    printf("If     statement: %lld ms\n", testIf()); fflush(stdout);
    printf("counter: %d\n", counter);
} 

switch: 3740 if: 3980

(similar results over multiple attempts)

I also reduced the number of cases/ifs to 5 and the switch function still won.

---

A good optimizing compiler such as MSVC can generate:

a simple jump table if the cases are arranged in a nice long range a sparse (two-level) jump table if there are many gaps a series of ifs if the number of cases is small or the values are not close together a combination of above if the cases represent several groups of closely-spaced ranges.

In short, if the switch looks to be slower than a series of ifs, the compiler might just convert it to one. And it's likely to be not just a sequence of comparisons for each case, but a binary search tree. See here for an example.

---

Here are some results from the old (now hard to find) bench++ benchmark:

Test Name:   F000003                         Class Name:  Style
CPU Time:       0.781  nanoseconds           plus or minus     0.0715
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way if/else if statement
 compare this test with F000004

Test Name:   F000004                         Class Name:  Style
CPU Time:        1.53  nanoseconds           plus or minus     0.0767
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way switch statement
 compare this test with F000003

Test Name:   F000005                         Class Name:  Style
CPU Time:        7.70  nanoseconds           plus or minus      0.385
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way if/else if statement
 compare this test with F000006

Test Name:   F000006                         Class Name:  Style
CPU Time:        2.00  nanoseconds           plus or minus     0.0999
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way switch statement
 compare this test with F000005

Test Name:   F000007                         Class Name:  Style
CPU Time:        3.41  nanoseconds           plus or minus      0.171
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way sparse switch statement
 compare this test with F000005 and F000006

What we can see from this is that (on this machine, with this compiler -- VC++ 9.0 x64), each if test takes about 0.7 nanoseconds. As the number of tests goes up, the time scales almost perfectly linearly.

With the switch statement, there's almost no difference in speed between a 2-way and a 10-way test, as long as the values are dense. The 10-way test with sparse values takes about 1.6x as much time as the 10-way test with dense values -- but even with sparse values, still better than twice the speed of a 10-way if/else if.

Bottom line: using only a 4-way test won't really show you much about the performance of switch vs if/else. If you look at the numbers from this code, it's pretty easy to interpolate the fact that for a 4-way test, we'd expect the two to produce pretty similar results (~2.8 nanoseconds for an if/else, ~2.0 for switch).

---

I'll answer 2) and make some general comments. 2) No, there is no jump table in the assembly code you've posted. A jump table is a table of jump destinations, and one or two instructions to jump directly to an indexed location from the table. A jump table would make more sense when there are many possible switch destinations. Maybe the optimiser knows that simple if else logic is faster unless the number of destinations is greater than some threshold. Try your example again with say 20 possibilities instead of 4.

---

I was intrigued, and took a look at what I could change about your example to get it to run the switch statement faster.

If you get to 40 if statements, and add a 0 case, then the if block will run slower than the equivalent switch statement. I have the results here: https://www.ideone.com/KZeCz.

The effect of removing the 0 case can be seen here: https://www.ideone.com/LFnrX.

---

Note that when a switch is NOT compiled to a jump table, you can very often write if's more efficiently than the switch...

(1) if the cases have an ordering, rather than the worst case testing for all N, you can write your if's to test if in the upper or lower half, then in each half of that, binary search style... resulting in the worst case being logN rather than N

(2) if certain cases/groups are far more frequent than other cases, then designing your if's to isolate those cases first can speed up the average time through

---

No these are if then jump else if then jump else...A jump table would have a table of addresses or use a hash or something like that.

Faster or slower is subjective. You could for example have case 1 be the last thing instead of first and if your test program or real world program used case 1 most of the time the code would be slower with this implementation. So just re-arranging the case list, depending on the implementation, can make a big difference.

If you had used cases 0-3 instead of 1-4 the compiler might have used a jump table, the compiler should have figured out removing your +1 anyway. Perhaps it was the small number of items. Had you made it 0 - 15 or 0 - 31 for example it may have implemented it with a table or used some other shortcut. The compiler is free to choose how it implements things so long as it meets the functionality of the source code. And this gets into compiler differences and version differences and optimization differences. If you want a jump table, make a jump table, if you want an if-then-else tree make an if-then-else tree. If you want the compiler to decide, use a switch/case statement.

---

Not sure why one is faster and one is slower, though.

That is actually not too hard to explain... If you remember that mispredicted branches are tens to hundreds of times more expensive than correctly predicted branches.

In the % 20 version, the first case/if is always the one that hits. Modern CPUs "learn" which branches are usually taken and which are not, so they can easily predict how this branch will behave on almost every iteration of the loop. That explains why the "if" version flies; it never has to execute anything past the first test, and it (correctly) predicts the result of that test for most of the iterations. Obviously the "switch" is implemented slightly differently -- perhaps even a jump table, which can be slow thanks to the computed branch.

In the % 21 version, the branches are essentially random. So not only do many of them execute every iteration, the CPU cannot guess which way they will go. This is the case where a jump table (or other "switch" optimization) is likely to help.

It is very hard to predict how a piece of code is going to perform with a modern compiler and CPU, and it gets harder with every generation. The best advice is "don't even bother trying; always profile". That advice gets better -- and the set of people who can ignore it successfully gets smaller -- every year.

All of which is to say that my explanation above is largely a guess. :-)

---

None. In most particular cases where you go into the assembler and do real measurements of performance your question is simply the wrong one. For the given example your thinking goes definitively too short since

counter += (4 - counter % 4);

looks to me to be the correct increment expression that you should be using.

---