Talk:Duff's device/Archive 1

Archive 1

Tom himself

Here is a fresh comment from Tom himself why he wrote it on the Lambda weblog (nexus of the sect of functional programming :-):

What was I reading to write that?
I knew enough to write that bit of code because I had read the source code for Dennis Ritchie's 
PDP-11 C Compiler, specifically the version shipped with Fifth Edition UNIX. It's a remarkable 
program -- it compiles a fairly sophisticated language, producing decent code, all in a 64K byte 
footprint.

Most of the syntax analysis is done by recursive descent, except for expressions, which are parsed 
by using precedence tables with what we called the Railway Siding algorithm when I was in school. 
Code generation is done by a table-driven tree-pattern matcher.

The whole compiler runs in two passes (uhh, actually seven if you count one for the preprocessor, 
one for the optional freestanding peep-hole optimizer and three for the assembler), but the 
organization is essentially single pass -- it was split in two for space reasons. The first pass 
does syntax analysis & typechecking and generates code for everything but expressions. (And maybe 
switch statements? It's been 30 years since I read the code.) Its output is an assembly-language 
code/data stream with embedded expression trees to be processed in the second pass.

If the machine it compiled for were still of contemporary interest, I'd recommend it to anyone 
looking for a good introduction to the practicalities of software design and implementation.

Presumably to keep the compiler's size managable, case labels are treated syntactically as 
ordinary goto labels with a number attached. There was a stack of switch statements, and whenever 
a case was encountered, a label went in the output and was recorded in the stack (with an error 
if the stack was empty, i.e. if no switch was active.) Since case labels weren't syntactically 
bound to switch statements, they could occur anywhere in the switch's body, including, for example, 
in the middle of a nested do-while statement.

By Tom Duff at Wed, 11/23/2005 - 17:54

Here is Tom's comment

--Marc van Woerkom 15:12, 2 December 2005 (UTC)

Missing information

There is no explanation in the text on why the pointer increment is missing from "to". —The preceding unsigned comment was added by Skypher (talk • contribs) 15:54, 28 January 2007 (UTC).

The canonical example of this is copying to memory-mapped I/O. —The preceding unsigned comment was added by 71.245.136.42 (talk) 06:18, 9 February 2007 (UTC).

There's nothing "canonical" about Duff's original example; note that the Duff's Device given in the article isn't even the same code as in his original email. The non-incrementing of to in his case is irrelevant to the working of the device and deserves at most a footnote, not its current confusing treatment as if it were a major issue (the fact that there's a library routine to copy isn't relevant, because there are many other ways to use the device that won't be found in a library routine, e.g. *to++ = func(*from++)).

Yes, there is:

Note that to is not incremented because Duff was copying to a single memory-mapped output register.

Kurosa 01:39, 22 February 2007 (UTC)

I really do not understand why keep this requirement of (count > 0) - if you rewrite it a bit, it can be zero:

Oops, made a mistake :)

/* this assumes count is signed */
switch (count & 7) {
	while ((count -= 8) > -1) {
		*d = *s++;
	case 7:	*d = *s++;
	case 6:	*d = *s++;
	case 5:	*d = *s++;
	case 4:	*d = *s++;
	case 3:	*d = *s++;
	case 2:	*d = *s++;
	case 1:	*d = *s++;
	case 0: ;
	}
}

Best regards,

 Ashot.

Put a better explanation for non-C programmers please...

I'm not so sure that a non-C programmer would get a lot of excitement/revulsion out of this --kibibu 01:15, 7 October 2005 (UTC)

The sort of explanation for a non-C programmer would be useful for those just starting to program in C as well. Also people wondering about this as the basis of coroutines and protothreads. Hackwrench 02:17, 7 October 2005 (UTC)

The only thing a non-C programmer needs to understand this article is a beginner's knowledge of C, which can be obtained the usual way and doesn't belong here. This holds even more so for understanding C implementations of coroutines and protothreads that use the same trick that Duff's Device uses (they do not use Duff's Device per se; as Duff wrote in his original email, "I have another revolting way to use switches to implement interrupt driven state machines [...]"). As for the rewrite, it adds an extra subtract, test, and branch for any multiple of 8, so it would be slightly more efficient to test for count == 0 as a special case -- which often isn't needed (when it is known that count can't be 0). -- Jibal 08:21, 6 April 2007 (UTC)

Your code does not compile. Code cannot exist in a switch-case before the first case-label. Adding a dummy "case -1:" there would work though. Ps. Please sign your comments with ~~~~. Bisqwit 13:28, 24 August 2007 (UTC)

I don't know what compiler you used but the code compiles just fine on my g++ compiler. The dummy is was not needed on this compiler. 8 September 2007

Missing Book

K&R's The C Programming language should probably be added to the list of books, since Stroustrup's is there. SavantEdge 23:43, 26 April 2007 (UTC)

I agree. I added it. Jeff Carr (talk) 05:57, 19 November 2007 (UTC)

One usage of the device is not listed

Apart from being used in the context of writing to a device. The device is also used to test C compilers and C++ compilers. Essentially, if the compiler freaks out on the code it isn't a true C or C++ compiler.

Also, as others said, there are other uses of the device other than writing to device. The *to++ = func(*from++) example is as such a more general use of the device.

I also think one should be explicite about telling that the switch is done outside of the loop. It seems that many people misses this detail - if the switch is done inside the loop you make the test each time and gain nothing and also it is not duff's device any more.

Alf —Preceding unsigned comment added by 217.144.227.22 (talk) 11:30, 9 January 2008 (UTC)

Irreducible flow graph?

Doesn't Duff's Device give you an irreducible flow graph, so that an optimizing compiler would most likely split it, giving one the same code as one would get handling the count % 8 bytes outside the loop? —Preceding unsigned comment added by 209.234.91.82 (talk) 15:59, 31 January 2008 (UTC)

