Duff's Device

Discussion in 'C Programming' started by Hallvard B Furuseth, Sep 28, 2006.

  1. 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, Sep 28, 2006
    #1
    1. Advertising

  2. 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
    Hallvard B Furuseth, Sep 28, 2006
    #2
    1. Advertising

  3. 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.
    Laurent Deniau, Sep 28, 2006
    #3
  4. "Hallvard B Furuseth" <> wrote in message
    news:...
    > 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.lang.c/msg/66008138e07aa94c?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.lang.c/msg/bb78298175c42411?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/~sgtatham/coroutines.html

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


    Rod Pemberton
    Rod Pemberton, Sep 28, 2006
    #4
  5. "Rod Pemberton" <> writes:
    > "Hallvard B Furuseth" <> wrote in message
    > news:...
    >> 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.lang.c/msg/66008138e07aa94c?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.lang.c/msg/bb78298175c42411?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) <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.
    Keith Thompson, Sep 29, 2006
    #5
  6. Keith Thompson <> wrote:

    > 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.
    Christopher Benson-Manica, Sep 29, 2006
    #6
  7. 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/~sgtatham/coroutines.html
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Sep 29, 2006
    #7
  8. Hallvard B Furuseth

    Mabden Guest

    "Harald van D?k" <> wrote in message
    news:...
    > 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/~sgtatham/coroutines.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.
    Mabden, Oct 2, 2006
    #8
  9. 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, Oct 3, 2006
    #9
  10. Rod Pemberton writes:
    > FYI, others have pointed out Simon Tatham's "Coroutines in C":
    > http://www.chiark.greenend.org.uk/~sgtatham/coroutines.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
    Hallvard B Furuseth, Oct 3, 2006
    #10
  11. 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.
    Christopher Layne, Oct 3, 2006
    #11
  12. 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
    Hallvard B Furuseth, Oct 3, 2006
    #12
    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. Jamie Risk

    Duff Device reference ...

    Jamie Risk, Oct 16, 2004, in forum: C Programming
    Replies:
    1
    Views:
    413
    Michael Wojcik
    Oct 20, 2004
  2. Christopher Benson-Manica

    A small question about Duff's Device

    Christopher Benson-Manica, Oct 21, 2004, in forum: C Programming
    Replies:
    2
    Views:
    306
    Michael Wojcik
    Oct 21, 2004
  3. Jan Richter

    duff's device / loop unriolling

    Jan Richter, Aug 19, 2005, in forum: C Programming
    Replies:
    19
    Views:
    678
    Tim Rentsch
    Aug 29, 2005
  4. Replies:
    10
    Views:
    703
  5. yawnmoth

    how does duff's device work?

    yawnmoth, Nov 9, 2008, in forum: C Programming
    Replies:
    7
    Views:
    318
    Phil Carmody
    Nov 9, 2008
Loading...

Share This Page