Selecting code without switch(...)

[colin shuker]

Hi, this is a strange problem, but its annoying me.
I want to run a certain piece of code depending on a value.
I can clearly do this with if...else if...else if...else statements,
or with a switch statement like below:

switch(x)
{
   case 1  :Do code 1; break;
   case 2  :Do code 2; break;
   case 3  :Do code 3; break;
   case 4  :Do code 4; break;
   case 5  :Do code 5; break;
   case 6  :Do code 6; break;
   case 7  :Do code 7; break;
   case 8  :Do code 8; break;
   case 9  :Do code 9; break;
   case 10  :Do code 10; break;
}

But since I am making chess program, I need code to run as fast as
possible.
If code 10 had to be run, then all the cases 1 to 9 have to be checked.
I think thats equivalent to 9 if statements.

I was trying to do something like this.
Create an array of 'chunks' of code, so that you could just call
array[7] and get the code for 7 is executed.

But I can't just put code in an array, that wouldn't make sense.
Is there any way around this, so I can avoid a big switch statement??

Thanks for any help

[Andrew: disabled smilies in this post]
[ July 08, 2006: Message edited by: Andrew Monkhouse ]

[Ernest Friedman-Hill]

Define an interface "Handler", with a method "doIt()".

Write ten implementations of it, one for each case.

Make a HashMap, using Integers as the keys, and the Handler implementations as the values.

Instead of the switch, you write

((Handler) theMap.get(new Integer(x))).doIt();

Whether this is faster or not, it can be more elegant if the individual case statements are nontrivial.

Note, though, that a switch with contiguous indices is going to be compiled to a JVM "tableswitch" bytecode, which is going to look up the code to branch to using a binary search; it's already going to be far faster than the if-thens, although not necessarily as fast as the HashMap lookup.

[colin shuker]

Thanks, but I only have 5 or 6 if statements in my switch block.
And I've found out using collections /Maps does slow things down.
I guess if I had a 1000 blocks of code, it would be better.

So does switch work faster than multiple if's?
That is worth knowing

Thanks for your help
[ July 08, 2006: Message edited by: colin shuker ]

[Jim Yingst]

Since you're dealing with a very specific performance issue, I'm going to move this thread to the Performance forum. I would say that in general the switch statement is usually the last option to try, so I don't want the general readership to pick up the wrong message here (which is that for some high-performance applications, switch may be your best option).

[Jim Yingst]

Following up some more:

Comparing the performance of these options depends on a number of variables, especially: how many choices are there, and are the numeric values of the coices close together, or widely spaced? Most statements about speed which we might make here can turn out to be false in some other circumstances. However, in general, for a large number of options, if/elseif is pretty bad. A hashmap is usually much better, but a switch statement can often be faster yet (especially if the options are closely-spaced). However the fastest option may be to use an array instead:

private statid final Handler[] handlers = ...
 
void choose(int x) {
    if (x < 0 || x >= handlers.length)
        throw new IllegalArgumentException();
    Handler h = handlers[x];
    if (h == null)
        throw new IllegalArgumentException();
    h.doIt();
}

In some cases you can speed this further. If you are certain that this method is never called with an out-of-range value or a value for which h is null, you can skip those checks. This may well be the best option for you - I'd say it's worth a try.