Modern compilers

Shouldn't modern compilers already have some kind of loop unrolling optimization like this already?

I don't see any advantage of using this device, other than for historic reason.--Huntercool (talk) 10:37, 6 June 2008 (UTC)

Duff's Device targets a very special problem (serial copy to a register) that modern compilers are unlikely to have an optimization for. That said, the device itself is probably not useful for its original purpose, but the technique is still applicable. For example, it is possible to implement protothreads in pure C with the same nested switch/case construct. Rrelf (talk) 11:28, 11 June 2008 (UTC)

Compiler warnings

When I compile the example source on a linux box, I get:

% gcc -O2 -Wall -o duff-orig duff-orig.c
duff-orig.c:6: warning: return type of 'main' is not 'int'
duff-orig.c: In function 'main':
duff-orig.c:9: warning: implicit declaration of function 'atoi'
duff-orig.c:10: warning: implicit declaration of function 'send'
duff-orig.c: At top level:
duff-orig.c:14: warning: conflicting types for 'send'
duff-orig.c:10: warning: previous implicit declaration of 'send' was here

Therefore I would make the following suggestions:

• Fix main's return type, add a "return 0".
• Add an include for stdlib.h for the atoi prototype.
• Rename send to something not already used, like duff().
• Add a prototype for duff() above main().

The result compiles cleanly, here it is. Do these changes detract from the readability of the example?

/*
    duff.c
 */
#include <stdio.h>
#include <stdlib.h>

void duff(int count);
int main(int argc, char *argv[]) {
 puts("duff's device.");
 if (argc > 1) {
   int count = atoi(argv[1]);
   duff(count);
 }
 return 0;
}

void duff(int count) {
    if (!count) return;
    int n = (count + 7) / 8;
    switch (count % 8) {
      case 0: do { puts("case 0");
      case 7:      puts("case 7");
      case 6:      puts("case 6");
      case 5:      puts("case 5");
      case 4:      puts("case 4");
      case 3:      puts("case 3");
      case 2:      puts("case 2");
      case 1:      puts("case 1");
                 } while (--n > 0);
    }
}

It also seems a bit weird that the indentation for duff() and main() don't match. Infinoid (talk) 13:03, 11 July 2008 (UTC)

slashdot

This article has been linked from slashdot, so I just added the slashdotted template as a precaution. --Codemonkey 01:07, 7 October 2005 (UTC)

The mod 8 operation could be optimized at the cost of readability. Mod is a complex operation, and unless the compiler optimizes for the specific case of mod $2^{n}$ likely any performance improvements seen by using a jump table will vanish.

It is more optimal to use a logical and for the modulus and a logical shift for the division.

This also illustrates the importance of maintaining a length that is a power of 2.

--67.173.214.71 02:09, 7 October 2005 (UTC)

What do you mean that mod is a complicated operation? It comes free with every assembly DIV instruction. Hackwrench 02:29, 7 October 2005 (UTC)

Also why would the remainder be a loop? Hackwrench 02:29, 7 October 2005 (UTC)

Re: "[Mod] comes free with every assembly DIV instruction." Counting instructions can be misleading. On most processor implementations, not every instruction is born equal. For instance, on an Intel Pentium 4 processor, the DIV instruction takes 80 cycles, while a mask operation takes only 1 cycle (note: mod $2^{n}$ can be implemented as a mask operation, i.e., using the AND instruction). In other words, on an Intel Pentium 4, if you know that the divisor is a power of 2, your implementation of the modulus operation can be 80 times faster than the general case where nothing is known about the divisor and where you must fall back to use the DIV instruction. [A source for the instruction latencies is http://swox.com/doc/x86-timing.pdf].

Re: "Duff's Device is an optimized implementation of a serial copy." Tom Duff's device is not just about optimizing serial copy. It's more general than that. It's a way to express loop unrolling (or loop unwinding) in the C programming language. Optimizing serial copy is just one application of loop unrolling, there are many others. See point 1 of Tom's original usenet posting (available for instance there http://www.lysator.liu.se/c/duffs-device.html).

Re: "Based on an algorithm used widely by assemblers..." Loop unrolling is also implemented in many compilers (e.g., GNU's GCC). Since fewer and fewer folks write assembly anymore, loop unrolling is perhaps now more likely to be the result of a compilation.

If you're interested in optimization, the best thing you can do is throw any compiler that doesn't optimize for mod $2^{n}$ into the trash and use a decent one; writing less readable code to help out a non-optimizing compiler is penny wise and pound foolish. As for "maintaining a length that is a power of 2", Duff's Device handles any length (except 0); 8 is just the block factor for unrolling, which should indeed be a power of 2. Also, the jump table is a result of the case values being a non-sparse set of constants; it has nothing to do with powers of 2. Finally, Duff's Device does not obtain a performance improvement over a more straightforward loop unrolling implementation that uses an 8-at-a-time loop plus a switch statement for the leftover elements (the way Duff said he would "usually handle this"), it only reduces the number of lines of code by combining the loop and the switch statement. -- Jibal 08:47, 6 April 2007 (UTC)

Foolish? I learned long ago not to assume anything about what a compiler can and cannot optimize (hint: check the generated assembly code every once in a while to get a feel for what things cost.) In this case the function is taking a signed size for some reason, and on virtually all C compilers division/modulo round towards zero whereas shift/and round towards negative infinity. At best this means that the compiler might use some clever bithack to adjust the shift/and, and at worst (surprisingly often in fact) it won't bother and resort to a plain old division.--83.166.6.116 (talk) 22:05, 1 October 2008 (UTC)

Removing content

There currently are two source-code variants of the same concept in the article. The similarity between the two is very high, so i'm thinking about merging them to leave only one snippet. However, before i do such a thing, i'd like some feedback about it.

Also, there's this: "Its behavior is undefined if it is entered with count having the value zero.", with which i disagree. The behaviour is quite predictable: it will run a loop of roughly MAXINT iterations, copying the memory contents starting with *from... -- Jokes Free4Me (talk) 10:58, 11 June 2008 (UTC)

As far as I'm concerned, the second variant (the one that starts with "duff.c" in a comment) is entirely redundant and can be safely removed. Rrelf (talk) 11:25, 11 June 2008 (UTC)

I have removed the part with duff.c because:

1) it is unsourced or OR

2) This article is about the code that Tom Duff wrote and named, not about other, purportedly similar codes.

3) The last part of it reads like a manual.

