switch and many case's. Any caveats?

[Test]

I am using a (some pseudo code):
switch (i)
{
case 1:
...
case 2:
...
...
case 249:
...
case 250:
...
}

where I have a couple hundred case's. Does this degrade performance and if so
what would a better way?

 

[Kleuske]

I am using a (some pseudo code):
switch (i)
{
case 1:
...
case 2:
...
...
case 249:
...
case 250:
...
}

where I have a couple hundred case's. Does this degrade performance and if so
what would a better way?

It _may_ degrade performance, but that's only a headache if it's in some
critical section and not the main issue. Constructs like that _do_ degrade
readability and hence maintainability. Maybe lookup-tables and/or
pointers-to-function may improve your code, but it's impossible to tell
w/o more detail.

Using numbers as case-labels is almost always a bad idea. #define something
understandable instead.

 

[jgharston]

where I have a couple hundred case's.

The plural of case is cases.
cat cats, dog dogs, table tables, tree trees, fire fires, case cases.

JGH

 

[Eric Sosman]

I am using a (some pseudo code):
switch (i)
{
case 1:
...
case 2:
...
...
case 249:
...
case 250:
...
}

where I have a couple hundred case's. Does this degrade performance and if so
what would a better way?

The original ANSI "C90" Standard required compilers to support at
least 257 case labels per switch, and the "C99" revision raised the
limit to 1023. So with "a couple hundred" cases you're safe, but with
"several hundred" you might get into trouble with C90 compilers. (A
particular C90 compiler may allow more than 257 cases, but the Standard
does not require all C90 compilers to do so.)

As for performance, you'll need to investigate on your own, most
likely by measurement. Realize that the results of the investigation
are not necessarily applicable to other machines, other compilers, or
even the same machine and compiler under different circumstances than
exactly what was measured. It is likely (but by no means certain) that
if the case numbers are "dense" and have few gaps, the performance for
large-N and moderate-N will be similar.

Finally, "a better way" depends quite a lot on the nature of what
you're doing. If your couple hundred cases are all doing similar
things, perhaps there's a way to parameterize the differences between
the cases and use an array of a couple hundred parameter values. Or
maybe you need an array of function pointers. Or maybe you need a
switch with a lot of cases -- it's hard to tell.

Consider also the matter of maintenance: If you expect to tinker
with the cases a lot, the notion of "better" should probably include
some thought for making the tinkering easier and error-resistant. You
do *not* want to edit a thousand-case switch to change the behavior of
case 426, recompile, test, and discover that you mistakenly changed
462 instead ...

 

[Rui Maciel]

Using numbers as case-labels is almost always a bad idea. #define
something understandable instead.

Enums also work quite nicely, as the compiler is able to perform some sanity
checks.


Rui Maciel

 

[Andrew Smallshaw]

Using numbers as case-labels is almost always a bad idea. #define something
understandable instead.

In a complex case such as this I tend to find them more manageable:
I can't comment as to the OP's code but in my experience large
switches are usually the result of implementing a complex FSM. If
you have 250 states each one probably represents some form of
intersection between a dozen or more variables and creating meaningful
names for them all that a remotely suitable for use as manifest
constant or enumerated values is a complete non-starter.

What would you call the state "output buffer is full, input buffer
has been partially processed, a timeout occurred in the last
iteration of processing, a peer system has posted some changes to
the data that need to be accounted for, and the string holding the
furry dice has snapped"?

The notes designing this code are simply going to refer to it as
"state 247". If code can't be self-documenting then at least you
want a one-to-one correspondence beween your design notes and the
code. You can always summarise the essential conditions for a
particular case in comments if you want. You can also make a case
that the FSM needs simplification but that is a wider structural
issue that may or may not be appropriate in a given context.

Returning to the OP's question my opinion tends to be "don't worry
about it" for things like this. With modern optimising compilers
you really have no idea what code is going to be generated and
attempting to second-guess them is waste of time. If it's idenfied
as a problem you can always break it up in some manner, e.g:

switch (i >> 4) {

case 0:
switch (i & 15) {
...
}

....

}

However, my default position would be not to bother until and unless
that code is actually identified as problematic, especially if the
different cases are largely or entirely sequential in nature.

 

[Paul N]

I am using a (some pseudo code):
switch (i)
   {
   case 1:
    ...
   case 2:
    ...
    ...
   case 249:
   ...
   case 250:
   ...
   }

where I have a couple hundred case's. Does this degrade performance and if so
what would a better way?

I was under the impression that switches were good - you are telling
the compiler clearly what you want, and it can choose the best way of
implementing it itself.

If you can be confident that i is in the range 1-250, and can't find a
way of telling the compiler this, then an array as suggested by
William Ahern might be slightly quicker. Though it might not be worth
the hit to readability and maintainability.

 

[Malcolm McLean]

