By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,750 Members | 1,214 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,750 IT Pros & Developers. It's quick & easy.

Duff's Device

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

Expand|Select|Wrap|Line Numbers
  1. void duff(const char *str, int len) {
  2. int n = (len + 7) / 8;
  3. switch (len % 8) {
  4. case 0: do{ foo(*str++);
  5. case 7:     foo(*str++);
  6. case 6:     foo(*str++);
  7. ...
  8. case 1:     foo(*str++);
  9. } while (--n 0);
  10. }
  11. }
instead of this?

Expand|Select|Wrap|Line Numbers
  1. void duff2(const char *str, int len) {
  2. switch (len % 8) {
  3. case 0: while ((len -= 8) >= 0) {
  4. foo(*str++);
  5. case 7: foo(*str++);
  6. case 6: foo(*str++);
  7. ...
  8. case 1: foo(*str++);
  9. }
  10. }
  11. }
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
Sep 28 '06 #1
Share this Question
Share on Google+
11 Replies


P: n/a
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
Sep 28 '06 #2

P: n/a
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.
Sep 28 '06 #3

P: n/a

"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
Sep 28 '06 #4

P: n/a
"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.
Sep 28 '06 #5

P: n/a
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.
Sep 29 '06 #6

P: n/a
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

Sep 29 '06 #7

P: n/a
"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.
Oct 2 '06 #8

P: n/a
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
Oct 3 '06 #9

P: n/a
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
Oct 3 '06 #10

P: n/a
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.
Oct 3 '06 #11

P: n/a
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
Oct 3 '06 #12

This discussion thread is closed

Replies have been disabled for this discussion.