4) It talks about fixing the count == 0 bug, but the original code was clearly described as not working for count == 0, so this is not a bug.

Lklundin (talk) 19:58, 20 November 2008 (UTC)

C-FAQ.com explanation

This is another comprehensive explanation: http://c-faq.com/misc/duffexpln.html —Preceding unsigned comment added by Parallelized (talk • contribs) 13:50, 15 February 2009 (UTC)

legal C by virtue of the relaxed specification of the switch statement

I know this may seem heretical, but to me the reason Duff's device is non-obvious is because of the relaxed specification of the While statement: it is legal to jump into the centre of a While statement, and the Switch statement is used as a way of adding the jump-to-the-middle.

Look at it again: What is special about the switch statement? Nothing. What is special about the While statement? It has a jump to the middle.

The idea of structured programming was that programming could be done using structures, where a structure was something like a "function" or an "object". Using these higher level structures would make programming faster and more correct.

A structured programming language was a programming language that had structure built in. Just like it is possible to do object-oriented programming in a non-object oriented language (the first versions of C++ used the C compiler and a macro language), it is possible to do structured programming in a non-structured language: you construct "while" loops out of "goto" statements.

But the point of structured programming is to use the structures as fixed ideas. In particular, Do,While,For are supposed to have single, fixed entry and exit points. Duff's device subverts our expectations of the While loop by not entering the While loop at the While.

I don't see that it subverts our expectations of the Switch statement in any way. —Preceding unsigned comment added by 203.206.162.148 (talk) 07:37, 11 December 2009 (UTC)

Agreed. There are two things here that may be unintuitive for programmers: fall-through between switch cases and jumping into the middle of a loop. Of these two, the first is well-known to every C programmer while the second is far less so, and is what made me surprised by the device. 84.108.59.222 (talk) 12:07, 1 February 2010 (UTC)

memcpy is not equivalent

In case of overlapping to and from areas, memcpy is not equivalent. overlapping copies are often used in (lzss-based) compression algorithms. 109.192.116.219 (talk) 09:41, 1 June 2010 (UTC)

memcpy() is not equivalent to this code EVER. This code copies from an array of several memory locations to a single location, where memcpy() copies from one array to another. 75.137.114.54 (talk) 05:53, 23 May 2011 (UTC)

"volatile" keyword needed?

Isn't it necessary here to declare "to" as a pointer to a volatile short? Otherwise, I'm thinking that an optimizing compiler, seeing that the value of "to" never changes, could generate code that only performed a single store into "*to" for each call to the send() function. That optimization would be appropriate behavior for "to" being a pointer to a RAM location, but not for "to" being a pointer to a memory-mapped I/O device. — Wdfarmer (talk) 02:39, 15 May 2011 (UTC)

This is true for most modern compilers, but the original code was targeted at a 1980s compiler that didn't do anywhere near as much optimization as modern ones do. As such, the volatile keyword didn't exist, any memory reference resulted in an actual memory reference. 75.101.123.180 (talk) 10:24, 9 June 2011 (UTC)

Historically speaking...

From the article:

The primary increase in speed versus a simple, straightforward loop comes from loop unwinding, which reduces the number of branches performed (which are computationally expensive due to the need to flush - and hence stall - the pipeline).

Did CPUs even have pipelines in 1983? —Preceding unsigned comment added by 75.186.5.185 (talk) 08:05, 31 March 2011 (UTC)

Even the earliest SPARCs come a couple years afterwords, but this portion of text is from a modern perspective. There is a rather more serious problem with this text in the article. In the next sentence, referring to XFree86, what is referenced is a mention of removal of instances of Duff's Device from XFree86 shrinking it by a large amount. This is unrelated to pipelining and branch prediction, but instead of cache usage. 75.101.123.180 (talk) 10:33, 9 June 2011 (UTC)

PHP version

(this text is a "wiki formatted copy" from PHP Manual, For (loop), User Contributed Notes, bishop 17-Jul-2003)

This is a modified form of Duff's original device, because PHP doesn't understand the original's egregious syntax.

        $n = $ITERATIONS % 8; 
	while ($n--) $val++; 
	$n = (int)($ITERATIONS / 8); 
	while ($n--) { 
	    $val++;     $val++;     $val++;    $val++;     
	    $val++;     $val++;     $val++;    $val++; 
	}

That's algorithmically equivalent to the common form:

	for ($i = 0; $i < $ITERATIONS; $i++) { 
	    $val++; 
	}

$val++ can be whatever operation you need to perform ITERATIONS number of times.

Example of average run time across 100 samples with ITERATIONS = 10000000 (10 million) is:

Duff version:     7.986 s 
Obvious version: 27.608 s

--Krauss (talk) 09:59, 26 July 2011 (UTC)

As far as I can read PHP the above is not equivalent to Duffs device, but just an example of loop unrolling. The defining characteristic of Duffs device is that it handles any remaining iterations in loop unrolling by interleaving a switch statement with the (do-while) loop. Lklundin (talk) 13:33, 26 July 2011 (UTC)

minor simplification

Since the whole point of the device seems to be source code optimization, it might be worthwhile to notice that the brackets in the switch statement are redundant. That is, the following is also valid C:

