Optimising Java switch statement with many cases?

Question

I am currently using a switch statement to handle types of incoming messages of which there are 20 or so different cases. Some of these cases are orders of magnitude more likely to occur than others.

Is the hotspot compiler able to optimise the order of examining cases to find the correct case to execute or should I structure my code so that the most common cases appear first:

switch(messageType)
{
    case MOST_COMMON:
        // handle it
        break;

...
    case LEAST_COMMON:
        // handle it
        break;
}

All cases are mutually exclusive.

Would I be better off using the strategy pattern and a Map lookup on message type?

Performance is the key concern as I am handling thousands of messages per second and am trying to cut down on object creation and method call overhead.

Many thanks,

Chris

Edit: Thanks for the pointers. messageType is an int with a tight range of values so it looks like it will compile to the "tableswitch" bytecode so no need to reorder the cases.

Relevant part of JVM spec is here http://java.sun.com/docs/books/jvms/second_edition/html/Compiling.doc.html#14942

IIRC most compilers handle `switch` statements in C and C++ with lookup tables. Java might do the same thing. But I could be wrong. — NullUserException, Nov 04 '11 at 14:56
possible duplicate of [Java: If vs. Switch](http://stackoverflow.com/questions/1061101/java-if-vs-switch) — Andy Thomas, Nov 04 '11 at 14:57
The JIT *should* optimize the path during execution. I'd profile both mechanisms to see for sure. — Dave Newton, Nov 04 '11 at 14:59
@Dave Newton - I'm looking at the content of both questions. The premise behind this question is a presumption that switch's are implemented as if/else chains. The prior question explains how they are actually implemented. — Andy Thomas, Nov 04 '11 at 15:18
possible duplicate of [Does switch case order affect speed?](http://stackoverflow.com/questions/23204580/does-switch-case-order-affect-speed) — Raedwald, Apr 26 '14 at 08:49

score 5 · Answer 1 · answered Nov 04 '11 at 14:57

5

If the cases are enum values or are densely distributed int values, then mucking with order won't help you once the JIT compiler kicks in to turn it all into a lookup table.

If you're using Java7 string switches or sparsely distributed values, then most common should go first since it turns into a cascading set of if-like test and branch operations.

answered Nov 04 '11 at 14:57

Mike Samuel

118,113
30
216
245

with java7 string switches it will be slower becuase it however turns into cascading 'if' like statements it will use 'equals' on eveluating strings – maks Nov 04 '11 at 15:12
Hi Mike, switch is on an int with a tight range of values so I think the answer is lookup table and no need to reorder the clauses. – ChrisWhoCodes Nov 04 '11 at 15:19
@maks, I think I agree. Are you trying to point me at a part of my answer that is wrong or just remarking on string switches in general? – Mike Samuel Nov 04 '11 at 16:29

score 4 · Accepted Answer · edited May 23 '17 at 12:14

4

Unless you are sure that this switch statement is causing you performance problems, then I would suggest that you're optimizing prematurely. Also, check out the accepted answer to this question.

edited May 23 '17 at 12:14

Community

1
1

answered Nov 04 '11 at 14:56

Mike

7,994
5
35
44

Hi Mike, point taken :) This code deals with a few hundred million events per working day and accounts for about 30% of the CPU cycles for the program. Just wanted an opinion on the JIT before diving into the JVM spec. – ChrisWhoCodes Nov 04 '11 at 15:18

score 2 · Answer 3 · answered Nov 04 '11 at 15:25

A switch statement is a perform a lookup to determine which block of code to jump to. It is not a series of if/else checks and the order the blocks are declared has no impact on performance. i.e. they are all case values are checked equally and at once.

A pseudo code it the same as (for a small int value range)

goto case_label[messageType.ordinal()];

For a large int value ranges a different table structure is used. (I assume its a hash table)

The CPU can use branch prediction and if one case is much more common that the others it can optimise execution dynamically.

Optimising Java switch statement with many cases?

3 Answers3

Linked