Why switch is faster than if

Question

Lots of Java books describe the switch statement as being faster than the if else statement. But I did not find out anywhere why switch is faster than if.

Example

I have a situation I have to choose any one item out of two. I can use either use

switch (item) {
    case BREAD:
        //eat Bread
        break;
    default:
        //leave the restaurant
}

or

if (item == BREAD) {
    //eat Bread
} else {
    //leave the restaurant
}

considering item and BREAD is a constant int value.

In the above example which is faster in action and why?

Answer 1

Because there are special bytecodes that allow efficient switch statement evaluation when there are a lot of cases.

If implemented with IF-statements you would have a check, a jump to the next clause, a check, a jump to the next clause and so on. With switch the JVM loads the value to compare and iterates through the value table to find a match, which is faster in most cases.

Answer 2

A switch statement is not always faster than an if statement. It scales better than a long list of if-else statements as switch can perform a lookup based on all the values. However, for a short condition it won't be any faster and could be slower.

Answer 3

The current JVM has two kinds of switch byte codes: LookupSwitch and TableSwitch.

Each case in a switch statement has an integer offset, if these offsets are contiguous (or mostly contiguous with no large gaps) (case 0: case 1: case 2, etc.), then TableSwitch is used.

If the offsets are spread out with large gaps (case 0: case 400: case 93748:, etc.), then LookupSwitch is used.

The difference, in short, is that TableSwitch is done in constant time because each value within the range of possible values is given a specific byte-code offset. Thus, when you give the statement an offset of 3, it knows to jump ahead 3 to find the correct branch.

Lookup switch uses a binary search to find the correct code branch. This runs in O(log n) time, which is still good, but not the best.

For more information on this, see here: Difference between JVM's LookupSwitch and TableSwitch?

So as far as which one is fastest, use this approach: If you have 3 or more cases whose values are consecutive or nearly consecutive, always use a switch.

If you have 2 cases, use an if statement.

For any other situation, switch is most likely faster, but it's not guaranteed, since the binary-search in LookupSwitch could hit a bad scenario.

Also, keep in mind that the JVM will run JIT optimizations on if statements that will try to place the hottest branch first in the code. This is called "Branch Prediction". For more information on this, see here: https://dzone.com/articles/branch-prediction-in-java

Your experiences may vary. I don't know that the JVM doesn't run a similar optimization on LookupSwitch, but I've learned to trust the JIT optimizations and not try to outsmart the compiler.

Answer 4

So if you plan to have loads of packets memory isn't really a large cost these days and arrays are pretty fast. You also cannot rely on a switch statement to auto generate a jump table and as such it's easier to generate the jump table scenario yourself. As you can see in below example we assume a maximum of 255 packets.

To get the below result your need abstraction.. i'm not going to explain how that works so hopefully you have an understanding of that.

I updated this to set the packet size to 255 if you need more then that you'll have to do a bounds check for (id < 0) || (id > length).

Packets[] packets = new Packets[255];

static {
     packets[0] = new Login(6);
     packets[2] = new Logout(8);
     packets[4] = new GetMessage(1);
     packets[8] = new AddFriend(0);
     packets[11] = new JoinGroupChat(7); // etc... not going to finish.
}

public void handlePacket(IncomingData data)
{
    int id = data.readByte() & 0xFF; //Secure value to 0-255.

    if (packet[id] == null)
        return; //Leave if packet is unhandled.

    packets[id].execute(data);
}

Edit since I use a Jump Table in C++ a lot now i'll show an example of a function pointer jump table. This is a very generic example, but I did run it and it works correctly. Keep in mind you must set the pointer to NULL, C++ will not do this automatically like in Java.

#include <iostream>

struct Packet
{
    void(*execute)() = NULL;
};

Packet incoming_packet[255];
uint8_t test_value = 0;

void A() 
{ 
    std::cout << "I'm the 1st test.\n";
}

void B() 
{ 
    std::cout << "I'm the 2nd test.\n";
}

void Empty() 
{ 

}

void Update()
{
    if (incoming_packet[test_value].execute == NULL)
        return;

    incoming_packet[test_value].execute();
}

void InitializePackets()
{
    incoming_packet[0].execute = A;
    incoming_packet[2].execute = B;
    incoming_packet[6].execute = A;
    incoming_packet[9].execute = Empty;
}

int main()
{
    InitializePackets();

    for (int i = 0; i < 512; ++i)
    {
        Update();
        ++test_value;
    }
    system("pause");
    return 0;
}

Also another point i'd like to bring up is the famous Divide and Conquer. So my above 255 array idea could be reduced to no more then 8 if statements as a worst case scenario.

I.e. but keep in mind it get's messy and hard to manage fast and my other approach is generally better, but this is utilize in cases where arrays just won't cut it. You have to figure out your use case and when each situation works best. Just as you wouldn't want to use either of these approaches if you only have a few checks.

If (Value >= 128)
{
   if (Value >= 192)
   {
        if (Value >= 224)
        {
             if (Value >= 240)
             {
                  if (Value >= 248)
                  {
                      if (Value >= 252)
                      {
                          if (Value >= 254)
                          {
                              if (value == 255)
                              {

                              } else {

                              }
                          }
                      }
                  }
             }      
        }
   }
}

Answer 5

At the bytecode level, subject variable is loaded only once into processor register from a memory address in the structured .class file loaded by Runtime,and this is in a switch statement; whereas in an if-statement, a different jvm instruction is produced by your code-compiling DE, and this requires that each variable be loaded in to registers although same variable is used as in next preceeding if-statement. If you know of coding in assembly language then this would be commonplace; although java compiled coxes are not bytecode, or direct machine code, the conditional concept hereof is still consistent. Well, I tried to avoid deeper technicality upon explaining. I hope I had made the concept clear and demystified. Thank you.