dsend(to, from, count)
char *to, *from;
int count;
{
    int 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);
}

— Emil J. 17:39, 4 November 2008 (UTC)

The ORIGINAL goal of Duff's device had nothing to do with gratuitously creating obscure source code syntax; it was a strategy to modify the source code to work around early C compilers' deficiencies in optimizing the execution speed of certain types of loops. Omitting the brackets around the switch statement would not be expected to have any impact whatsoever on the compiled output, so keeping the original goal in mind, there's no benefit in omitting them.

Granted, this entire exercise demonstrates some fairly controversial syntax which can easily obscure the actual operation being performed by the loop, so adding a little bit more syntactical mystery doesn't really hurt. But personally, I would defer to the common convention that switch blocks are always surrounded by brackets.

With modern processors, and modern C compilers' more advanced optimization capabilities, the more straightforward construct will often be just as effective (if not more so), so this entire technique is probably only relevant for historical purposes, or for very specialized, extremely speed-sensitive scenarios where it can be positively demonstrated that the more straightforward approach yields sub-optimal execution speeds for a specific combination of compiler and hardware. 24.222.2.222 (talk) 17:25, 5 August 2014 (UTC)

This is an interesting, but *bad* idea.

I wish there were a way to place universal caveats about coding style. You don't ever code for a competent seasoned engineer to read, you code for a mid-level engineer hopped up on caffeine at 3am to read. Cascading fall-throughs like this are just silliness and trouble waiting to happen.Tgm1024 (talk) 15:09, 20 November 2014 (UTC)

Hello! This, in general, isn't a forum; however, programming is pretty much like advertising – everything is about the target audience. Like there isn't much advertising around high-end server-class motherboards, for example, there's also code that simply isn't intended to be maintained later by caffeinated Joe Averages. :) — Dsimic (talk | contribs) 21:48, 21 November 2014 (UTC)

Bad metaphor: In an ad, you know roughly who the target audience is simply by the placement of the ad (the correct magazine, etc.) And if it's a general placement without target (a billboard for example), then the non-targets simply ignore the message. Code is different: You cannot code for a non-caffeinated high-end engineer down the road.....you have no idea who will be handling things, and he has no ability to "ignore the billboard". Besides, the most senior guys in the world will have a hard time with such things late at night (and after 12 diet cokes) just trying to meet a crazy deadline. Defensive programming is a critical concept. The idea of "just get better engineers" has always been broken logic.

Now I don't buy into this concept in all cases. For instance, the witch-hunt against the goto still in 2015 seems to have legs when it should not, and there are still people advocating "if (0==variable)" in languages like C where assignments are also expressions, and banning multiple returns from functions/methods, all of which are good examples of over-kill "nanny coding". But when it comes to absurd idioms like this crazy crap:

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

....then you have to start putting down the ego and start thinking about clarification instead. Yes, we all know what it does. No, that doesn't mean it's a good idea.

Tgm1024 (talk) 20:37, 25 January 2015 (UTC)

Well, it's perfectly fine if we disagree on something. However, I still don't think that dumbing everything down is the way to go in all environments; if we'd take that route, why should anyone use C in the first place? Programming in something backed by a virtual machine is always much better for deadline-pressured caffeinated juniors, seniors, or whoever you refer to. Also, I've seen a lot of awfully bad C and C++ code written by those "take it easy" developers, which was so bad that equivalent but well-written PHP code ran faster with all the overheads of interpreted execution. Also, I've seen a whole lot of awful PHP code. In a few words, there's no substitute for real knowledge – neither the choice of language nor complex or simple constructs help if one doesn't know what he or she is doing. — Dsimic (talk | contribs) 23:29, 26 January 2015 (UTC)

Please, this talk-page is reserved for discussions on how to improve the article. It is not a forum for discussion of programming. Please continue only with specific suggestions on how to improve the article. Lklundin (talk) 07:46, 27 January 2015 (UTC)

Well, that's exactly what I've said back in November 2014: "this, in general, isn't a forum". — Dsimic (talk | contribs) 07:55, 27 January 2015 (UTC)

Potential reference

• Holly, Ralf (August 1, 2005). "A Reusable Duff Device". Dr. Dobb's Journal.

Lesser Cartographies (talk) 02:35, 18 September 2015 (UTC)

Hello! That's a great find, thank you; added it into the article as a reference. — Dsimic (talk | contribs) 08:33, 18 September 2015 (UTC)

This article is about a specific piece of code

This article is about a specific piece of code, written by Tom Duff. Much like the Egyptian Pyramids, the purpose of this article is not for editors to modify the original design with what they consider improvements to this design. And please list only alternative implementations via a WP:RS. The same goes for comments on the usefulness of the code. @Sbmeirow: Therefore, please revert your edit. Thank you. Lklundin (talk) 18:08, 10 October 2015 (UTC)

1) Removing or adding white space isn't changing the code, and nothing you listed is a valid reason to revert those white space changes. • Sbmeirow • Talk • 21:22, 10 October 2015 (UTC)

2) The code in "Simplified explanation" section is NOT the original Duff's code that was originally posted on the USENET or BBS. I just now opened up the Dr Dobbs article and looked at it, and wow, guess what, my code changes (>>3 and &7) that you reverted were actually in this article, so it's actually back on you for being overly aggressive on your reverts.

3) Simple code optimization are similar to English grammar changes, and a person doesn't have to provide a cite obvious mathematical statement like "1 + 1 = 2". See Wikipedia:You don't need to cite that the sky is blue and Wikipedia:Common knowledge.

• Sbmeirow • Talk • 21:22, 10 October 2015 (UTC)

