Duffs Device In Duffs Own Words

This is the text of a document by TomDuff describing DuffsDevice, which he sent to comp.lang.c in 1988 when DuffsDevice came up. This version was taken from http://groups-beta.google.com/group/comp.lang.c/msg/bb78298175c42411, with the formatting intact, except where Wiki's TextFormattingRules interfered (WikiWords, italics, etc).

The original netnews version (from 1984) Tom refers to and reconstructed can be found at http://groups.google.com/groups?selm=2748%40alice.UUCP, and Tom presumably knows this.

 From: td@alice.UUCP (Tom Duff)
 Newsgroups: comp.lang.c
 Subject: Re: Explanation, please!
 Summary: Original citation
 Message-ID: <8144@alice.UUCP>
 Date: 29 Aug 88 20:33:51 GMT
 References: <638@paris.ICS.UCI.EDU> <634@proxftl.UUCP> <660@proxftl.UUCP>
 Organization: AT&T Bell Laboratories, Murray Hill NJ
 Lines: 151

 I normally do not read comp.lang.c, but Jim McKie told me
 that "Duff's device" had come up in comp.lang.c again.  I
 have lost the version that was sent to netnews in May 1984,
 but I have reproduced below the note in which I originally
 proposed the device.  (If anybody has a copy of the netnews
 version, I would gratefully receive a copy at research!td or
 td@research.att.com.)

 To clear up a few points:
 1)      The point of the device is to express general
         loop unrolling directly in C.  People who have
         posted saying `just use memcpy' have missed the
         point, as have those who have criticized it using
         various machine-dependent memcpy implementations
         as support.  In fact, the example in the message is
         not implementable as memcpy, nor is any computer
         likely to have an memcpy-like idiom that implements
         it.

 2)      Somebody claimed that while the device was named
         for me, I probably didn't invent it.  I almost
         certainly did invent it.  I had definitely not
         seen or heard of it when I came upon it, and nobody
         has ever even claimed prior knowledge, let alone
         provided dates and times.  Note the headers on the
         message below:  apparently I invented the device
         on November 9, 1983, and was proud (or disgusted)
         enough to send mail to dmr.  Please note that I
         do not claim to have invented loop unrolling, merely
         this particular expression of it in C.

 3)      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.

 4)      Somebody invoked (or more properly, banished) the
         'false god of efficiency.'  Careful reading of my
         original note will put this slur to rest.  The
         alternative to genuflecting before the god of
         code-bumming is finding a better algorithm.  It
         should be clear that none such was available.  If
         your code is too slow, you must make it faster.  If no
         better algorithm is available, you must trim cycles.

 5)      The same person claimed that 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.

 6)      Even Henry Spencer, who hit every other nail square on
         the end with the flat round thing stuck to it, made a
         mistake (albeit a trivial one).  Here is Henry replying
         to bill@proxftl.UUCP (T. William Wells):
         >>... Dollars to doughnuts this code
         >>was written on a RISC machine.

         >Nope.  Bell Labs Research uses VAXen and 68Ks, mostly.

         I was at Lucasfilm when I invented the device.

 7)      Transformations like this can only be justified by measuring the
         resulting code.  Be careful when you use this thing that you don't
         unwind the loop so much that you overflow your machine's instruction
         cache.  Don't try to be smarter than an over-clever C compiler that
         recognizes loops that implement block move or block clear and compiles
         them into machine idioms.

 Here then, is the original document describing Duff's device:

 From research!ucbvax!dagobah!td  Sun Nov 13 07:35:46 1983
 Received: by ucbvax.ARPA (4.16/4.13)
         id AA18997; Sun, 13 Nov 83 07:35:46 pst
 Received: by dagobah.LFL (4.6/4.6b)
         id AA01034; Thu, 10 Nov 83 17:57:56 PST
 Date: Thu, 10 Nov 83 17:57:56 PST
 From: ucbvax!dagobah!td (Tom Duff)
 Message-Id: <8311110157.AA01034@dagobah.LFL>
 To: ucbvax!decvax!hcr!rrg, ucbvax!ihnp4!hcr!rrg, ucbvax!research!dmr,
         ucbvax!research!rob

 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:

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

 (Obviously, this fails if the count is zero.)
 The VAX C compiler compiles the loop into 2 instructions (a movw and
 a sobleq, I think.)  As it turns out, this loop was the bottleneck in
 a real-time animation playback program which ran too slowly by about 50%.
 The standard way to get more speed out of something like this is to unwind
 the loop a few times, decreasing the number of sobleqs.  When you do that,
 you wind up with a leftover partial loop.  I usually handle this in C with
 a switch that indexes a list of copies of the original loop body.  Of
 course, if I were writing assembly language code, I'd just jump into the
 middle of the unwound loop to deal with the leftovers.  Thinking about this
 yesterday, the following implementation occurred to me:

         send(to, from, count)
         register short *to, *from;
         register count;
         {
                 register 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);
                 }
         }

 Disgusting, no?  But it compiles and runs just fine.  I feel a combination
 of pride and revulsion at this discovery.  If no one's thought of it before,
 I think I'll name it after myself.

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

 Many people (even bwk?) have said that the worst feature of C is that
 switches don't break automatically before each case label.  This code forms
 some sort of argument in that debate, but I'm not sure whether it's for or
 against.

                         yrs trly
                         Tom