Does the order of case in Switch statement can vary the performance?

Question

Let say I have a switch statement as below

switch(alphabet) {

    case "f":
        //do something
        break;

    case "c":
        //do something
        break;

    case "a":
        //do something
        break;

    case "e":
        //do something
        break;

}

Now suppose I know that the frequency of having Alphabet e is highest followed by a, c and f respectively. So, I just restructured the case statement order and made them as follows:

switch(alphabet) {

    case "e":
        //do something
        break;

    case "a":
        //do something
        break;

    case "c":
        //do something
        break;

    case "f":
        //do something
        break;
}

Will the second switch statement be faster than the first switch statement? If yes and if in my program I need to call this switch statement say many times, will that be a substantial improvement? Or if not in any how can I use my frequency knowledge to improve the performance?

Answer 1

I think the way switch case do is it will loop over all the cases from top to bottom to find some match. If it matches, it stops there.

So, if you made changes to prioritize the frequency cases, the answer is yes, it can help somehow with performance. But I believe that it will not help much.

Answer 2

They have the same performance for a relatively small set of values. I tried checking the assembly code of C program before, the compiler creates a jump table out of all the values you have in your switch statement.

But if the case values are too many, it's a safe bet that they will degenerate to if else if, so putting your case 'E' on top would surely speed things up.

It's also applicable in C#, C# also produces a jump table for switch statements with a small set, albeit for adjacent values only. So it's O(1), there's no multiple testing even if the first values doesn't match.

Answer 3

Not so much that you should be concerned. It's certainly not something that can be predicted.

With string case labels, the compiler actually uses an internal hash table that maps the strings to indexes in a jump-table. So the operation is actually O(1) - independent of the number of labels.

For integer labels, then I believe the actual code that is generated depends on the number of labels and whether the numbers are consecutive (or "almost" consecutive). If they're consecutive (1, 2, 3, 4, ...) then they'll just be transformed into a jump table. If there's a lot of them, then the Hashtable+jump table (like with strings) will be used. If there's only a few labels and they're not table to be immediately transformed into a jump table, only then will be transformed into a series of if..then..else statements.

In general, though, you should write code so that you can read it, not so that the compiler can produce "faster" code.

(Note my description above is an implementation detail of how the C# compiler works internally: you shouldn't rely on it always working like that -- in fact, it might not even work exactly like that now, but at least it's the general idea).

Answer 4

It depends on how the compiler implements the switch statement.

First, you can't arbitrarily permute the order; if you have one case block in a C-like language (C, C++, C#, Java, ...), and that case block does not terminate in break, you can't rearrange the cases because the absence of the break means the compiler must implement fall-through to the next case. If we ignore this special situation, you can permute the rest of the cases.

If the number of cases is small, the compiler may implement the case tests by a sequences of compares. If the number of cases is modest, it may construct a balanced binary tree from the cases. If the number of cases is large, most compilers implement an indexed branch on the switch value if it is from a dense set. If parts of the set of case values is dense, and parts are not, the compiler may partition the cases into groups using a binary tree to select which dense set, and an indexed jump within the dense set. (In fact, the compiler may technically do anything that passes control to the appropriate case, but most often it is one of the above).

You can see that order may matter, or it may not, depending on how the compiler implements the switch. For most good compilers, it does not matter much.