Hello! While the new "Improvements" section introduced in Sbmeirow's initial edits surely doesn't belong to the article due to its original research nature (clearly, no references were provided), whitespace and code formatting changes restored in Sbmeirow's subsequent edit are rather fine because the Duff's device § Simplified explanation section describes a functionally equivalent version of Duff's device. — Dsimic (talk | contribs) 22:52, 10 October 2015 (UTC)

Hello Dsimic, Thanks for chiming in and explaining the inappropriately and misleadingly summarized edit by Sbmeirow. Lklundin (talk) 06:01, 11 October 2015 (UTC)

You're welcome, and I'd just add that it's all about discussing any issues that may arise along the way. — Dsimic (talk | contribs) 06:07, 11 October 2015 (UTC)

A) My edits clearly don't deserves the abusive term "misleadingly" as stated by Lklundin.

B) Compare my code example to code that is half way down this reference from the article, a section called "A Reusable Duff Device", then it's very obvious my code example is similar to the Dr Dobbs article.

C) Concerning my original edit "The original code was written in an era where variable declaration was lax. Newer compilers will complain about the lack of a type for count and n.", which is common knowledge for engineers/programmers so this doesn't fall under "original research" either. It's amazing this article does NOT state these code examples are ancient K&R C coding style, instead of modern ANSI C/C89/C90/C99 coding style. This is basically the point of my edit, which I should have stated differently, yet still neither is "original research".

D) This article needs an ANSI C or preferred C99 memory copy example near the bottom, because this is 2015 not 1983. Actually the code in "Simplified explanation" section should be "ANSI C" compliant at a minimum, instead of the out-dated crappy K&R style that new compilers don't support by default.

E) We need more coding examples in all Wikipedia coding articles, even if they fall under the blatantly abused description of "original research". Coding newbies have migrated to StackOverflow and StackExchange, thus we need to come up with a better way to improve coding articles, and quit using "OR" as a lame excuse for not doing it.

• Sbmeirow • Talk • 10:13, 11 October 2015 (UTC)

Look, it's great that you are such an exceedingly knowledgeable programmer. The thing is just that per WP:NOTTEXTBOOK it is not needed here. Oh, and try to understand the difference between an adjective and an adverb (as in e.g. "inappropriately and misleadingly summarized", as opposed to the completely different use of adjectives to describe a noun such as "edits"). All the best, Lklundin (talk) 11:04, 11 October 2015 (UTC)

Please, let's keep in mind that Duff's device presents pretty much an important programming artefact. As such, having "crappy", outdated K&R coding style actually helps in reflecting the historical nature, IMHO. However, mentioning in the article that the used style is K&R would be only beneficial. — Dsimic (talk | contribs) 14:38, 11 October 2015 (UTC)

Stroustrup's version

I don't believe that it is Stroustrup's version at all. In 'The C Programming Language' by Kernighan and Ritchie they say that the most important conceptual code in the c programming language is "while(*dst++=*src++);". I havent read that book in more than a decade, but that code is in there.

Without seeing what is actually written in Stroustrups derivative of the c programming language (book and language), I can not say for sure that I gotten this context wrong. Regardless, the syntax as shown in the example is c-code NOT c++.

Therefor I nominate the section for delete, as it is wrong. — Preceding unsigned comment added by 86.12.140.205 (talk) 15:40, 10 March 2016 (UTC)

Well, the content in the Duff's device § Stroustrup's version section is backed by a reference, which I just checked to be correctly cited – it matches exactly what's on page 141 in Bjarne Stroustrup's book The C++ Programming Language. Thus, the section is perfectly fine. — Dsimic (talk | contribs) 19:26, 7 April 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Duff's device. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added {{dead link}} tag to http://www.l33tskillz.org/usenix2003/notes/t-09-5/
• Added archive https://web.archive.org/web/20051013062233/http://www.sics.se:80/~adam/pt/ to http://www.sics.se/~adam/pt/
• Added archive https://web.archive.org/web/20080828170858/http://www.eigenclass.org/hiki/threadring-with-protothreads to http://eigenclass.org/hiki/threadring-with-protothreads

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 12:50, 17 December 2016 (UTC)

0 case

This is nitpicking, but maybe a warning should be added that the current printed algorithm is incorrect for the case count = 0 (1 iteration too much). — Preceding unsigned comment added by 89.144.199.7 (talk) 13:31, 26 June 2022 (UTC)

"This code assumes that initial count > 0." --John (User:Jwy/talk) 16:39, 26 June 2022 (UTC)

Code Example modified

I used a define to specify an imaginary IO port as in Duff's original prog quoted in DrDobbs Journal cited above. Using the construct

   **to = **from++