Now if the number of choices is very small, the performance of a HashMap and the array solutions will probably remain exactly the same as above, but the if-else will get much better, maybe enough to justify using it. And the performance of the switch statement may improve, if the values are widely spaced. So for a very small number of choices, HashMap becomes the worst choice, and the other three are pretty close to each other. (Well, if/elseif doesn't become competitive until the nubmer of choices is two or maybe three.)

One minor advantage that the switch and (to a lesser extent) if/elseif have is that it's possible to in-line the method calls, manually or just letting the JVM do it. (I recommend the latter, as the JVM usually does a more reliable job.) In some situations this may be enough to make switch faster than an array.

With all of this, you really need to test the options yourself to find out for sure. And be aware that a different JVM on a different machine may give different results. However, for what you've described, I'm guessing best options are either a switch statement or an array.

[Andrew Monkhouse]

Just thought you might be interested in the bytecode that gets generated when you use if statements versus if you use case statements. For the class

public class SwitchVsIf {
    public static void main(String[] args) {
        int i = 3;
 
        if (i == 1) {
            doSomething(i);
        } else if (i == 2) {
            doSomething(i);
        } else if (i == 3) {
            doSomething(i);
        }
 
        switch (i) {
            case 1:
                doSomething(i);
                break;
            case 2:
                doSomething(i);
                break;
            case 3:
                doSomething(i);
                break;
        }
    }
 
    static void doSomething(int i) {
    }
}

We get:

$ javap -c SwitchVsIf
Compiled from "SwitchVsIf.java"
public class SwitchVsIf extends java.lang.Object{
public SwitchVsIf();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return
 
public static void main(java.lang.String[]);
  Code:
   0:   iconst_3
   1:   istore_1
   2:   iload_1
   3:   iconst_1
   4:   if_icmpne       14
   7:   iload_1
   8:   invokestatic    #2; //Method doSomething:(I)V
   11:  goto    35
   14:  iload_1
   15:  iconst_2
   16:  if_icmpne       26
   19:  iload_1
   20:  invokestatic    #2; //Method doSomething:(I)V
   23:  goto    35
   26:  iload_1
   27:  iconst_3
   28:  if_icmpne       35
   31:  iload_1
   32:  invokestatic    #2; //Method doSomething:(I)V
   35:  iload_1
   36:  tableswitch{ //1 to 3
                1: 64;
                2: 71;
                3: 78;
                default: 82 }
   64:  iload_1
   65:  invokestatic    #2; //Method doSomething:(I)V
   68:  goto    82
   71:  iload_1
   72:  invokestatic    #2; //Method doSomething:(I)V
   75:  goto    82
   78:  iload_1
   79:  invokestatic    #2; //Method doSomething:(I)V
   82:  return
 
static void doSomething(int);
  Code:
   0:   return
 
}

With i were set to 3, the if statement must first check that it is not equal to 1 and jump to line 14:

   2:   iload_1
   3:   iconst_1
   4:   if_icmpne       14

It then repeats that logic when it checks that i is not equal to 2 and jumps to line 26:

   14:  iload_1
   15:  iconst_2
   16:  if_icmpne       26

It can then do the real work (after verifying that i is equal to 3:

   26:  iload_1
   27:  iconst_3
   28:  if_icmpne       35
   31:  iload_1
   32:  invokestatic    #2; //Method doSomething:(I)V

Compare that with the switch statement, where a single instruction tells the java runtime what line it should execute next:

   35:  iload_1
   36:  tableswitch{ //1 to 3
                1: 64;
                2: 71;
                3: 78;
                default: 82 }

So having decided that i is equal to 3, we know that the next line to be run will be line 78:

   78:  iload_1
   79:  invokestatic    #2; //Method doSomething:(I)V
   82:  return

It is interesting to compare how Java handled the switch statement at a low level compared with Jim's solution where he is using an array. Java seems to be doing a lookup (possibly in an array) to work out what line number to run next.

Based on that I would expect the switch statement to be faster than the if statement, and probably comparable to Jim's solution.

Regards, Andrew

[steve souza]

This seems like premature optimization. HashMaps are very very fast. I would guess to the tune of millions of calls to get per second. How many times are you expecting to call this code?

[Jim Yingst]

[steve]: This seems like premature optimization. HashMaps are very very fast. I would guess to the tune of millions of calls to get per second. How many times are you expecting to call this code?

He did say he's actually seen it execute more slowly with a Map here. And it's a chessplaying program, so it's not hard to imagine that there's a very tight loop in there somewhere. Though it does bear asking, Colin: was the slowdown observed as part of the overall execution of the program, or were you isolating the HashMap/switch performance on its own? If the latter, then yes it's still very possible that the performance difference you've observed will not actually matter in context.

[Andrew]: It is interesting to compare how Java handled the switch statement at a low level compared with Jim's solution where he is using an array. Java seems to be doing a lookup (possibly in an array) to work out what line number to run next.

Yup. Probably not, strictly speaking, a Java array, but same idea. If the case values are widely spaced, then a switch can also compile to a lookupswitch statement, which is likely to require log N time to execute as the instruction requires a binary search of the table.

You may also want to check out the JVM Spec on Compiling Switches, as well as the tableswitch and lookupswitch commands.

[Andrew]: Based on that I would expect the switch statement to be faster than the if statement, and probably comparable to Jim's solution.

Ah, but that seems to assume that each instruction takes the same amount of time to execute. That's not necessarily the case. Executing tableswitch may well take a bit longer than iload, iconst, if_icmpne. Hard to say exactly. I ran some tests comparing execution times; it seems that with just 2 or 3 brances, switch and if/else are virtually indistinguishable in time. At 4 branches if/else starts to take noticeably longer, and of course this gets worse as the number of branches increases.