Re: switch case and efficiency

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

Martijn Mulder wrote:
I have well over a thousend cases after a switch.

Then you may have a design issue, and a possible maintenance issue. I do hope that file is machine generated. Even so, see if there's a more compact way. Are all the case statements unique, with no opportunity for generalization?

1. Is there a practical limit to the number of cases?

I honestly don't know. When your compiler times out, eats up too much memory or crashes with an internal error, you've probably hit it. This is the most likely case. It would also be possible for the CLR to hit the limit as it's loading or JIT-compiling your code, but this seems less likely.

There are no relevant theoretical upper limits. If we assume that the switch is always implemented with a jump table (i.e. there is no opportunity for optimizing it further by rewriting the case blocks) then it can't have more than 4 294 967 295 cases, but this will hardly be the limiting factor in any case (for starters, the table alone would take up 16 GiB). And even then there's no rule that it has to be implemented like this.

This is one of those "if you have to ask, it's probably time to rethink your solution" kind of limits.

2. Can I optimize (and uglify) my code so that switch-case runs faster?

There is no *general* way to optimize a switch, it's already the purest expression of "if this, then that". Depending on the specifics (what you're doing in every case block, what values you're using for both switch and cases and what the compiler/runtime are doing) it may be possible to optimize it. For example, you could replace it with something else altogether, like a hashtable and a general function.

3. How is switch implemented (binary search, linear search...)?

It depends on the compiler, the CLR and the specific statement.

The compiler may choose to emit a series of compares and jumps (likely if the switches are wildly disparate), or it may emit a switch opcode (if the switches are consecutive) or a combination of these. That's just what Microsoft's current C# compiler does, mind you -- certainly nothing prohibits the compiler from, say, generating a minimal perfect hash function and using that to index a jump table. (Which, incidentally, is another possible way of optimizing your switch by replacing it with something else.)

These opcodes may in turn be compiled by the CLR in whatever way it chooses. I'm not aware of any guarantee on the efficiency of the switch statement, and the CIL specification certainly doesn't mandate one. The switch opcode (which requires consecutive, zero-based values) is almost certainly implemented as an indexed jump, as there's no general way to do it better. The CLR may or may not recognize a series of compares-and-jumps as a high-level switch statement and optimize accordingly.

In short: if you're that interested in efficiency, profile.

--
J.
.

Relevant Pages

  • Re: Optimizing a switch statement
    ... > his switch statement, he omits a case for '5': ... > The case selectors are not contiguous in the above ... compilers that introduce jump tables, but I've not personally seen one. ... If the compiler is smart enough to generate a jump table, ...
    (comp.lang.cpp)
  • Re: Extremely easy question about Time to check table look-ups
    ... i create a simple 100x100 table called A, with "switch" statements ... Not stupid if there is no other way to do it. ... the simple jump table would would be too big to be practical. ... You'll have to inspect the compiler output. ...
    (comp.programming)
  • Re: switch and if..else same at assemby code ?
    ... Some processors have specialized instructions for jump tables. ... uniform assembly language, there is a lot of dependency on the processor ... There is also a lot of variance left for the compiler writer. ... Some may automatically convert a switch statement into a jump ...
    (comp.lang.c)
  • Re: The Lisp Curse
    ... If a switch() has less than three sections, then, yes, some do ... convert that to if-then code instead of a jump table. ... code as CMP/JMP sequences. ... I've not seen a C compiler not output a jump ...
    (comp.lang.forth)
  • Re: DPROD issues
    ... a switch like that typically ... makes a compiler nonstandard in that mode. ... treatment of specific intrinsics is one ... subroutine sub1a ...
    (comp.lang.fortran)