looks too much like the many memory copy related routines where "**to" is a variable pointer pointer to a destination in memory that would need to be incremented. Indeed, I looked at the sources on this page and tried to write an example program that showed the behavior (and didn't increment the destination pointer resulting in the example not working. As such, it was a confusing example that hid the way duff's algorithm actually worked.

The central point of this article should be the focus on combinining the switch and loop constructs into 1 entity -- the fact that Duff's code needed to specifically write to a contant Hardware address was secondary.

Additionally, parameterizing the "to" destination also makes it seem like the destination should be parameterized, when in fact, it would be a specific, HARD-CODED address in memory that wouldn't change for the life of the HARDWARE.

Calling a routine "sendto_<name of HW-port>" makes it even more clear that this specific implementation was for a specific piece of HW, and not a general purpose example. (Astara Athenea (talk))

@Athenae: It does not matter what you think about Duff's device. This article is about a piece of code written more than 30 years ago and you are not supposed to change (and thus utterly ruin) Wikipedia's description of that code. Please revert your changes ASAP. Thanks. Lklundin (talk) 09:11, 22 January 2017 (UTC)

@Lklundin: But the example that was presented wasn't what Duff wrote. If you follow the references -- especially the one to Dr. Dobbs Journal, you'll see that his original example used an "ALLCAPS" constant for the name of the IO_PORT, not "*to". If you want it to be historically accurate, the ALLCAPS version specifying an I/O port is closer. If you want the exact text, you can copy it from the Dr. Dobbs article -- that's fine with me if it is fine with Wikipedia standards. However, the article is talking about "Duff's Device" -- not Duff's program, or Duff's code, but the "Device" of overlaying the switch statement on top of a loop as a compact, though unusual way to perform strength reduction. In that light, it would make more sense to show an example in the context of what "C programmers" would commonly understand and deal with -- like copying memory from 1 location to another using the 1st change I inadvertently proposed using "*to++ = *from++". That didn't highlight his usage of using an ALLCAPS "#define" constant for the "to" destination. I did my homework -- his original program can be seen @ http://www.drdobbs.com/a-reusable-duff-device/184406208 . He later wrote up is device and presented it to bell labs in this (http://doc.cat-v.org/bell_labs/duffs_device) paper. NOTE, he says the algorithm on the 2nd source is an ***abstract***. It's not the one that he originally used as the wikipedia article seems to indicate. Please read both sources and note which claims to be the original and which claims to be an "abstract". Wikipedia quoted the abstract page -- not his original work.

In light of that, do you still believe my edits should be reverted, and if so, why? Do you want his original code from the "Dr. Dobb's" article, verbatim? I would have no problem with that -- the issue of clarity and intent are served by either my revision, or his original code.  ???

@Athenae: You are mistaken. You seem to be laboring under the false assumption that the cited Dr. Dobb's article shows Duff's original code, but it does not. The article as it was before you made your changes did show Duff's original code that he posted to Usenet in 1983 (and again in 1988). This is what the article is supposed to show, not some different version. Whether you consider your own versions to better demonstrate clarity and intent is irrelevant. So once again, please reinstate the original version of this article. Thanks, Lklundin (talk) 14:38, 23 January 2017 (UTC)

And somewhere in there the text is out of sync with the code example. Pretty confusing. --John (User:Jwy/talk) 21:03, 24 January 2017 (UTC)

I've reverted. If you are looking for clarity, its more important that the text match the code. --John (User:Jwy/talk) 21:10, 24 January 2017 (UTC)

Thanks. It is important for all editors to understand that this article is about a specific piece of code, and that therefore attempts to 'improve' it are misplaced. Lklundin (talk) 10:38, 25 January 2017 (UTC)

You are welcome, but I don't quite agree: It would seem its about an algorithm and the important thing is that it is described clearly. I like keeping the original formulation, but those unfamiliar with a "memory-mapped register" might be distracted by that "wierdness" and miss the point. But then again, the motivation for the efficiency of the algorithm is lost if you don't have that. --John (User:Jwy/talk) 16:46, 25 January 2017 (UTC)

Please be aware that the contested code is listed under the heading Original version, which clearly is not subject to attempts at clarification. Also, Duff's Device is clearly a specific implementation of a given algorithm. The developer named the code after himself, per his Usenet posting. Lklundin (talk) 17:24, 25 January 2017 (UTC)

@Lklundin: "It is important for all editors to understand that this article is about a specific piece of code" I don't agree that this article is about documenting a particular historic event; "Duff's Device" refers not to a particular piece of code that Duff wrote, but to a technique Duff discovered for solving a particular class of problems by intermingling a switch statement with a loop. 2603:8001:D3F0:87E0:0:0:0:1DF6 (talk) 01:06, 6 March 2023 (UTC)

@Lklundin: -- The article at Dr. Dobbs says that they are showing Duffs original code that he also wrote about in "a historic e-mail by Tom Duff that he wrote to Dennis Ritchie, see http://www.lysator.liu.se/c/duffs-device.html". In that article, Tom is talking about the algorithm and publishes ***an abstraction*** of the actual code: "Consider the following routine, ***abstracted*** from code which copies an array of shorts into the Programmed IO data register of an Evans & Sutherland Picture System II". The abstracted code *doesn't show the specific **register** used (as his original does). He wrote both copies, but the source "himself", calls the version cited on the DuffDevice page, an ***abstraction*** of the real code. Please confirm your understanding that an "abstraction" is not the same as the original code. and @Jwy: -- please consider your reversion as it doesn't quote Duff's original code and doesn't look anything like his original code, compared to the version I put up (I hesitated to post a verbatim copy of the original, due to ownership claims, but considering the context, it might not be out of place).

As I mentioned before, I wouldn't be adverse to putting either Duff's original code or my modified version in place as being the *original*. Nor do I have issue with calling the version not showing the Evans & Sutherland Picture System II's hardware port an "abstraction" (and keeping it as the author's (Duff)) revision of the code for "public consumption/posting" on USENET. But to claim that the code on the article page is his original that shows it talking to a specific piece of hardware -- the Evans & Sutherland Picture System-II, is patently false -- there is no mention of its port or sign that it was talking to that device -- unlike the version published in Dr. Dobbs.

I also feel that, the 'abstracted' version obscures what it is that is actually "Duff's Device". If the article is to be clear about what "Duff's Device" should be, it should show the code where the target is either an ALLCAPS-HW-DEFINED-PORT or as a way to copy memory (*to++=*from++). @Jwy: -- I'm not sure what you mean by "the motivation is lost" -- as using the same "Device" to copy memory from/to a source/destination in memory would also result in a measurable performance boost.

As for the imporantance of clarity -- I have a B.S. degree in Computer Science & decades of work experience, and I found the the example unclear. The example in Dr. Dobbs article made it clear, as it showed the HW-PORT in a #define and didn't try to "parametrize" (as the abstract does) what was a hard-coded example for a specific piece of HW.

Astara Athenea (talk) 28-Jan-2017

