Hundreds of cases in a switch, optimization?

Discussion in 'C Programming' started by He Shiming, Jun 19, 2005.

  1. He Shiming

    He Shiming Guest

    Hi,

    I just wrote a function that has over 200 "cases" wrapped in a "switch"
    statement. I'm wondering if there are performance issues in such
    implementation. Do I need to optimize it some way?

    In terms of generated machine code, how does hundreds of cases in a switch
    differ from hundreds of if-elses? Do compilers or processors do any
    optimization on such structured code? Do I need to worry about the
    performance, usually?

    Thanks,
    --
    He Shiming
    He Shiming, Jun 19, 2005
    #1
    1. Advertising

  2. He Shiming

    Alawna Guest

    there should be no difference between if-elsses and switches in terms
    of performance. switches are only easier to read. ie, they produce
    identical machine code.
    by the way, i am talking from a pascal point of view but it should
    also apply to C . Waiting like you for C guys to answer.
    Alawna, Jun 19, 2005
    #2
    1. Advertising

  3. He Shiming

    He Shiming Guest

    Well, thanks for the information anyway.

    --
    He Shiming

    "Alawna" <> wrote in message
    news:...
    > there should be no difference between if-elsses and switches in terms
    > of performance. switches are only easier to read. ie, they produce
    > identical machine code.
    > by the way, i am talking from a pascal point of view but it should
    > also apply to C . Waiting like you for C guys to answer.
    >
    He Shiming, Jun 19, 2005
    #3
  4. He Shiming

    Minti Guest

    He Shiming (NOSPAM) wrote:
    > Hi,
    >
    > I just wrote a function that has over 200 "cases" wrapped in a "switch"
    > statement. I'm wondering if there are performance issues in such
    > implementation. Do I need to optimize it some way?
    >
    > In terms of generated machine code, how does hundreds of cases in a switch
    > differ from hundreds of if-elses? Do compilers or processors do any
    > optimization on such structured code? Do I need to worry about the
    > performance, usually?


    Well, try to write these hundreds of switch statements using if-else's
    and see if you have it easy that way.

    I have seen a lot of code with 100's of switch statements in many cases
    it is just not _possible_ to apply any other strategy. However, as far
    as performance is concerned try to keep the cases that you feel are
    most likely to occur at the beginning of the switch block.


    --
    Imanpreet Singh Arora
    Minti, Jun 19, 2005
    #4
  5. In article <d9300m$g5l$>,
    "He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote:

    > Hi,
    >
    > I just wrote a function that has over 200 "cases" wrapped in a "switch"
    > statement. I'm wondering if there are performance issues in such
    > implementation. Do I need to optimize it some way?


    How could I know? Does it run fast enough? Does anyone complain that it
    is too slow? Have you measured how long it takes?


    > In terms of generated machine code, how does hundreds of cases in a switch
    > differ from hundreds of if-elses? Do compilers or processors do any
    > optimization on such structured code? Do I need to worry about the
    > performance, usually?


    It is time to read the documentation for your compiler and find out how
    to show the assembler code that it produces. Find out, then have a look
    at the code.

    Since compilers are around over fourty years, there are the following
    possibilities:

    a. There is no way to do a switch statement of 200 cases faster than
    200 if's.
    b. It is possible to do a switch statement of 200 cases faster than
    200 if's, but compiler writers for the last 40 years have been too
    stupid or too lazy to implement it.
    c. It's done much faster, and has been done that way for years.

    Guess a, b or c.
    Christian Bau, Jun 19, 2005
    #5
  6. In article <>,
    Alawna <> wrote:
    :there should be no difference between if-elsses and switches in terms
    :eek:f performance. switches are only easier to read. ie, they produce
    :identical machine code.
    :by the way, i am talking from a pascal point of view but it should
    :also apply to C . Waiting like you for C guys to answer.

    When you look at it from a pascal point of view... you are incorrect,
    at least in some implementations. I used to work with a Pascal
    compiler which would do "finite-difference" methods on the switch
    values in order to detect "runs" of labels, and would convert
    those runs into table indices. Labels were internally
    re-ordered at need.

    Whether or not "runs" are used, when the case values are
    constants and there are no "fall through" locations
    (i.e., each case ends with a 'break' instead of continuing
    on to the next label becasue no 'break' was specified),
    then the compiler can sort the labels and drop in a binary
    search over the values -- finding the right section of
    code in log2(N) comparisions instead of N-1 comparisions.
    --
    Feep if you love VT-52's.
    Walter Roberson, Jun 19, 2005
    #6
  7. He Shiming

    He Shiming Guest

    Well, I'll have to do a performance profile (which is kinda complicated) if
    I were to find out about what cases are being accessed most frequently. I
    can't tell because there are hundreds of them.

    So, is it true that to get to the last "case" of a switch block, the
    processor needs to iterate through the whole list every time? If so, I could
    split 200 cases into like 5 unit and do a value-comparision before entering
    the switch. But is it worth it to do so? (especially when there are 200
    cases).

    --
    He Shiming

    "Minti" <> wrote in message
    news:...
    >
    >
    > Well, try to write these hundreds of switch statements using if-else's
    > and see if you have it easy that way.
    >
    > I have seen a lot of code with 100's of switch statements in many cases
    > it is just not _possible_ to apply any other strategy. However, as far
    > as performance is concerned try to keep the cases that you feel are
    > most likely to occur at the beginning of the switch block.
    >
    >
    > --
    > Imanpreet Singh Arora
    >
    He Shiming, Jun 19, 2005
    #7
  8. He Shiming

    forayer Guest

    He Shiming (NOSPAM) wrote:
    > Hi,
    >
    > I just wrote a function that has over 200 "cases" wrapped in a "switch"
    > statement. I'm wondering if there are performance issues in such
    > implementation. Do I need to optimize it some way?


    to my understandin, switch-cases n if-thens evaluate each expr until a
    match is found (if no match is found then 'default' or the last else is
    used). one way 2 optimize such irrelevant checkin wud b 2 use an arrays
    of funtion ptrs. but of course, ur switch-case expr shud b sumthin like
    case 1,case 2..., or it shud b possible to hash the cases to such a
    range of numbers.

    cheers.
    forayer, Jun 19, 2005
    #8
  9. He Shiming

    DeltaOne Guest

    Switches cases most often use jump tables and evaluate where as the if
    else do not use them. Thus switches may give an illusion of being fast
    but its not necessary,the only thing is that compilation may be a bit
    fast not the execution. It asically depends on how intelligent the
    compiler is. If its a good compiler they may be converted to the same
    amount of c code or c++ code what ever.

    And if you want ptimiztion then dont rely only on C++ compiler you can
    do some on your own by grouping something or even re ordering the
    structures.
    DeltaOne, Jun 19, 2005
    #9
  10. He Shiming

    pete Guest

    He Shiming wrote:

    > > I have seen a lot of code with 100's of switch statements
    > > in many cases
    > > it is just not _possible_ to apply any other strategy.


    If the cases are all consecutive integers,
    then you could rewrite it as functions
    with an array of function pointers
    to just index the correct function in one shot.

    --
    pete
    pete, Jun 19, 2005
    #10
  11. Le 19/06/2005 11:08, dans
    , « forayer »
    <> a écrit :

    > to my understandin, switch-cases n if-thens evaluate each expr until a
    > match is found (if no match is found then 'default' or the last else is
    > used). one way 2 optimize such irrelevant checkin wud b 2 use an arrays
    > of funtion ptrs. but of course, ur switch-case expr shud b sumthin like
    > case 1,case 2..., or it shud b possible to hash the cases to such a
    > range of numbers.
    >
    > cheers.


    <OT>
    Please avoid "b" "n" "2" "ur" and such things.
    They make reading rather inconvenient (at least for a french reader) ;-)
    </OT>
    Jean-Claude Arbaut, Jun 19, 2005
    #11
  12. He Shiming

    forayer Guest

    Jean-Claude Arbaut wrote:
    > <OT>
    > Please avoid "b" "n" "2" "ur" and such things.
    > They make reading rather inconvenient (at least for a french reader) ;-)
    > </OT>


    i'll keep that in mind from now on, and i do apologize for any
    inconvenience caused to anyone. sorry.

    cheers,
    forayer
    forayer, Jun 19, 2005
    #12
  13. Le 19/06/2005 13:07, dans
    , « forayer »
    <> a écrit :

    >
    >
    > Jean-Claude Arbaut wrote:
    >> <OT>
    >> Please avoid "b" "n" "2" "ur" and such things.
    >> They make reading rather inconvenient (at least for a french reader) ;-)
    >> </OT>

    >
    > i'll keep that in mind from now on, and i do apologize for any
    > inconvenience caused to anyone. sorry.


    Well, I do apologize for my own english mistakes ;-)
    Jean-Claude Arbaut, Jun 19, 2005
    #13
  14. In article <>,
    "Minti" <> wrote:

    > He Shiming (NOSPAM) wrote:
    > > Hi,
    > >
    > > I just wrote a function that has over 200 "cases" wrapped in a "switch"
    > > statement. I'm wondering if there are performance issues in such
    > > implementation. Do I need to optimize it some way?
    > >
    > > In terms of generated machine code, how does hundreds of cases in a switch
    > > differ from hundreds of if-elses? Do compilers or processors do any
    > > optimization on such structured code? Do I need to worry about the
    > > performance, usually?

    >
    > Well, try to write these hundreds of switch statements using if-else's
    > and see if you have it easy that way.
    >
    > I have seen a lot of code with 100's of switch statements in many cases
    > it is just not _possible_ to apply any other strategy. However, as far
    > as performance is concerned try to keep the cases that you feel are
    > most likely to occur at the beginning of the switch block.



    If you are concerned about execution speed, then
    Look at the assembler code.
    Measure the execution time.
    Learn what makes it fast

    But only if
    Making it faster would actually help somebody.

    In my experience, the biggest performance gains can be achieved by
    finding the bits in your code that are not just slow but completely
    braindamaged slow, and fixing them. Not the kind where you ask "what is
    faster: Switch or If", but the kind where you ask yourself "how could
    anyone be so stupid to write code that way? "

    Learn to find these bits of code and learn to use tools to find them.
    Christian Bau, Jun 19, 2005
    #14
  15. He Shiming

    CBFalconer Guest

    Alawna wrote:
    >
    > there should be no difference between if-elsses and switches in
    > terms of performance. switches are only easier to read. ie, they
    > produce identical machine code.


    Not necessarily so. An if else has to test everything in turn. A
    switch (or CASE in Pascal) can (but may not) use a transfer table,
    in which case there is no additional overhead to adding cases.

    --
    Some useful references about C:
    <http://www.ungerhu.com/jxh/clc.welcome.txt>
    <http://www.eskimo.com/~scs/C-faq/top.html>
    <http://benpfaff.org/writings/clc/off-topic.html>
    <http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n869/> (C99)
    <http://www.dinkumware.com/refxc.html> (C-library}
    <http://gcc.gnu.org/onlinedocs/> (GNU docs)
    CBFalconer, Jun 19, 2005
    #15
  16. He Shiming

    He Shiming Guest

    Oh that's definitely a great idea, I'll try, thanks.

    --
    He Shiming

    "pete" <> wrote in message
    news:...
    > He Shiming wrote:
    >
    > If the cases are all consecutive integers,
    > then you could rewrite it as functions
    > with an array of function pointers
    > to just index the correct function in one shot.
    >
    > --
    > pete
    He Shiming, Jun 19, 2005
    #16
  17. On Sun, 19 Jun 2005 13:32:14 +0800, He Shiming wrote:

    > Hi,
    >
    > I just wrote a function that has over 200 "cases" wrapped in a "switch"
    > statement. I'm wondering if there are performance issues in such
    > implementation. Do I need to optimize it some way?


    If it runs too slowly then you should probably look to optimise it in some
    way.

    > In terms of generated machine code, how does hundreds of cases in a switch
    > differ from hundreds of if-elses?


    However the compiler chooses. Most reasonable compilers will attempt to
    optimise switch statement using jump tables or range division (or a
    combination) where appropriate. How efeectively that can be done depends
    in the case values you are using.

    It is also possible for a compiler to optimise a chain of if else
    statements (e.g. one that tests a variable against various values) in a
    similar way so you can't assume that that would be less efficient.

    > Do compilers or processors do any
    > optimization on such structured code? Do I need to worry about the
    > performance, usually?


    It is reasonable to assume that compilers will deal with switch statements
    sensibly, and only worry about it, e.g. by looking at the assembly it
    produces, if you suspect a compiler isn't doing what you want.

    Lawrence
    Lawrence Kirby, Jun 19, 2005
    #17
  18. He Shiming

    He Shiming Guest

    Alrighty, I got the picture, thanks.

    --
    He Shiming

    "DeltaOne" <> wrote in message
    news:...
    > Switches cases most often use jump tables and evaluate where as the if
    > else do not use them. Thus switches may give an illusion of being fast
    > but its not necessary,the only thing is that compilation may be a bit
    > fast not the execution. It asically depends on how intelligent the
    > compiler is. If its a good compiler they may be converted to the same
    > amount of c code or c++ code what ever.
    >
    > And if you want ptimiztion then dont rely only on C++ compiler you can
    > do some on your own by grouping something or even re ordering the
    > structures.
    >
    He Shiming, Jun 19, 2005
    #18
  19. In article <d93c90$o20$>,
    "He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote:

    > Well, I'll have to do a performance profile (which is kinda complicated) if
    > I were to find out about what cases are being accessed most frequently. I
    > can't tell because there are hundreds of them.
    >
    > So, is it true that to get to the last "case" of a switch block, the
    > processor needs to iterate through the whole list every time? If so, I could
    > split 200 cases into like 5 unit and do a value-comparision before entering
    > the switch. But is it worth it to do so? (especially when there are 200
    > cases).


    One more time: Look at the assembler code if it matters.


    (And in most compilers that you will ever see it doesn't make the
    slightest difference how you arrange your labels. In some especially
    clever Java implementation, it may happen that the most common case
    executes fastest - no matter where you put it. )
    Christian Bau, Jun 19, 2005
    #19
  20. In article <>,
    "forayer" <> wrote:

    > He Shiming (NOSPAM) wrote:
    > > Hi,
    > >
    > > I just wrote a function that has over 200 "cases" wrapped in a "switch"
    > > statement. I'm wondering if there are performance issues in such
    > > implementation. Do I need to optimize it some way?

    >
    > to my understandin, switch-cases n if-thens evaluate each expr until a
    > match is found (if no match is found then 'default' or the last else is
    > used). one way 2 optimize such irrelevant checkin wud b 2 use an arrays
    > of funtion ptrs. but of course, ur switch-case expr shud b sumthin like
    > case 1,case 2..., or it shud b possible to hash the cases to such a
    > range of numbers.


    Did you verify your understanding by measuring the actual speed or
    looking at code that was generated? I don't think so.
    Christian Bau, Jun 19, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. windandwaves
    Replies:
    24
    Views:
    909
    Roy Schestowitz
    Feb 24, 2005
  2. Bryan Parkoff

    65536 Switch Cases

    Bryan Parkoff, Sep 16, 2004, in forum: C++
    Replies:
    5
    Views:
    444
    Ivan Vecerina
    Sep 17, 2004
  3. z-man
    Replies:
    7
    Views:
    383
    Tor Iver Wilhelmsen
    Oct 5, 2006
  4. Lynn McGuire

    maximum cases in a switch ?

    Lynn McGuire, Aug 9, 2011, in forum: C++
    Replies:
    67
    Views:
    2,332
    James Kanze
    Aug 22, 2011
  5. Ronny
    Replies:
    6
    Views:
    120
Loading...

Share This Page