Switch seems slower than if

Question

I was curious as to the speed on switch, believing that it was "very" fast, but I have a test case that seems to show a single switch is about as fast as about 4 if tests, when I expected (no solid reason) it to be as fast as 1 test. Here's the two methods I wrote to compare switch with if:

public static int useSwitch(int i) {
    switch (i) {
        case 1: return 2;
        case 2: return 3;
        case 3: return 4;
        case 4: return 5;
        case 5: return 6;
        case 6: return 7;
        default: return 0;
    }
}

public static int useIf(int i) {
    if (i == 1) return 2;
    if (i == 2) return 3;
    if (i == 3) return 4;
    if (i == 4) return 5;
    if (i == 5) return 6;
    if (i == 6) return 7;
    return 0;
}

Here's my testing code:

long x = 0;
for (int i = 0; i < 999999; i++)
    x += useIf(i % 7); // I use "x" so calls won't get optimized out

And another identical loop for useSwitch()

On my machine these loops take about the same time to complete, which was a surprise.
I arrived at the number of ifs as "4", because that's the average given the input range (I think).
If I reduce the number of logic options, the if version is noticeably faster.

My question is:

Is it that switch actually isn't that fast, or is this an "unfair" test in some way?

This link may be helpful- http://stackoverflow.com/questions/680656/what-is-the-difference-between-if-else-and-switch — Avinash T., Dec 30 '12 at 06:42
How are you measuring the time? Are you running in -server mode? Your test is most likely meaningless. — Diego Basch, Dec 30 '12 at 06:47
This is probably unfair. Most of the CPU time will be spent processing the modulo (%), which would obscure any difference you'd see in the switch vs if(). Try using i % 8 instead... the JVM might optimize that into its bitwise mask equivalent of i & ~7 — jstine, Dec 30 '12 at 07:16
I know that my answer does not answer your question, but in your case you may optimize your code (i see that you are looking for optimization performance) by holding and array of int's or (enum), whereas the index of the array is the key-> your function will be return arr[index] — Michael, Dec 30 '12 at 11:59
@Michael thanks but this code has no use for me other than to test switch speed. There is no useful application for it. — Bohemian, Dec 30 '12 at 19:24

score 15 · Accepted Answer · answered Dec 30 '12 at 07:30

This is an unfair comparison to some extent. Most of the CPU time will be spent processing the modulo operation: i % 7. Modulo even on latest greatest CPUs is extremely slow and probably takes 20x longer to execute than either the if() or switch() implementations you're trying to benchmark.

Furthermore, there are two different ways that switch statements can be optimized. One is by lookup table, which is used in sequential cases like the one you've put forth. The other way is by using search partition trees, where appropriate. This happens when the cases are sparse, such as in the following example:

switch (someInt) {
    case 0:  ... break;
    case 10:  ... break;
    case 102:  ... break;
    case 6543:  ... break;
    case 19303:  ... break;
    case 19305:  ... break;
    // and so forth...
}

Most compilers will use an unrolled partition tree to find the correct case, which on long switches gives very good avg and worst-case jumps needed to hit the right one. The resulting pseudo-code would be something like this:

if (someInt >= 6543) {
    if (someInt >= 19303) {
        // continue tree search, etc.
    }
    else if (someInt==6543) {}
}
else if (someInt >= 0) {
    if (someInt >= 10) {
        // continue tree search, etc.
    }
    else if (someInt == 0) {} 
}
else {
    // default case handler...
}

It doesn't really help much with just 6-8 cases as shown here, but if you had a switch with perhaps 50+ cases then it can be really helpful. A linear search would have O(n) (50 conditions worst, 25 avg), while the partition tree version would be close to sqrt(n) (8-9 conditions worst, 5-7 avg, depending on compiler choices).

Evgeniy Dorofeev · Answer 2 · 2012-12-30T07:14:02.603

5

Switch is supposed to be faster, it's enough to look at the bytecode

   TABLESWITCH
      1: L1
      2: L2
      3: L3
      4: L4
      5: L5
      6: L6

to see that it is a special operation. In real life there may be no difference because of JVM optimizations. But if we run your code with -Xint (interepret only mode) then the difference should be evident, on my PC it is 63 to 93 (ms) in favour of switch.

edited Dec 30 '12 at 07:14

answered Dec 30 '12 at 07:02

Evgeniy Dorofeev

133,369
30
199
275

TheZuck · Answer 3 · 2012-12-30T07:10:44.907

The interesting question here is how the compiler translates switch (might be like a hash table or the results can be similar to an if-else structure). It can also do all kinds of optimizations based on the input (if it's known). However, this is compiler dependent and is not defined in any spec I'm aware of.

So, I can't give you the answer, but I can tell you that if you want to refine your test even more you can always give it an input of 7. This will make it go through all of the tests until returning an answer, and if the switch is optimized it will give you better results, if it's just like an if-else it will have similar results. Just don't hard code the 7 so that the compiler doesn't know it ahead of time, use something like parseint to get it from a string.

score 1 · Answer 4 · answered Dec 30 '12 at 11:49

As you have code which may or may not be eliminated based on how smart the JIT is, you may have determined that the if statements are easier to eliminate than a switch. This is not surprising as many if statements are more likely to be eliminated e.g. assertions and debug checks.

Switch seems slower than if

4 Answers4

Linked