@Athenae: My interest in reverting was clarity and laziness. As it stood before I reverted, the commentary around the article was referring to variable names that were not in the example. I did not have time or interest to make the changes there to match it up - that would be the responsibility of the original editor that created the mis-match. The easiest way to resolve that problem was to revert back to something that made much more sense. I don't have a horse in the game otherwise. --John (User:Jwy/talk) 03:40, 29 January 2017 (UTC)

@Athenae: I am sorry, from your lengthy comment I fail to see a specific proposal for how to improve the article. Lklundin (talk) 10:34, 29 January 2017 (UTC)

@Jwy: @Lklundin: -- well I'm not real hot on rewriting the article at this point, but it seems the Dr.Dobbs section should come first as an example of his original code -- then the existing examples of what he sent off in his email with his "abstracted" code... then, *maybe*, another example showing Duff's dev used in a classic memory copy routine and how, even there, the reduction in #loops by a factor of 8 speeds up that as well. But that's alot of rewriting and I'm a computer scientist, but not a very good, _concise_ writer unless I spend a fair amount of time in multiple revisions cutting things out from my 1st or earlier attempts.

I dunno, Lklundin _seems_ to have more of a history w/this article than I, if he wants to add a 'lead-in' w/the original code that would seem to clarify the historical points as well as providing 2 different looking examples that should make it easier for readers to abstract the key points -- or I could write-up a third example showing a memcpy (it would be trivial, so if Lklundin wants to do that as well, I'm not attached to the idea.

My involvement came from being confused by the original article's point and getting clear after seeing the 1st version showing ports and stuff -- then I understood the 2nd was a 1st attempt at abstracting the algorithm...

Comments? Astara Athenea (talk) 29 Jan 2017

@Athenae: Since Wikipedia has no concept of ownership you should not feel compelled to ask specific, previous contributors for feed-back regarding your suggestions for improvements. Before you start editing the article I would caution you though, to take a moment and reflect on the fact that so far your edits to the article have not been constructive. You repeatedly modified code that was clearly described and sourced as being a verbatim copy of a specific historical code. Your first edit summary clearly shows that you failed to read and understand the intention of the code. After having had this pointed out to you, you then went on to 'improve' the verbatim copy of a historical code, again displaying a lack of understanding of this article. When asked (by me) to self-revert you did nothing for 60 hours, at which point another editor reverted your edits. With that start, your addition of your own code examples motivated by the hope of clarifying an already concise and well explained code, is maybe not the best next step to take. Remember that Wikipedia is a collection of information collected from external sources, so your own, personal idea of what constitutes a clarification may not be universally accepted. Good luck. Lklundin (talk) 15:28, 30 January 2017 (UTC)

References

There isn't anything wrong with adding new sections at the bottom of the article. • Sbmeirow • Talk • 17:36, 25 January 2017 (UTC)

Change code to better reflect use

The use of the pointer "to" is unclear as we are either overwriting the same section of memory over and over again (and not the contents of a register @Jwy) or writing to a second part of memory (by adding ++ after *to in all examples) which I feel diverges too far from the source material. SetOfAllSets (talk) 18:44, 12 October 2023 (UTC)

The register keyword gives the compiler a hint to move the pointer to "to" into a register SetOfAllSets (talk) 18:45, 12 October 2023 (UTC)

The supplied code is exactly what is quoted in Reference 2. Since this section is labelled "Original version", it shouldn't be modified to match our current opinions on programming. --SarekOfVulcan (talk) 20:12, 12 October 2023 (UTC)

As explained in the text, "Duff's problem was to copy 16-bit unsigned integers ("shorts" in most C implementations) from an array into a memory-mapped output register, denoted in C by a pointer." While it is confusing if you are unfamiliar with such hardware and how C might deal with it, it is the original code and that it is a register is actually immaterial to the algorithm. And (I _think_) the algorithm is mostly of historical interest as most modern languages/compilers take away the need for this level of optimization by the programmer. Since it is of historical interest, the original code is most appropriate. --John (User:Jwy/talk) 19:09, 14 October 2023 (UTC)

Digging into the references, I see how the use of the register is of importance:

In the "Subject: Re: Explanation, please!" reference, Mr. Duff himself says:

It is claimed:

...the device wouldn't exhibit the desired speed-up. The argument was flawed in two regards: first, it didn't address the performance of the device, but rather the performance of one of its few uses (implementing memcpy) for which many machines have a high-performance idiom. Second, the poster made his claims in the absence of timing data, which renders his assertion suspect. A second poster tried the test, but botched the implementation, proving only that with diligence it is possible to make anything run slowly.

The algorithm probably would not help if it were memory to memory copy (memcpy would probably be faster). Its only when it is NOT memory to memory but memory to register that is is useful! --John (User:Jwy/talk) 19:53, 14 October 2023 (UTC)

@Jwy "memory to a register" the register keyword hints to the compiler to do that for you, duff's device would be copying to a variable moved into a register and overwriting the contents of the variable repeatedly in the example. 2600:1700:4540:3D10:275A:2F43:F4B7:2395 (talk) 23:09, 16 November 2023 (UTC)

@2600:1700:4540:3D10:275A:2F43:F4B7:2395 this was me, I forgot to log in on my phone SetOfAllSets (talk) 23:11, 16 November 2023 (UTC)

I know. And the text SAYS its memory to register. My point is that the editor's change to make it memory to memory - besides changing the original magazine article's program - is not desirable. --John (User:Jwy/talk) 04:11, 17 November 2023 (UTC)

Including the “modern C” version

@SarekOfVulcan has repeatedly removed my addition of the snippet of code with explanations of outdated syntax, and has even gone so far as to request page protection, even claiming that there was a talk page dedicated to discussing this change, when this is obviously not true. The bottom line is, that I have sourced my edits and the edits are relevant content-wise to the topic, and do not detract from the original topic of interest. ~2025-35430-19 (talk) 16:08, 21 November 2025 (UTC)

It was the wrong snippet of code that was updated, rather than the device itself. While I acknowledge this mistake, I believe nonetheless the page ought to provide the “modern C” version and explanations of other things, such as the K&R parameter list used. ~2025-35430-19 (talk) 16:21, 21 November 2025 (UTC)

My objections stand. The article doesn't need a long sourced discussion about how C has changed since Duff first wrote this code, and the "modern C" version is barely different from the code as originally written. And given that the code as originally written took advantage of a memory-mapped output register that likely is not going to show up on modern machines, and if you change it to remove that, the compiler will probably optimize it into something faster anyway, there's no need to include the "modern" version and make the article longer for no actual gain.--SarekOfVulcan (talk) 21:38, 21 November 2025 (UTC)

Your claim that the article doesn't need a long sourced discussion about how C has changed since Duff first wrote this code is not only unrepresentative of my proposed changes, but it is further destructive to assert this. The way you phrase this suggests that there is an entire section dedicated to explaining what version of C it was or how C is different now, when all I had done was include the snippet of code as well as two sentences explaining the difference. While I acknowledge that compilers and optimisations have evolved significantly since K&R C, compiler optimisations are beyond the scope of the article's content (aside from discussing whether register is really necessary or not), and code is provided notwithstanding of whatever compiler is used to compile it. This argument is essentially equivalent to claiming that a page containing excerpt from Beowulf need not to have a modern English translation because a concept or phrase from Old English is lost in translation to modern English. Furthermore, nothing justifies the claim that "nothing is gained" from the article through its inclusion, especially when the proposed changes are both adequately sourced, concise, and relevant to the content. For the aforementioned reasons, the content is relevant and therefore provides constructive addition to existing written content. ~2025-34236-49 (talk) 01:25, 22 November 2025 (UTC)

"adequately sourced, concise, and relevant" is not the same as "useful". SarekOfVulcan (talk) 02:24, 22 November 2025 (UTC)

What part of "relevant" is not "useful"? ~2025-34236-49 (talk) 08:44, 22 November 2025 (UTC)

@SarekOfVulcan If I do not hear back I will apply WP:SILENCE and proceed with my changes. You have made next to zero effort to refute my points. ~2025-36699-87 (talk) 05:56, 30 November 2025 (UTC)

At that point, two people had disagreed with you, nobody had agreed. That's not how SILENCE works. SarekOfVulcan (talk) 19:57, 30 November 2025 (UTC)

You don't get to cover your ears and claim "I can't hear you", or sit on your hands and make zero effort to disprove or counter my points. If hundreds of people spam the talk page of Periodic table with "Helium is the second element of the periodic table" we aren't obliged to make this change just because an overwhelming amount of people make this claim. The closest thing I can even claim is resembling a countering of my points is you stating that "you don't like this change". ~2025-36699-87 (talk) 23:05, 30 November 2025 (UTC)

I don't believe the modern code snippet adds useful information to the article. --John (User:Jwy/talk) 06:50, 22 November 2025 (UTC)

Yeah, and I believe unicorns exist, but that doesn't mean anything if I don't substantiate my claims. ~2025-34236-49 (talk) 08:44, 22 November 2025 (UTC)

Why don't we do this:

== Duff's technique ==

Duff's problem was to copy 16-bit unsigned integers ("shorts" in most C implementations) from an array into a memory-mapped output register, denoted in C by a pointer. His original, un-optimized, K&R C code, looked as follows:

:send(to, from, count)
:register short *to, *from;
:register count;
:{
:    do {                          /* count > 0 assumed */
:        *to = *from++;
:    } while (--count > 0);
:}
:

Note that an unspecified type (such as count) defaults to int, and send() defaults to type void, so in later version of C the method signature would be:

:void send(short *to, short *from, int count)
:

--John (User:Jwy/talk) 06:59, 30 November 2025 (UTC)

References

I'd be content only showing the modern C method signature for this, actually. It doesn't even need to have its own paragraph, it can reside in the same sentence as the explanation of types. ~2025-36699-87 (talk) 10:40, 30 November 2025 (UTC)

That's what I'm suggesting above, I think, plus linking to the "K&R C" paragraph rather than the whole article. --John (User:Jwy/talk) 15:27, 30 November 2025 (UTC)

I'm still not clear why we're forcing a description of why-modern-c-doesn't-look-like-this into a discussion of a 40-year-old coding technique that isn't particularly used any more. SarekOfVulcan (talk) 20:01, 30 November 2025 (UTC)

And yet above you tried to pull the "two people disagree with you" card. We include it for the exact same justification why when we provide an excerpt of Beowulf we provide a translation in modern English. Just because the English language doesn't look like that anymore and it comes from a poem more than a thousand years old doesn't change a thing. ~2025-36699-87 (talk) 23:07, 30 November 2025 (UTC)

A description is already there explaining the types those unfamiliar with K&R C would consider missing (I haven't tried, but apparently it will stil compile with warnings). My suggestion only adds the signature to complete that picture. Repeating the body of the method is unnecessary, but I think the single line signature doesn't overdo it. --John (User:Jwy/talk) 01:25, 1 December 2025 (UTC)

I agree, there is virtually no harm in its inclusion nor any bloat to the article. On the contrary, not everything about antiquated C is obvious to the reader at first glance. ~2025-36699-87 (talk) 04:24, 2 December 2025 (UTC)

Adding this as per consensus (two editors agree on its inclusion) and that the one who objects hasn't made any effort to elaborate why. ~2025-36699-87 (talk) 00:55, 3 December 2025 (UTC)

to++

I can assure you that Tom Duff did not forget to auto-increment the destination pointer. All this sophistry to excuse publishing someone's incorrect version of his code, sigh... ~2025-40163-45 (talk) 23:16, 12 December 2025 (UTC)