Duff

Duff

[duhf]
Green, Duff, 1791-1875, American journalist and politician, b. Woodford co., Ky. After service in the War of 1812, he settled in Missouri, where he became (1824) editor of the St. Louis Enquirer. He moved (1825) to Washington, D.C., purchased the United States Telegraph, and backed Andrew Jackson for President. After Jackson was elected (1828), Green's newspaper became the administration journal and Green was admitted to Jackson's Kitchen Cabinet. He backed John C. Calhoun against Jackson in the nullification controversy, however, and thereafter he increasingly defended the South on the issues of slavery and the tariff. He left (1836) the Telegraph, and—having staunchly supported the Harrison-Tyler ticket in 1840—served Tyler on diplomatic missions to England (1843) and to Texas and Mexico (1844-45). He started (1844) in New York City the Republic, a newspaper devoted to tariff reduction and sympathetic toward the South. He became increasingly involved in Southern industrial development and railroad building. He had secured charters and funds for a Southern Pacific railroad and was about to start construction when the Civil War began. During the war he operated various ironworks for the Confederacy.
Duff, Alexander, 1806-78, Scottish missionary in India. In Calcutta (now Kolkata) he opened (1830) a mission college which became an important center of education in India; both religious and scientific subjects were taught. Duff was also instrumental in founding the Univ. of Calcutta. In 1844 he helped to launch the Calcutta Review.
Duff, Sir Lyman Poore, 1865-1955, Canadian jurist, b. Ontario. A lawyer and judge in British Columbia, he was appointed a judge of the Supreme Court of Canada in 1906, and in 1933 he became chief justice, serving until his retirement in 1944. He was chairman (1931-32) of the Royal Commission on Transportation (popularly called the Duff Commission) appointed to inquire into railroad problems in Canada, and twice (1931, 1943) he was administrator of the government of Canada. He was knighted in 1934.
In computer science, Duff's device is an optimized implementation of a serial copy that uses a technique widely applied in assembly language for loop unwinding. Its discovery is credited to Tom Duff in November of 1983, who at the time was working for Lucasfilm. It is perhaps the most dramatic use of case label fall-through in the C programming language to date. Note that Duff does not claim credit for discovering the concept of loop unrolling, just this particular expression of it in C.

Original version

Traditionally, a serial copy would look like:

do { /* count > 0 assumed */

   *to = *from++;            /* Note that the to pointer is NOT incremented */
} while (--count > 0);

Note that to is not incremented because Duff was copying to a single memory-mapped output register. In modern C this would be communicated by the use of the volatile keyword as a qualifier in the declaration of the pointer to.

While optimizing this, Duff realized that an unrolled version of his loop could be implemented by interlacing the structures of a switch and a loop.

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

Based on an algorithm used widely by programmers coding in assembly for minimizing the number of tests and branches during a copy, Duff's device appears out of place when implemented in C. The device is valid, legal C by virtue of the relaxed specification of the switch statement in the language's definition. At the time of the device's invention this was the first edition of The C Programming Language which requires only that the controlled statement of the switch be a syntactically valid (compound) statement within which case labels can appear prefixing any sub-statement. In conjunction with the fact that, in the absence of a break statement, the flow of control will fall-through from a statement controlled by one case label to that controlled by the next, this means that the code specifies a succession of count copies from sequential source addresses to the memory-mapped output port. Note that, as documented in the comment, the code assumes that count is strictly positive.

Many compilers will optimize the switch into a jump table just as would be done in an assembler implementation. C's default fall-through in case statements has long been its most controversial single feature; Duff observed that "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against.

The primary increase in speed versus a simple, straightforward loop comes from loop unwinding, which reduces the number of comparisons performed during a loop. The switch/case statement is used to handle the remainder of the data not evenly divisible by the number of operations unrolled (in this example, 8 byte moves are unrolled, so the switch/case handles an extra 1–7 bytes automatically).

This automatic handling of the remainder may not be the best solution on all systems and compilers — in some cases two loops may actually be faster (one loop, unrolled, to do the main copy, and a second loop to handle the remainder). The problem appears to come down to the ability of the compiler to correctly optimize the device, although at least one person has suggested that it may also interfere with pipelining and branch prediction on some architectures. Therefore, when considering using this code, it may be worth running a few benchmarks to verify that it actually is the fastest code on the target architecture, at the target optimization level, with the target compiler.


Here is an example that may prove more useful as an illustration (and fixes the count == 0 bug in the above code):

/*

   duff.c
*/

  1. include
  2. include

void dsend(int count);

int main(int argc, char *argv[]) {

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

void dsend(int count) {

   int n;
   if (!count) return;
   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); } }

Just save it as 'duff.c' and type 'cc duff.c' (on a Unix-like operating system). You should specify the count as a command-line argument for the device to be invoked.

Stroustrup's version

The original Device was made for copying to a register. To actually copy memory from one location to another, you must add an auto-increment to every reference to to, like so:

 *to++ = *from++;

This modified form of the Device appears as a "what does this code do?" exercise in Bjarne Stroustrup's book The C++ Programming Language, presumably because novice programmers cannot be expected to know about memory-mapped output registers. However, the standard C library provides the function memcpy for this purpose; it will not perform worse than this code, and may contain architecture specific optimisations that will make it significantly faster.

Books

References

External links

Search another word or see duffon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature