Duff's Device

[Hallvard B Furuseth]

I've been wondering sometimes:
Anyone know why Duff's device is usually written like this:

void duff(const char *str, int len) {
int n = (len + 7) / 8;
switch (len % 8) {
case 0: do{ foo(*str++);
case 7:     foo(*str++);
case 6:     foo(*str++);
...
case 1:     foo(*str++);
} while (--n 0);
}
}

instead of this?

void duff2(const char *str, int len) {
switch (len % 8) {
case 0: while ((len -= 8) >= 0) {
foo(*str++);
case 7: foo(*str++);
case 6: foo(*str++);
...
case 1: foo(*str++);
}
}
}

The original has an extra '+' and doesn't handle len=0.
Nor does it need the divide by 8, though I realize n-=1
may be cheaper than n-=8 on some architectures.
People have had 18 years to notice now:-)

--
Hallvard

[Hallvard B Furuseth]

I wrote:

I've been wondering sometimes:
Anyone know why Duff's device is usually written like this:
(...)

Er, a bit silly question - "that's the way it's published" of course.
I meant, is there a good reason to write it that way - produces
better code on some machine?

--
Hallvard

[Laurent Deniau]

Hallvard B Furuseth wrote:

I've been wondering sometimes:
Anyone know why Duff's device is usually written like this:

void duff(const char *str, int len) {
int n = (len + 7) / 8;
switch (len % 8) {
case 0: do{ foo(*str++);
case 7: foo(*str++);
case 6: foo(*str++);
...
case 1: foo(*str++);
} while (--n 0);
}
}

instead of this?

void duff2(const char *str, int len) {
switch (len % 8) {
case 0: while ((len -= 8) >= 0) {
foo(*str++);
case 7: foo(*str++);
case 6: foo(*str++);
...
case 1: foo(*str++);
}
}
}

The original has an extra '+' and doesn't handle len=0.
Nor does it need the divide by 8, though I realize n-=1
may be cheaper than n-=8 on some architectures.
People have had 18 years to notice now:-)

I did some speed test some time ago with gcc on x86 and the fastest
version I was able to find was:

static inline void
ooc_memchr_copy( char *restrict dst,
const char *restrict src, size_t cnt)
{
size_t rem = cnt % 8;
cnt = (cnt / 8) + 1;

switch (rem)
do { *dst++ = *src++;
case 7: *dst++ = *src++;
case 6: *dst++ = *src++;
case 5: *dst++ = *src++;
case 4: *dst++ = *src++;
case 3: *dst++ = *src++;
case 2: *dst++ = *src++;
case 1: *dst++ = *src++;
case 0: ;
} while(--cnt);
}

which is not the one published and works for cnt==0 as well as for
cnt==(size_t)-1. Why do you think that the orignal version is always the
one used?

a+, ld.

[Rod Pemberton]

"Hallvard B Furuseth" <h.**********@usit.uio.nowrote in message
news:hb**************@bombur.uio.no...

Anyone know why Duff's device is usually written
like this (snip) instead of this? (snip)

Yes.

This is his original post:
http://groups.google.com/group/net.l...e07aa94c?hl=en

This is another post from him with clarifications to various questions from
individuals on c.l.c:
http://groups.google.com/group/comp....75c42411?hl=en

From the original post, he (indirectly) states that the design of Duff's
Device in C was the direct result of his understanding of how to generate
efficient unrolled loops in assembly language for the VAX. At least, that
is the one thing other than Duff's Device that you should get from his
message...
FYI, others have pointed out Simon Tatham's "Coroutines in C":
http://www.chiark.greenend.org.uk/~s...oroutines.html

Protothreads is also based on a similar mechanism:
http://www.sics.se/~adam/pt/
Rod Pemberton

[Keith Thompson]

"Rod Pemberton" <do*********@bitfoad.cmmwrites:

"Hallvard B Furuseth" <h.**********@usit.uio.nowrote in message
news:hb**************@bombur.uio.no...

>Anyone know why Duff's device is usually written
like this (snip) instead of this? (snip)

Yes.

This is his original post:
http://groups.google.com/group/net.l...e07aa94c?hl=en

This is another post from him with clarifications to various questions from
individuals on c.l.c:
http://groups.google.com/group/comp....75c42411?hl=en

[...]

And here's the scary part:

