Talk:Duff's device

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)

The article is clear. Here traces for count=1 to 16

The article is clear. Here are traces from count=1 to 16, some may be picked to insert in the article. I didn't attempted to change the article because it is clear to me. But this can be clearer for some readers. I don't know if it is possible to hide and show the code clicking a button. If it is not possible, maybe the trace for code=10 is more illustrative. This discussion is short, if the traces become obstructive for reading, because it is not possible to hide and show them clicking a button, leave the more representative 1,7,8,10,16 cases to delete the rest.

void send(to, from, count:=1)
  register short *to, *from;
  register int count;
{
  assert(count<1> > 0);<True>
  predicate(0 == (count % 8)<1>)<False>
  register n<1> = (count<1> + 7) / 8;
  switch(count<1> % 8)<1>
  {
    case 1:      *to = *from++;
               } while (--n<0> > 0);
  }
}

void send(to, from, count:=2)
  register short *to, *from;
  register int count;
{
  assert(count<2> > 0);<True>
  predicate(0 == (count % 8)<2>)<False>
  register n<1> = (count<2> + 7) / 8;
  switch(count<2> % 8)<2>
  {
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<0> > 0);
  }
}

void send(to, from, count:=3)
  register short *to, *from;
  register int count;
{
  assert(count<3> > 0);<True>
  predicate(0 == (count % 8)<3>)<False>
  register n<1> = (count<3> + 7) / 8;
  switch(count<3> % 8)<3>
  {
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<0> > 0);
  }
}

void send(to, from, count:=4)
  register short *to, *from;
  register int count;
{
  assert(count<4> > 0);<True>
  predicate(0 == (count % 8)<4>)<False>
  register n<1> = (count<4> + 7) / 8;
  switch(count<4> % 8)<4>
  {
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<0> > 0);
  }
}

void send(to, from, count:=5)
  register short *to, *from;
  register int count;
{
  assert(count<5> > 0);<True>
  predicate(0 == (count % 8)<5>)<False>
  register n<1> = (count<5> + 7) / 8;
  switch(count<5> % 8)<5>
  {
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<0> > 0);
  }
}

void send(to, from, count:=6)
  register short *to, *from;
  register int count;
{
  assert(count<6> > 0);<True>
  predicate(0 == (count % 8)<6>)<False>
  register n<1> = (count<6> + 7) / 8;
  switch(count<6> % 8)<6>
  {
    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> > 0);
  }
}

void send(to, from, count:=7)
  register short *to, *from;
  register int count;
{
  assert(count<7> > 0);<True>
  predicate(0 == (count % 8)<7>)<False>
  register n<1> = (count<7> + 7) / 8;
  switch(count<7> % 8)<7>
  {
    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> > 0);
  }
}

void send(to, from, count:=8)
  register short *to, *from;
  register int count;
{
  assert(count<8> > 0);<True>
  predicate(0 == (count % 8)<0>)<True>
  register n<1> = (count<8> + 7) / 8;
  switch(count<8> % 8)<0>
  {
    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> > 0);
  }
}

void send(to, from, count:=9)
  register short *to, *from;
  register int count;
{
  assert(count<9> > 0);<True>
  predicate(0 == (count % 8)<1>)<False>
  register n<2> = (count<9> + 7) / 8;
  switch(count<9> % 8)<1>
  {
    case 1:      *to = *from++;
               } while (--n<1> > 0);
    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> > 0);
  }
}

void send(to, from, count:=10)
  register short *to, *from;
  register int count;
{
  assert(count<10> > 0);<True>
  predicate(0 == (count % 8)<2>)<False>
  register n<2> = (count<10> + 7) / 8;
  switch(count<10> % 8)<2>
  {
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<1> > 0);
    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> > 0);
  }
}

void send(to, from, count:=11)
  register short *to, *from;
  register int count;
{
  assert(count<11> > 0);<True>
  predicate(0 == (count % 8)<3>)<False>
  register n<2> = (count<11> + 7) / 8;
  switch(count<11> % 8)<3>
  {
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<1> > 0);
    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> > 0);
  }
}

void send(to, from, count:=12)
  register short *to, *from;
  register int count;
{
  assert(count<12> > 0);<True>
  predicate(0 == (count % 8)<4>)<False>
  register n<2> = (count<12> + 7) / 8;
  switch(count<12> % 8)<4>
  {
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<1> > 0);
    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> > 0);
  }
}

void send(to, from, count:=13)
  register short *to, *from;
  register int count;
{
  assert(count<13> > 0);<True>
  predicate(0 == (count % 8)<5>)<False>
  register n<2> = (count<13> + 7) / 8;
  switch(count<13> % 8)<5>
  {
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n<1> > 0);
    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> > 0);
  }
}

void send(to, from, count:=14)
  register short *to, *from;
  register int count;
{
  assert(count<14> > 0);<True>
  predicate(0 == (count % 8)<6>)<False>
  register n<2> = (count<14> + 7) / 8;
  switch(count<14> % 8)<6>
  {
    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<1> > 0);
    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> > 0);
  }
}

void send(to, from, count:=15)
  register short *to, *from;
  register int count;
{
  assert(count<15> > 0);<True>
  predicate(0 == (count % 8)<7>)<False>
  register n<2> = (count<15> + 7) / 8;
  switch(count<15> % 8)<7>
  {
    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<1> > 0);
    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> > 0);
  }
}

void send(to, from, count:=16)
  register short *to, *from;
  register int count;
{
  assert(count<16> > 0);<True>
  predicate(0 == (count % 8)<0>)<True>
  register n<2> = (count<16> + 7) / 8;
  switch(count<16> % 8)<0>
  {
    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<1> > 0);
    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> > 0);
  }
}

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)

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)