How Duff's Device Works • Hacker News Board

Re: How Duff's Device Works

#11

Post by ssp » Fri, Nov 12, 2010, 11:41 AM UTC

okmjuhb wrote: post #7

The history behind this actually goes the other way if I remember correctly; it was unclear for a time whether or not this sort of thing was allowed. The standard was modified so that Duff's device would be legal code after it was being used.

Tom Duff himself writes about it here:

http://doc.cat-v.org/bell_labs/duffs_device

In particular,

    The device is legal dpANS C. I cannot quote chapter and verse, but
    Larry Rosler, who was chairman of the language subcommittee (I think),
    has assured me that X3J11 considered it carefully and decided that
    it was legal. Somewhere I have a note from dmr certifying that all the
    compilers that he believes in accept it. Of course, the device is also
    legal C++, since Bjarne uses it in his book.

Re: How Duff's Device Works

#12

Post by [deleted] » Fri, Nov 12, 2010, 11:42 AM UTC

okmjuhb wrote: post #7

The history behind this actually goes the other way if I remember correctly; it was unclear for a time whether or not this sort of thing was allowed. The standard was modified so that Duff's device would be legal code after it was being used.

[deleted]

Re: How Duff's Device Works

#13

Post by Jach » Fri, Nov 12, 2010, 1:50 PM UTC

You can use this to implement coroutines in C when you're stuck without Python/Scheme/al.

http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

Re: How Duff's Device Works

#14

Post by anamax » Fri, Nov 12, 2010, 6:12 PM UTC

acqq wrote: post #5

yread wrote: post #3

Really interesting! But why wouldn't you copy the data in a simple while loop? What do you need the switch statement for?

Kids these days. I guess the OP didn't really understand everything or didn't bother to explain, especially my favorite bit about "computed goto" and the fact that if you code your compiler to emit assembly instructions with labels it's quite "natural" to implement it. Duff's device is an example of the "loop unwinding." Say you have n divisible by 8, then you can loop n / 8 times and have eight assignments in the lo…

> When such thing should be done? 1) If you measured your loop and it was too slow with a one assignment and one loop pass for every n. 2) you know that your compiler can't do the loop unwinding automatically -- modern compilers can do such things even if you write a normal loop if the compiler estimates that this can really help and when you give to it a specific direction to produce such code (e.g. aggressively optimize for speed).

Note that many compilers generate crappy code for duff's device. The switch statement, specifically the intermediate destinations, keeps them from generating good code for the unrolled loop body.

The compiled code can be so bad that a "not unrolled" loop to get to alignment followed by an unrolled aligned loop is significantly faster.

And, because this stuff is never simple, the fastest version may be range dependent, as in one version is faster for up to 100 elements while another is faster for more than 100.