Regarding Switch statement

Discussion in 'C Programming' started by prafulla, Feb 19, 2004.

  1. prafulla

    prafulla Guest

    Hi all,

    I don't have a copy of C standard at hand and so anyone of you can
    help me. I have always wondered how switch statements are so efficient
    in jumping to the right case (if any)? Can anybody point me to the
    innards of it please?

    Sorry if this is OT on clc and more relevant to comp.compilers. I am
    confused here too.

    TIA
    -Prafulla harpanhalli
    prafulla, Feb 19, 2004
    #1
    1. Advertising

  2. prafulla

    Jack Klein Guest

    On 18 Feb 2004 20:16:46 -0800, (prafulla)
    wrote in comp.lang.c:

    > Hi all,
    >
    > I don't have a copy of C standard at hand and so anyone of you can
    > help me. I have always wondered how switch statements are so efficient
    > in jumping to the right case (if any)? Can anybody point me to the
    > innards of it please?


    Who says they are efficient? The C standard does not discuss
    efficiency at all, this is a QOI issue. If a C implementation
    compiles a strictly conforming program that generates the correct
    output, whether it takes 5 seconds, 5 hours, or 5 years is not a
    language issue.

    > Sorry if this is OT on clc and more relevant to comp.compilers. I am
    > confused here too.


    How a compiler implements the "innards" is completely unspecified by
    the language and irrelevant here. Possibilities include a series of
    "if" "else if" statements, or perhaps a jump table.

    > TIA
    > -Prafulla harpanhalli


    comp.compilers would be a much better choice for implementation
    details.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
    Jack Klein, Feb 19, 2004
    #2
    1. Advertising

  3. prafulla wrote:
    >
    > Hi all,
    >
    > I don't have a copy of C standard at hand and so anyone of you can
    > help me. I have always wondered how switch statements are so efficient
    > in jumping to the right case (if any)? Can anybody point me to the
    > innards of it please?
    >
    > Sorry if this is OT on clc and more relevant to comp.compilers. I am
    > confused here too.


    This is really an implementation thing, not a language thing. How
    a particular C compiler implements switch/case is irrelevent to the
    C language itself.

    That said...

    There are numerous possibilities. Suppose, for example, that your
    cases are 0, 1, 2, 3, 4, and 5. The compiler could generate a jump
    table (after bounds checking) to each of the 6 possibilities, and
    jump directly to the appropriate case. Another possibility, if the
    cases are too disparate for a jump table, would be to generate a
    binary search through the values. (ie: if less than the median
    value, jump to A, else to B. Within A and B, each repeats the
    median comparison, until you end up at a simple "is it this value,
    and if not, jump to the default case".) You might even combine
    these methods, if you have clusters of values within a disparate
    group. (ie: 0, 1, 2, 3, 50, 51, 52, 99)

    Of course, there's nothing stopping the compiler from generating
    the equivalent of a bunch of if/else tests in the order in which
    you code the cases.


    If you have a specific compiler in mind, see if there is a groups
    specifically for that compiler. Otherwise, comp.compilers would be
    a good place for general questions regarding possible methods of
    optimizing switch/case statements.

    --

    +---------+----------------------------------+-----------------------------+
    | Kenneth | kenbrody at spamcop.net | "The opinions expressed |
    | J. | http://www.hvcomputer.com | herein are not necessarily |
    | Brody | http://www.fptech.com | those of fP Technologies." |
    +---------+----------------------------------+-----------------------------+
    Kenneth Brody, Feb 19, 2004
    #3
  4. prafulla wrote:

    > Hi all,
    >
    > I don't have a copy of C standard at hand and so anyone of you can
    > help me. I have always wondered how switch statements are so efficient
    > in jumping to the right case (if any)? Can anybody point me to the
    > innards of it please?
    >
    > Sorry if this is OT on clc and more relevant to comp.compilers. I am
    > confused here too.
    >
    > TIA
    > -Prafulla harpanhalli


    Two popular implementations of a switch statement are:
    1. if-elseif-else ladder.
    2. table of function pointers (jump table).

    You can always implement these yourself, by converting
    your switch statement into one of the above. The switch
    statement just happens to be a convenient notation for
    this programming pardigm (pattern?).

    I personally believe that the switch statement is evil
    and I prefer using tables of function pointers. I've
    seen many abused switch statements (including a greater
    evil of nesting them). One problematic issue of tables
    of function pointers is that each function must have
    the same signature (even if the function doesn't use
    all the parameters).

    I believe that switch statements are clear to read
    when they are small. But like plants and children,
    they don't remain small forever. ;-)

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c /faq.html
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
    Thomas Matthews, Feb 19, 2004
    #4
  5. Thomas Matthews <> writes:
    [...]
    > Two popular implementations of a switch statement are:
    > 1. if-elseif-else ladder.
    > 2. table of function pointers (jump table).
    >
    > You can always implement these yourself, by converting
    > your switch statement into one of the above. The switch
    > statement just happens to be a convenient notation for
    > this programming pardigm (pattern?).


    A C switch statement is not equivalent to an if-elseif-else ladder
    *unless* each case ends in a break. If some of the cases fall through
    to other cases, a translation will have to use something like gotos.
    Then again, an if-elseif-else ladder is implemented using gotos, or
    rather machine-level conditional and unconditional branches, but there
    can be optimization advantages in using a more structured intermediate
    representation -- which a compiler can do in the common case where
    each case does end in a break.

    If a switch statement is implemented using a jump table, it won't be a
    table of function pointers; it will be a table of label pointers.
    Standard C doesn't have such a construct <OT>though I think GNU C
    does</OT>.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
    Keith Thompson, Feb 19, 2004
    #5
  6. Kenneth Brody <> wrote in message news:<>...
    > prafulla wrote:
    > > I have always wondered how switch statements are so efficient
    > > in jumping to the right case (if any)? Can anybody point me to the
    > > innards of it please?


    > If you have a specific compiler in mind, see if there is a groups
    > specifically for that compiler....


    Easier yet, just look at the compiled code, e.g. with cc -S.

    Some compilers are fairly clever at combining different implementation
    ideas within one switch.

    It might be fun to stage a little experiment here, finding the
    cleverest compiled switch (and the worst).

    James
    James Dow Allen, Feb 20, 2004
    #6
  7. prafulla

    nrk Guest

    prafulla wrote:

    > Hi all,
    >
    > I don't have a copy of C standard at hand and so anyone of you can
    > help me. I have always wondered how switch statements are so efficient
    > in jumping to the right case (if any)? Can anybody point me to the
    > innards of it please?
    >


    Please note that there is no guarantee about efficiencies in the C standard.
    However, for stylistic reasons, when checking more than 3 if-else if-else
    if style conditions, I would pick switch. If you want some insight into
    the innards, Chris Torek posted an excellent article on the subject in the
    not too distant past. Here it is:

    http://www.google.com/groups?as_umsgid=

    -nrk.

    > Sorry if this is OT on clc and more relevant to comp.compilers. I am
    > confused here too.
    >
    > TIA
    > -Prafulla harpanhalli


    --
    Remove devnull for email
    nrk, Feb 20, 2004
    #7
  8. "nrk" <> wrote in message
    news:_fhZb.52867$...
    > Please note that there is no guarantee about efficiencies in the C

    standard.
    > However, for stylistic reasons, when checking more than 3 if-else if-else
    > if style conditions, I would pick switch.


    Unless you *want* to evaluate the expression each time, for example when it
    has a side-effect, changes its value or when it is a different expression
    :)

    My boss used to use switch even for a single case. He argued that switch is
    faster than if. Now that is what I call strange.
    Peter Pichler, Feb 20, 2004
    #8
  9. prafulla

    Richard Bos Guest

    CBFalconer <> wrote:

    > nrk wrote:
    >
    > > However, for stylistic reasons, when checking more than 3 if-else
    > > if-else if style conditions, I would pick switch.

    >
    > Please explain how you handle the following with switch:
    >
    > if (v > 10000) i = 0;
    > else if (v > 1000 ) i = 3;
    > else if (v > 100 ) i = 5;
    > else if (v > 10 ) i = 2;
    > else if (v > 5 ) i = 1;
    > else i = 0;
    >
    > and be prepared to reorganize either column of values at any time,
    > including the number of cases to be handled.
    >
    > The above table is closely related to the Bush regimes tax
    > policies in the US.


    v is monthly income in hundreds of dollars, i is income tax in dollars?

    Richard
    Richard Bos, Feb 20, 2004
    #9
  10. prafulla

    CBFalconer Guest

    nrk wrote:
    >

    .... snip ...
    >
    > However, for stylistic reasons, when checking more than 3 if-else
    > if-else if style conditions, I would pick switch.


    Please explain how you handle the following with switch:

    if (v > 10000) i = 0;
    else if (v > 1000 ) i = 3;
    else if (v > 100 ) i = 5;
    else if (v > 10 ) i = 2;
    else if (v > 5 ) i = 1;
    else i = 0;

    and be prepared to reorganize either column of values at any time,
    including the number of cases to be handled.

    The above table is closely related to the Bush regimes tax
    policies in the US.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
    CBFalconer, Feb 20, 2004
    #10
  11. prafulla

    nrk Guest

    CBFalconer wrote:

    > nrk wrote:
    >>

    > ... snip ...
    >>
    >> However, for stylistic reasons, when checking more than 3 if-else
    >> if-else if style conditions, I would pick switch.

    >
    > Please explain how you handle the following with switch:
    >
    > if (v > 10000) i = 0;
    > else if (v > 1000 ) i = 3;
    > else if (v > 100 ) i = 5;
    > else if (v > 10 ) i = 2;
    > else if (v > 5 ) i = 1;
    > else i = 0;
    >
    > and be prepared to reorganize either column of values at any time,
    > including the number of cases to be handled.
    >
    > The above table is closely related to the Bush regimes tax
    > policies in the US.
    >


    Try to engage your brain please ;-) I was obviously talking about
    situations where a switch would be appropriate. If that wasn't obvious to
    you, that's your lookout, not mine.

    -nrk.

    --
    Remove devnull for email
    nrk, Feb 20, 2004
    #11
  12. prafulla

    CBFalconer Guest

    nrk wrote:
    > CBFalconer wrote:
    > > nrk wrote:
    > >>

    > > ... snip ...
    > >>
    > >> However, for stylistic reasons, when checking more than 3 if-else
    > >> if-else if style conditions, I would pick switch.

    > >
    > > Please explain how you handle the following with switch:
    > >
    > > if (v > 10000) i = 0;
    > > else if (v > 1000 ) i = 3;
    > > else if (v > 100 ) i = 5;
    > > else if (v > 10 ) i = 2;
    > > else if (v > 5 ) i = 1;
    > > else i = 0;
    > >
    > > and be prepared to reorganize either column of values at any time,
    > > including the number of cases to be handled.
    > >
    > > The above table is closely related to the Bush regimes tax
    > > policies in the US.

    >
    > Try to engage your brain please ;-) I was obviously talking about
    > situations where a switch would be appropriate. If that wasn't
    > obvious to you, that's your lookout, not mine.


    Now now, let's not get testy :) Looking up I distinctly see the
    prequisite "more than 3 if else if" clauses. We do tend to
    require precision around here, and I have been bitten by it often
    enough. Acting like Bushmen is not appropriate.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
    CBFalconer, Feb 20, 2004
    #12
  13. prafulla

    Alan Balmer Guest

    On Fri, 20 Feb 2004 15:10:00 GMT, nrk
    <> wrote:

    >> policies in the US.
    >>

    >
    >Try to engage your brain please ;-) I was obviously talking about
    >situations where a switch would be appropriate. If that wasn't obvious to
    >you, that's your lookout, not mine.


    It's harder to code political statements with switch.

    --
    Al Balmer
    Balmer Consulting
    Alan Balmer, Feb 20, 2004
    #13
  14. prafulla

    nrk Guest

    CBFalconer wrote:

    > nrk wrote:
    >>

    > ... snip ...
    >>
    >> However, for stylistic reasons, when checking more than 3 if-else
    >> if-else if style conditions, I would pick switch.

    >
    > Please explain how you handle the following with switch:
    >
    > if (v > 10000) i = 0;
    > else if (v > 1000 ) i = 3;
    > else if (v > 100 ) i = 5;
    > else if (v > 10 ) i = 2;
    > else if (v > 5 ) i = 1;
    > else i = 0;
    >
    > and be prepared to reorganize either column of values at any time,
    > including the number of cases to be handled.
    >
    > The above table is closely related to the Bush regimes tax
    > policies in the US.
    >


    If you must insist on a switch solution to this particular case... then:

    static const int vtable[] = { 10000, 1000, 100, 10, 5, };
    static const int itable[] = { 0, 3, 5, 2, 1, };
    int index = 0, test = 0;

    while ( index < sizeof vtable/sizeof vtable[0] ) {
    switch ( test ) {
    case 1:
    i = itable[index-1];
    goto end;
    case 0:
    test = index < sizeof vtable/sizeof vtable[0] &&
    (v > vtable[index++]);
    break;
    }
    }
    i = 0;
    end:
    /* use i here */

    This just re-inforces the idea that it is probably better to engage the
    muscle between the ears than to take statements on style out of context and
    try to apply them willy-nilly ;-) At least, you didn't ask me for C&V for
    that stylistic statment!

    -nrk.
    --
    Remove devnull for email
    nrk, Feb 20, 2004
    #14
  15. prafulla

    nrk Guest

    nrk wrote:

    > CBFalconer wrote:
    >
    >> nrk wrote:
    >>>

    >> ... snip ...
    >>>
    >>> However, for stylistic reasons, when checking more than 3 if-else
    >>> if-else if style conditions, I would pick switch.

    >>
    >> Please explain how you handle the following with switch:
    >>
    >> if (v > 10000) i = 0;
    >> else if (v > 1000 ) i = 3;
    >> else if (v > 100 ) i = 5;
    >> else if (v > 10 ) i = 2;
    >> else if (v > 5 ) i = 1;
    >> else i = 0;
    >>
    >> and be prepared to reorganize either column of values at any time,
    >> including the number of cases to be handled.
    >>
    >> The above table is closely related to the Bush regimes tax
    >> policies in the US.
    >>

    >
    > If you must insist on a switch solution to this particular case... then:
    >
    > static const int vtable[] = { 10000, 1000, 100, 10, 5, };
    > static const int itable[] = { 0, 3, 5, 2, 1, };
    > int index = 0, test = 0;
    >
    > while ( index < sizeof vtable/sizeof vtable[0] ) {


    Dang it! That's not going to work, is it?

    > switch ( test ) {
    > case 1:
    > i = itable[index-1];
    > goto end;
    > case 0:
    > test = index < sizeof vtable/sizeof vtable[0] &&
    > (v > vtable[index++]);
    > break;
    > }
    > }
    > i = 0;
    > end:
    > /* use i here */


    Let's try again:

    static const int vtable[] = { 10000, 1000, 100, 10, 5, };
    static const int itable[] = { 0, 3, 5, 2, 1, };
    int index = 0, test = 0;

    while ( index < sizeof vtable/sizeof vtable[0] ) {
    switch ( test ) {
    case 1:
    i = itable[index];
    goto end;
    case 0:
    test = (v > vtable[index] || (++index, 0));
    break;
    }
    }
    i = 0;
    end:
    /* use i here */

    I think there's a lesson somewhere in this for me, but I refuse to learn :)

    -nrk.

    >
    > This just re-inforces the idea that it is probably better to engage the
    > muscle between the ears than to take statements on style out of context
    > and
    > try to apply them willy-nilly ;-) At least, you didn't ask me for C&V for
    > that stylistic statment!
    >
    > -nrk.


    --
    Remove devnull for email
    nrk, Feb 20, 2004
    #15
  16. CBFalconer <> writes:
    [...]
    > Now now, let's not get testy :) Looking up I distinctly see the
    > prequisite "more than 3 if else if" clauses. We do tend to
    > require precision around here, and I have been bitten by it often
    > enough. Acting like Bushmen is not appropriate.


    <OT>
    I'm sure you didn't intend that as an ethnic slur. The Bushmen are an
    actual ethnic group in southern Africa. (There's been some debate, I
    think, about whether "Bushmen" is an appropriate term, but the brief
    Googling I just did indicates that it's now generally accepted.)
    </OT>

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
    Keith Thompson, Feb 21, 2004
    #16
  17. On Fri, 20 Feb 2004 11:42:44 -0700, in comp.lang.c , Alan Balmer
    <> wrote:

    >On Fri, 20 Feb 2004 15:10:00 GMT, nrk
    ><> wrote:
    >
    >>> policies in the US.
    >>>

    >>
    >>Try to engage your brain please ;-) I was obviously talking about
    >>situations where a switch would be appropriate. If that wasn't obvious to
    >>you, that's your lookout, not mine.

    >
    >It's harder to code political statements with switch.


    Wasn't it an american president who said
    "walk softly, but carry a big switch?"

    :)

    --
    Mark McIntyre
    CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
    CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>


    ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
    http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
    ---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
    Mark McIntyre, Feb 21, 2004
    #17
  18. prafulla

    CBFalconer Guest

    Keith Thompson wrote:
    > CBFalconer <> writes:
    > [...]
    > > Now now, let's not get testy :) Looking up I distinctly see the
    > > prequisite "more than 3 if else if" clauses. We do tend to
    > > require precision around here, and I have been bitten by it often
    > > enough. Acting like Bushmen is not appropriate.

    >
    > <OT>
    > I'm sure you didn't intend that as an ethnic slur. The Bushmen are an
    > actual ethnic group in southern Africa. (There's been some debate, I
    > think, about whether "Bushmen" is an appropriate term, but the brief
    > Googling I just did indicates that it's now generally accepted.)


    I didn't, but I did intend it to connote the present US regime in
    temporary (we trust) power, who have been known to play fast and
    loose with accuracy and precision.
    </OT>

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
    CBFalconer, Feb 21, 2004
    #18
    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. Replies:
    21
    Views:
    1,039
    Giannis Papadopoulos
    Aug 2, 2005
  2. Replies:
    5
    Views:
    622
    David T. Ashley
    Jan 15, 2007
  3. Kurt
    Replies:
    7
    Views:
    375
    mlimber
    Mar 23, 2007
  4. bthumber
    Replies:
    5
    Views:
    411
    Alexey Smirnov
    Jan 29, 2009
  5. Switch Within A Switch

    , Apr 22, 2006, in forum: Javascript
    Replies:
    7
    Views:
    100
    Lasse Reichstein Nielsen
    Apr 22, 2006
Loading...

Share This Page