An unusual use of case/switch

Discussion in 'C Programming' started by Xavier Roche, Sep 16, 2013.

  1. Xavier Roche

    Xavier Roche Guest

    Hi folks!

    I stumbled upon an interesting case (!) of case/switch code suggesting
    that case/switch are somehow equivalent to goto/<labels> in C ; ie. you
    may interleave loops of conditions between case and switch, for example.

    Here's an example (I would not recommend the coding style) of what I saw
    ; the code compiles without a single warning with gcc or clang. Is the
    above (horrible) code really valid as per C standard ?

    #include <stdio.h>
    #include <stdlib.h>

    static void foo(int c) {
    switch(c) {
    while(--c) {
    default:
    printf("%d\n", c);
    continue;
    case 0:
    printf("function called with zero\n");
    break;
    case 1:
    printf("function called with one\n");
    }
    break;
    case 42:
    printf("function called with 42\n");
    break;
    }
    }

    int main(int argc, const char **argv) {
    int i;
    for(i = 1 ; i < argc ; i++) {
    const int value = atoi(argv);
    foo(value);
    }
    return EXIT_SUCCESS;
    }

    $ ./case 0 1 2 42
    function called with zero
    function called with one
    2
    1
    function called with 42
     
    Xavier Roche, Sep 16, 2013
    #1
    1. Advertisements

  2. Xavier Roche

    Siri Cruise Guest

    http://en.wikipedia.org/wiki/Duff's_device

    In computer science, Duff's device is an optimized implementation of a serial
    copy that uses a technique widely applied in assembly language for loop
    unwinding. Its discovery is credited to Tom Duff in November 1983, who at the
    time was working for Lucasfilm. It is perhaps the most dramatic use of case
    label fall-through in the C programming language to date. Duff does not claim
    credit for discovering the concept of loop unrolling, just this particular
    expression of it in C.

    Straightforward code to copy items from an array to a memory-mapped output
    register might look like this:

    do {
    *to = *from++;
    } while(--count > 0);

    Note that this is not a memory-to-memory copy, in which you would see *to++.
    While optimizing this, Duff realized that an unrolled version of his loop could
    be implemented by interlacing the structures of a switch and a loop.

    register n = (count + 7) / 8;
    switch(count % 8) {
    case 0: do { *to = *from++;
    case 7: *to = *from++;
    case 6: *to = *from++;
    case 5: *to = *from++;
    case 4: *to = *from++;
    case 3: *to = *from++;
    case 2: *to = *from++;
    case 1: *to = *from++;
    } while(--n > 0);
    }

    Notice that Duff's device can just as easily be applied with any other size for
    the unrolled loop, not just 8.
    ..
    ..
    ..
    C's default fall-through in case statements has long been one of its most
    controversial features; Duff observed that "This code forms some sort of
    argument in that debate, but I'm not sure whether it's for or against."
     
    Siri Cruise, Sep 16, 2013
    #2
    1. Advertisements

  3. Xavier Roche

    James Kuyper Guest

    I believe it is (but I'm somewhat more reliable when I say that code is
    defective than I am when I say it's defect-free). A switch statement
    merely causes control to jump to the corresponding case label or default
    label. Conventional usage makes the body of a switch statement a
    sequence of statements interleaved with case labels or a default label,
    but that's just a convention. The case and default labels can appear in
    almost any of the same locations that an ordinary label may occur, so
    long as they occur only inside the body of a switch statement.

    There is one exception:
    "If a switch statement has an associated case or default label within
    the scope of an identifier with a variably modified type, the entire
    switch statement shall be within the scope of that identifier."
    (6.8.4.2p2) But that exception doesn't apply to the code you're talking
    about.

    Here's equivalent code using if()'s and gotos; perhaps this will help
    understand how a switch statement works.

    if(c==0) goto case0;
    else if(c==1) goto case1;
    else if(c==42) goto case42;
    else goto Default;
    while(--c){
    Default:
    printf("%d\n", c);
    continue;
    case0:
    printf("function called with zero\n");
    break;
    case1:
    printf("function called with one\n");
    }
    goto endblock;
    case42:
    printf("function called with 42\n");
    endblock:

    Note that if there were no default labels inside your switch statement,
    the equivalent code above would have "goto endblock" instead of "goto
    Default".
     
    James Kuyper, Sep 16, 2013
    #3
  4. There's a similar rule for gotos. N1570 6.8.6.1p1:

    A goto statement shall not jump from outside the scope of an
    identifier having a variably modified type to inside the scope
    of that identifier.

    (This is a constraint.) The restriction is on the goto, not on the
    label, because a label within the scope of a VLA could be legally
    targeted by a goto statemen within the same scope; a case label
    can only be targeted by the enclosing switch.
     
    Keith Thompson, Sep 16, 2013
    #4
  5. Xavier Roche

    Geoff Guest

    Ultimately, no matter the structure of the original source language
    code, the system degenerates into a sequence of machine code that
    contains conditional and unconditional jump instructions. In other
    words, your code is free of gotos only at a high level, inside the
    machine it's nothing but gotos.
     
    Geoff, Sep 16, 2013
    #5
  6. Xavier Roche

    James Kuyper Guest

    The term "goto statement" in N1570 6.8.6.1p1 refers exclusively with the
    C source code construct described in that section, so your comments
    about the resulting sequence of machine code are quite irrelevant. If
    you wish to continue being silly about it, you could take note of the
    fact that the standard never defines what "goto statement" means, but in
    context it's quite clear that it's referring to the first grammar
    production for a jump-statement, which is defined in 6.8.6p1.
     
    James Kuyper, Sep 16, 2013
    #6
  7. True, but not particularly relevant.

    All C code is reduced by the compiler to machine code, which is a
    sequence of instructions, which is in turn a sequence of bits. And I
    can easily imagine a target system that uses some constructs other than
    conditional and unconditional jump instructions.

    The whole point of C and other high-level languages (i.e., languages at
    a higher level than assembly language) is that you don't have to care
    about the lower-level machine code. C source code specifies *behavior*;
    the instruction sequence generated by a compiler is merely the means to
    that end.

    In a sense, the real power of higher-level control constructs (if/else,
    while, switch/case, and yes, even goto) is what they *don't* permit you
    to do.
     
    Keith Thompson, Sep 16, 2013
    #7
  8. Xavier Roche

    Geoff Guest

    I didn't think I was being any more silly than Keith and his citation
    of N1570 6.8.6.1p1 as some kind of improvement on your explanation of
    the OP's code snippet.

    The original question IMO was "is this valid?"; is it ugly/horrid?

    I think Siri Cruise beat you guys to the punch with both a cogent and
    succinct explanation as to the origin and purpose of the technique.
    Maybe my post deserved a smiley... ;)
     
    Geoff, Sep 16, 2013
    #8
  9. That citation was not particularly intended as an improvement on the
    explanation of the OP's code. It was merely a side point about a
    similar rule.
     
    Keith Thompson, Sep 16, 2013
    #9
  10. Xavier Roche

    Xavier Roche Guest

    Xavier Roche, Sep 16, 2013
    #10
  11. Xavier Roche

    James Kuyper Guest

    It was more of an addendum than an improvement, and I had been debating
    whether to mention 6.8.6.1p1 when I wrote my response to the OP. I
    decided against it, but it was close decision, so I didn't mind Keith
    going the other way.
    Yes, I probably wouldn't have even bothered responding if there's been a
    smiley on that message.
     
    James Kuyper, Sep 17, 2013
    #11
  12. Xavier Roche

    Tim Rentsch Guest

    This form:

    register int n = count/8;
    switch(count % 8) {
    do {
    *to = *from++;
    case 7: *to = *from++;
    case 6: *to = *from++;
    case 5: *to = *from++;
    case 4: *to = *from++;
    case 3: *to = *from++;
    case 2: *to = *from++;
    case 1: *to = *from++;
    case 0: ;
    } while(n-- > 0);
    }

    seamlessly handles the case where count == 0.
     
    Tim Rentsch, Sep 22, 2013
    #12
  13. Xavier Roche

    jgh Guest

    While optimizing this ...

    One of those things I've forgotten, but how is:

    more optimised than

    JGH
     
    jgh, Sep 23, 2013
    #13
  14. Xavier Roche

    Ian Collins Guest

    By the time the compiler has finished optimising the code, it probably
    isn't....
     
    Ian Collins, Sep 23, 2013
    #14
  15. Xavier Roche

    Tim Rentsch Guest

    Sorry, I overlooked the missing ++'s (missing in the original
    as well as my revised version):

    register int n = count/8;
    switch(count % 8) {
    do {
    *to++ = *from++;
    case 7: *to++ = *from++;
    case 6: *to++ = *from++;
    case 5: *to++ = *from++;
    case 4: *to++ = *from++;
    case 3: *to++ = *from++;
    case 2: *to++ = *from++;
    case 1: *to++ = *from++;
    case 0: ;
    } while(n-- > 0);
    }

    However, if you actually try compiling and running the two
    cases shown above (where the '++' is missing on the left-hand
    sides), I expect you will find the unrolled loop runs
    substantially faster than the simple do/while version.
     
    Tim Rentsch, Sep 23, 2013
    #15
  16. Xavier Roche

    Ian Collins Guest

    Why?

    I thought the convoluted option would just make it harder for the
    compiler to recognise opportunities for optimisations, particularly loop
    unrolling. So I tried compiling both and sure enough, Sun's cc
    generated the same code as gcc for the switch case, but it went on to
    generate unrolled versions for the simple loop.
     
    Ian Collins, Sep 23, 2013
    #16
  17. It's called "loop unrolling"; a Google search for that phrase might be
    instructive (though I haven't actually bothered to check).

    With the simple do/while loop and an insufficiently clever compiler, it
    has to perform the check (--count > 0) on each iteration. With the
    Duff's device version, that check is done only once every 8 iterations;
    it spends most of its time running straight-line code:

    *to = *from++;
    *to = *from++;
    *to = *from++;
    ...

    Modern optimizing compilers can often unroll loops for you.
    They might do a better job of deciding how to unroll the loop (is
    16 cases better than 8? what about 32?). And often straightforward
    code is easier to analyze, and therefore easier to optimize, than
    hand-micro-optimized code.
     
    Keith Thompson, Sep 23, 2013
    #17
  18. Xavier Roche

    Tim Rentsch Guest

    Because when I tried it myself that result is what I got.
    You don't quite say both what, and in the tests I ran that
    makes a difference. The case I was referring to is where
    'from' is incremented but 'to' pointlessly is not, ie, a basic
    step of

    *to = *from++;

    For that assignment step, the unrolled loop ran faster (by
    about 25% IIRC). I also tried a basic step of

    *--to = *from++;

    with about the same results. The common "copying" basic step,
    ie,

    *to++ = *from++;

    was completely the other way, and dramatically so - the simple
    loop ran faster by at least a factor of two. Looking at the
    generated code, it seemed obvious that there was some sort of
    special casing to handle this idiom, using lots of different
    tricks, not just loop unrolling.

    This is not to say I think the same results will occur will all
    compilers, I don't. But that would be the least surprising
    result given the information available to me when I made the
    statement. I'd be interested to see some performance results
    of various cases under the Sun compiler, if running those isn't
    too much trouble.
     
    Tim Rentsch, Sep 23, 2013
    #18
  19. (snip)
    (snip on optimization)
    As I understand it, in the original Duff's case *to is an
    I/O port, so writing to it is not pointless.

    The probably means it should be volatile, such that the stores
    don't get optimized away. That might stop some optimizations
    that the compiler might otherwise be able to do.

    -- glen
     
    glen herrmannsfeldt, Sep 23, 2013
    #19
  20. Xavier Roche

    Ian Collins Guest

    *to++ = *from++;
    This bag of tricks was what I was referring to above as the compiler
    recognising and exploiting opportunities for optimisation. Compiler
    writers have had decades to tune their code to optimise idiomatic code.
    If you have a test case, I'll run the numbers.
     
    Ian Collins, Sep 23, 2013
    #20
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.