| It amazes me that after 10 years of writing C there are still little
| corners that I haven't explored fully. (Actually, I have another
| revolting way to use switches to implement interrupt driven state
| machines but it's too horrid to go into.)

Does anyone know the details? If the orginal Duff's Device wasn't
"too horrid to go into" ... (*shudder*).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Christopher Benson-Manica]

Keith Thompson <ks***@mib.orgwrote:

Does anyone know the details? If the orginal Duff's Device wasn't
"too horrid to go into" ... (*shudder*).

One might even call it "Duff's Last Theorem" :-)

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

[Harald van Dijk]

Keith Thompson wrote:

And here's the scary part:

| It amazes me that after 10 years of writing C there are still little
| corners that I haven't explored fully. (Actually, I have another
| revolting way to use switches to implement interrupt driven state
| machines but it's too horrid to go into.)

Does anyone know the details? If the orginal Duff's Device wasn't
"too horrid to go into" ... (*shudder*).

http://www.chiark.greenend.org.uk/~s...oroutines.html

[Mabden]

"Harald van D?k" <tr*****@gmail.comwrote in message
news:11**********************@c28g2000cwb.googlegr oups.com...

Keith Thompson wrote:

And here's the scary part:

| It amazes me that after 10 years of writing C there are still little
| corners that I haven't explored fully. (Actually, I have another
| revolting way to use switches to implement interrupt driven state
| machines but it's too horrid to go into.)

Does anyone know the details? If the orginal Duff's Device wasn't
"too horrid to go into" ... (*shudder*).

http://www.chiark.greenend.org.uk/~s...oroutines.html

The best part is it ends with "Share and Enjoy"*!

*"Share and Enjoy" is, of course, the company motto of the hugely successful
Sirius Cybernetics Corporation Complaints division, which now covers the
major land masses of three medium sized planets and is the only part of the
Corporation to have shown a consistent profit in recent years.

[Hallvard B Furuseth]

Laurent Deniau writes:

Hallvard B Furuseth wrote:

>I've been wondering sometimes:
Anyone know why Duff's device is usually written like this:
(...)

I did some speed test some time ago with gcc on x86 and the fastest
version I was able to find was:

static inline void
ooc_memchr_copy( char *restrict dst,
const char *restrict src, size_t cnt)
{
size_t rem = cnt % 8;
cnt = (cnt / 8) + 1;
(...)

Heh. Strange, keeps an add but still speeds it up.

which is not the one published and works for cnt==0 as well as for
cnt==(size_t)-1. Why do you think that the orignal version is always
the one used?

It isn't; it's just the one I've _usually_ seen. (Not that I've seen

the device used all that often:-)

--
Hallvard

[Hallvard B Furuseth]

Rod Pemberton writes:

FYI, others have pointed out Simon Tatham's "Coroutines in C":
http://www.chiark.greenend.org.uk/~s...oroutines.html

Cool. Why didn't anyone tell me about that __LINE__ trick before?:-)
I wouldn't call them coroutines though. Too limited.

Personally I don't see anything ugly about it, BTW. Hiding ugly stuff
is one of the things macros are _for_. Except the crFinish macro, but
that one is not necessary:

#define AutoSwitch(state) /* state=integer state variable */\
switch (state) case 0:
#define AScontrol(state, stmt) /* stmt=return/break/continue/goto */\
if (1) { (state) = __LINE__; stmt; case __LINE__:; } else (void)(0)

Now it's just a normal switch in that break/continue/etc work as
normally - it's just that the case statements look nicer this way.

int foo(void)
{
static int state, cur;
AutoSwitch(state)
for (cur = 1; cur < 10; cur++)
AScontrol(state, return cur*cur);
return 0;
}
--
Hallvard

[Christopher Layne]

Hallvard B Furuseth wrote:

Personally I don't see anything ugly about it, BTW. Hiding ugly stuff

Go look at the Putty code and report back to us.

[Hallvard B Furuseth]

Christopher Layne writes:

>Hallvard B Furuseth wrote:

>Personally I don't see anything ugly about it, BTW. Hiding ugly stuff

Go look at the Putty code and report back to us.

OK, now that has way too many magic macros to keep track of.
(Which is one reason I made 'return' etc arguments to my variants BTW,
that way if there is a return statement somewhere it is in the body.)

--
Hallvard