An unusual use of case/switch

[Xavier Roche]

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

 

[Siri Cruise]

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 ?

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."

 

[James Kuyper]

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;
}
}

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".

 

[Keith Thompson]

On 09/16/2013 09:39 AM, Xavier Roche wrote: [...]
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.

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.

 

[Geoff]

On 09/16/2013 09:39 AM, Xavier Roche wrote: [...]
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.

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.

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.

 

[James Kuyper]

....

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.

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.

 

[Keith Thompson]

On 09/16/2013 09:39 AM, Xavier Roche wrote: [...]
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.

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.

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.

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.

 

[Geoff]

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.

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...

 

[Keith Thompson]

On Mon, 16 Sep 2013 13:42:23 -0400, James Kuyper


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.

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.

 

[Xavier Roche]

Le 16/09/2013 16:22, Siri Cruise a écrit :

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

Ah, thanks - this is actually a pretty neat example of a "legit" use.

 

[James Kuyper]

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.

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.

Maybe my post deserved a smiley...

Yes, I probably wouldn't have even bothered responding if there's been a
smiley on that message.

 

[Tim Rentsch]

[snip] http://en.wikipedia.org/wiki/Duff's_device [snip]

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);
}

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.

 

[jgh]

While optimizing this ...

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

more optimised than

JGH

 

[Ian Collins]

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


more optimised than

By the time the compiler has finished optimising the code, it probably
isn't....

 

[Tim Rentsch]

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


more optimised than

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.

 

[Ian Collins]

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.

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.

 

[Keith Thompson]

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


more optimised than

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.

 

[Tim Rentsch]

Why?

Because when I tried it myself that result is what I got.

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.

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.

 

[glen herrmannsfeldt]

(snip)

(snip)
(snip)
Because when I tried it myself that result is what I got.

(snip on optimization)

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

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

 

[Ian Collins]

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.

*to++ = *from++;

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 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.

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.

If you have a test case, I'll run the numbers.