בת×ריך ×™×•× ×©×œ×™×©×™, 8 במ××™ 2012 19:50:51 UTC+1, מ×ת Test:

I am using a (some pseudo code):
switch (i)
where I have a couple hundred case's. Does this degrade performance and if so
what would a better way?

It could well.
It's to be hoped that the compiler produces a jump table for such a long switch. But you can't control that. Switches in inner loops often degrade performance, for instance the switch on the instruction opcode really hammers a C Java Virtual Machine.
There's no one answer. If there was, there wouldn't be a problem, because the compiler would implement it.

Are the labels contiguous? That nake it easier for the compiler to build the jump table.
Are all cases equally likely, or do you have a titles type distribution - thousands of Mr's, about a third Miss, Mrs and Ms, a sprinkling of Drs and Revs, and then a few very rare Profs, Lords, Sirs, His Divine Grace's and soon. In that case, you can possibly speed things up by a if() to filter outthe common cases.
Then you can often implement a structured search. Instead of an if else ladder, you have a binary search. Of course there's no point in simply doing abinary search on the case labels, because if that was the fastest way to switch the compler would already do it. You need to apply knowledge about the distribution of labels to make the likely branches more likely to be taken (the processor probably assumes that an if will be taken, and so piplinesit, so you arrnage the common cases to be true. But you really need to look at the assembly.)


But there's no easy answer. None of this will necessarily work. Inherently switching is a rather slow operation.

 

[Jianjun Mao]

1. Using function array to implement this. Every state maps to a function, then store this function into an array named func_arr[N]. And you can call the function like this: func_arr[state](...).

2. In my point of view, hundreds of cases will not degrade the performance because of the high speed CPU, and many application are implemented in this way, such as: lex and yacc.

 

[Guest]

In a complex case such as this I tend to find them more manageable:
I can't comment as to the OP's code but in my experience large
switches are usually the result of implementing a complex FSM. If
you have 250 states each one probably represents some form of
intersection between a dozen or more variables and creating meaningful
names for them all that a remotely suitable for use as manifest
constant or enumerated values is a complete non-starter.

I'd argue it might be time to consider partitioning your SM when it's got 250 states. I've seen large SMs that made sense but if I recall correctly itwas the events that exploded (one event for every character maybe?). It was interfacing to Telex so that was a *long* time ago!

What would you call the state "output buffer is full, input buffer
has been partially processed, a timeout occurred in the last
iteration of processing, a peer system has posted some changes to
the data that need to be accounted for, and the string holding the
furry dice has snapped"?

poor design!

The notes designing this code are simply going to refer to it as
"state 247". If code can't be self-documenting then at least you
want a one-to-one correspondence beween your design notes and the
code. You can always summarise the essential conditions for a
particular case in comments if you want. You can also make a case
that the FSM needs simplification but that is a wider structural
issue that may or may not be appropriate in a given context.

<snip>

 

[Joe keane]

switch (i)
{
case 1:
...
case 2:
...
...
case 249:
...
case 250:
...
}

If this is really what you want to do, i think that's the best way to
write the code.

It would help if you could explain a bit why there are two hundred
cases. I have seen code where there are a couple dozen cases, and i
thought trying to 'modularize' it would result in code that is less
readable and probably slower.

 

[Quentin Pope]

The original ANSI "C90" Standard required compilers to support at
least 257 case labels per switch, and the "C99" revision raised the
limit to 1023. So with "a couple hundred" cases you're safe, but with
"several hundred" you might get into trouble with C90 compilers. (A
particular C90 compiler may allow more than 257 cases, but the Standard
does not require all C90 compilers to do so.)

I believe the requirement is that it must accept *at least one*
conforming program with this number of case labels, so there is no
guarantee you're safe for any particular program.

 

[Tim Rentsch]

The plural of case is cases.
cat cats, dog dogs, table tables, tree trees, fire fires, case cases.

I believe the usage is defensible, to distinguish between
"case" as an English word and 'case' as a C keyword. So
for example

switch(n%10){
case 0:
case 1: x = 0; break;

case 2:
case 3:
case 5:
case 7: x = 1; break;

case 4:
case 6:
case 8:
case 9: x = 3; break;

}

There are three cases, but 10 case's.

 

[Tim Rentsch]

I believe the requirement is that it must accept *at least one*
conforming program with this number of case labels, so there is no
guarantee you're safe for any particular program.

Not exactly. The Standard requires conforming implementations
to accept any strictly conforming program. A program that is
strictly conforming in all other regards, and also uses no more
than 1023 case labels in any switch() statement, is strictly
conforming and so must be accepted by any conforming implementation.

 

[Quentin Pope]

Not exactly. The Standard requires conforming implementations to accept
any strictly conforming program. A program that is strictly conforming
in all other regards, and also uses no more than 1023 case labels in any
switch() statement, is strictly conforming and so must be accepted by
any conforming implementation.

