Duffs Device

There was some discussion about how exactly TomDuff should be quoted. I attempted to resolve this by copying the text from http://groups.google.com/groups?selm=2748%40alice.UUCP, preserving formatting as far as possible, so we all can read DuffsDeviceInDuffsOwnWords. I hope this to be a step towards further refactoring of this page, and DuffsDeviceDiscussion. -- AalbertTorsius

Thanks. -- Doug

My take is that we know Duff's explanation lead to a few points of confusion recently. The page would be improved if those points were clarified. This isn't to say that Duff didn't explain correctly, it's just that sometimes you really have to repeat and emphasize important points for them to be understood. Since it would be inappropriate to edit Duff's words to provide that clarification, we should provide our own explanation, and link to or quote Duff's as a historical note. That is what I tried to accomplish with revision 74. If Duff's posts are to be included, I think at a minimum they should be indented into fixed-font mode. If you want to take a crack at it, doing it a different way, I'm not opposed. In the end, as long as we end up with a readable page that conveys the message, that is all I care about. -- MS

Then I think we have an agreement in principle. How about if we have some prefatory comments at the start to help avoid misunderstandings of the topic, followed by the whole of Duff's comments (I still feel strongly about that part), in Courier or whatever stylism you think is appropriate to set it off from other contributors? And a link to the Discussion page? (Which you may have noticed I've started to refactor to remove warfare while attempting to leave points made.) -- Doug

A CeeLanguage coding procedure, a special case of unrolling a tight loop, by exploiting the fall-through of the C case statement, interlacing it with a C do...while statement. Invented by TomDuff while he was working on an animation system at LucasFilm? Ltd.

You are encouraged to read about DuffsDeviceInDuffsOwnWords.

As TomDuff states, he had a valid reason for unrolling this particular loop. In general, the RulesOfOptimization apply, and it seems that using DuffsDevice to unroll a loop can even have an adverse effect. TomDuff had tried everything else and still needed to speed up that loop, but it certainly seems as if all use of DuffsDevice found by Google are cases of premature or even false optimization (or cases of "Look at me, I'm mister Guru coder!"). Still, it is a worthwhile example, illustrating a coding metaphor and highlighting why, occasionally, you have to do stuff that breaks the rules of style and beauty.

For a lengthy discussion about misunderstandings of DuffsDevice and its applicability today see DuffsDeviceDiscussion.

[...] a brief explanation would help for those who don't know C.

Yikes. If you don't know C, then you probably should avoid the whole topic, seriously. But for what it's worth, the basic idea is that people usually think of switch/case conditionals as shorthand for a series of IF-ELSEs, so that:

  if      (a == 1) { func1(); }
  else if (a == 2) { func2(); }
  else if (a == 3) { func3(); }
  else             { func4(); }

...could be replaced with:

  switch(a) {
  case 1:   func1(); break;
  case 2:   func2(); break;
  case 3:   func3(); break;
  default:  func4(); break;
  }

...if we omit the breaks, it 'falls through', so that if a == 2, func2, func3 and func4 are carried out (funcy, isn't it?), which is of course no longer congruent with the original if-statement:

  switch(a) {
  case 1:   func1();
  case 2:   func2();
  case 3:   func3();
  default:  func4();
  }

...but it turns out that C switch is not at all a matter of syntactic sugar for the if-else construct, it actually is quite different in a number of ways. One example is that switch can only accept certain types of integer variables, not any old type that could be used with if.

There are several other interesting differences, also, but the one that DuffsDevice demonstrates is that each case is not a nested block, and does not actually correspond to the blocks following each if in the first example.

People sort of know this pretty much from the beginning, since case statements "fall through" to the next lower one if the break is left out, but until Duff wrote DuffsDevice, no one noticed just how deep the difference goes.

[Another clue is the scoping involved - I'm sure many people in addition to myself have been bitten by declaring a variable inside a case "block" and having the compiler complain. I knew at one level why this happened for a long time but it never came home to me until I encountered DuffsDevice. -- ChrisMellon?]

DuffsDevice illustrates that switch statements (or rather, the case subcomponent) is utterly not block structured, and thus that common intuition is just plain wrong. It illustrates this by interweaving a switch and a loop, in a way such that neither encloses the other, they are just interweaved, very much as they might be in assembler code, as Duff commented.

This violates one of the original tenets of structured programming, but it's one that everyone has forgotten (demonstrably -- see other pages on the wiki), so that's not why people object to it. They object to DuffsDevice precisely because it violates the intuitive notion of nested-block equivalence of switch.

The popular wisdom is that C was wrong to be designed this way, and that any coder who writes code that reveals this nature of switch/case in C is wrong. Popular wisdom, however, is also what gets certain U.S. politicians voted into office: doesn't mean it's right. -- Doug

Re the code: I essentially started out with machine code, so I tend to find the various details (and restrictions) of higher level languages rather tedious (even though I've not used machine code in ages). In the above case, various such details are combined in one example, which wasn't commented, leaving it unclear which specific details were relevant in relation to the various points made. Example question: what are the outermost braces for? I also guessed that some readers would only get the gist of exactly how the code worked, and not follow precisely what happens.

Just so people know, DuffsDevice is intended to portably replace this kind of pseudo-AssemblyLanguage snippet. The switch statement replaces the computed jump below.

        mov ax,count
        add ax,#7
        div ax,#8    ; ax: n=c/8  dx: c%8
        neg dx
        add dx,#7
        mul dx,#(width - loop)
        jmp loop+dx
 loop:  out to,[from]
        inc from
 width: out to,[from]
        inc from
        out to,[from]
        inc from
        out to,[from]
        inc from
        out to,[from]
        inc from
        out to,[from]
        inc from
        out to,[from]
        inc from
        out to,[from]
        inc from
 ; end of loop body
        dec ax
        jnz loop

Note: The width+jump calculation is hand-optimized code. It would not be used by a compiler, which would use an indirect jump over a table of labels instead.

The switch in DuffsDevice is used to jump into the loop, in much the same way as in the code above.

CategoryCee CategoryConditionalsAndDispatching