5.2.4.1
"The implementation shall be able to translate and execute at least one
program that contains at least one instance of every one of the following
limits: ..."

This is quite a weak guarantee.

 

[James Kuyper]

5.2.4.1
"The implementation shall be able to translate and execute at least one
program that contains at least one instance of every one of the following
limits: ..."

This is quite a weak guarantee.

True, but that's not the promise Tim is talking about. 4p6 says "A
conforming hosted implementation shall accept any strictly conforming
program." Depending upon how "accept" is defined, that could be a very
strong guarantee, making up for the weakness of 5.2.4.1 - but the
standard fails to define "accept".

Some people have argued that "accept" must be equivalent to "translate
and execute". However, if that were the case, there would be no such
thing as a conforming implementation, because it's a relatively
straightforward task to describe a strictly conforming program that will
exceed the capacity of any particular implementation to handle it.
5.2.4.1 doesn't place any limits, explicit or implicit, on the total
size of a program, whether measured in terms of characters of source
code or in terms of tokens after phase 4 is complete. There's not many
implementations out there, if any, which could accept, in that sense, a
strictly conforming but arbitrarily long program with non-trivial
semantics that met every upper limit listed in 5.2.4.1 - not just once,
like the "one program", but at every possible opportunity.

Creating such a program would be more of a problem than describing it.
Any program which is too complex for a C implementation to parse, is
probably going to be very difficult to generate, too.

The ordinary English usage of "accept" allows me to say that I've
accepted a gift as long as I took it from the hands of the giver and
thanked that person for the gift, even if I never opened the gift, and
threw it away as soon as the giver was out of sight. Similarly, consider
a system which:

1. Always issues a diagnostic message saying "Your program may contain
defects" to satisfy 5.1.1.3p1.
2. Parses the program though phases 1-4 to determine whether any #error
directive survived conditional processing. If so, it issues the
specified error message, satisfying 6.10p5, and does nothing else with
it, satisfying 4p4. Otherwise, it issues a message saying "program
accepted", satisfying 4p6.
3. Checks to see whether the program is an exact match for the "one
program" mentioned in 5.2.4.1, and if so, translates and executes it
correctly. Otherwise, it does nothing more with it.

I contend that such a system could conform to all of the actual
requirements of the C99 standard (rather than the intended requirements,
which I gather were a bit stronger). C2011 seems to contain all of the
same weasel wording that allowed this to be a conforming C99
implementation, but I haven't had time to study it in detail to be sure
about that.

 

[Nobody]

5.2.4.1
"The implementation shall be able to translate and execute at least one
program that contains at least one instance of every one of the following
limits: ..."

This is quite a weak guarantee.

AIUI, the intent is to avoid requiring an implementation to handle the
worst-case combinations of limits, e.g. a structure having 1023 members, each of
which is a structure having 1023 members, and so on, nested to 63 levels
(i.e. 1023^63 members in total), or a function with 127 parameters, each
of which has such a pathological structure as its type.

IOW, if the implementation has fixed limits, they can't be any lower than
the values specified, but it doesn't have to support every possible
combination of those limits.

 

[Guest]

I believe the usage is defensible, to distinguish between
"case" as an English word and 'case' as a C keyword. So
for example

switch(n%10){
case 0:
case 1: x = 0; break;

case 2:
case 3:
case 5:
case 7: x = 1; break;

case 4:
case 6:
case 8:
case 9: x = 3; break;

}

There are three cases, but 10 case's.

why would this be made such an unusual exception to normal english usage?

 

[Tim Rentsch]

5.2.4.1
"The implementation shall be able to translate and execute at least one
program that contains at least one instance of every one of the following
limits: ..."

I'm familiar with 5.2.4.1. It doesn't change the point I was
making, namely, that your claim about what the requirements are
for what implementations must accept is wrong.

This is quite a weak guarantee.

It is neither a weak guarantee nor a strong guarantee, because it
is not a guarantee. This sentence, along with almost every other
sentence in the Standard, is simply part of the definition of what
constitutes a conforming implementation of ISO C. Definitions
don't make promises; they are just definitions.

 

[88888 Dihedral]

Tim Rentschæ–¼ 2012å¹´5月11日星期五UTC+8上åˆ12時52分26秒寫é“：

I believe the usage is defensible, to distinguish between
"case" as an English word and 'case' as a C keyword. So
for example

switch(n%10){
case 0:
case 1: x = 0; break;

case 2:
case 3:
case 5:
case 7: x = 1; break;

case 4:
case 6:
case 8:
case 9: x = 3; break;

}

There are three cases, but 10 case's

I suggest you can use the following method to speed up!

s=1<<n; //

if (s&(1|2)) { ..... // case 0 or 1 }
else if (s&(4|8|32|128)) { ....// case 2,3,5,7 }
else if (s&(16|64|256|512)){ ... // };