|
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. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In computing, optimization is the process of modifying a system to make some aspect of it work more efficiently or use fewer resources. ...
Look up Implementation in Wiktionary, the free dictionary. ...
See the terminology section, below, regarding inconsistent use of the terms assembly and assembler. ...
In computer programming and compiler optimization terminology, loop unwinding, also known as loop unrolling, is a technique for optimizing parts of computer programs — a member of the loop transformation family. ...
Thomas Douglas Selkirk Duff (b. ...
Year 1983 (MCMLXXXIII) was a common year starting on Saturday (link displays the 1983 Gregorian calendar). ...
Lucasfilm Ltd. ...
C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...
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. Memory-mapped I/O (MMIO) and port I/O (also called port-mapped I/O or PMIO) are two complementary methods of performing input/output between the CPU and I/O devices in a computer. ...
In computer programming, a variable or object declared with the volatile keyword may be modified externally from the declaring object. ...
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.
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); } } 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. Its behavior is undefined if it is entered with count having the value zero. See the terminology section, below, regarding inconsistent use of the terms assembly and assembler. ...
The C Programming Language, Brian Kernighan and Dennis Ritchie, one of the most read and trusted books on C. The C Programming Language (also known as K&R or the white book) is a famous computer science book which has been influential in the application and development of the C...
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 unrolling, 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). In computer programming and compiler optimization terminology, loop unwinding, also known as loop unrolling, is a technique for optimizing parts of computer programs — a member of the loop transformation family. ...
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. In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an object, normally by running a number of standard tests and trials against it. ...
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, it is not particularly useful in this form since the standard C library already supplies a memory-copying function which is likely to be even more optimized. Bjarne Stroustrup Bjarne Stroustrup (IPA: ) (born December 30, 1950 in Aarhus, Denmark) is a computer scientist and the College of Engineering Chair Professor of Computer Science at Texas A&M University. ...
Books Bjarne Stroustrup Bjarne Stroustrup (IPA: ) (born December 30, 1950 in Aarhus, Denmark) is a computer scientist and the College of Engineering Chair Professor of Computer Science at Texas A&M University. ...
Brian Wilson Kernighan (IPA pronunciation: , the g is silent), (born 1942 in Toronto, Ontario, Canada) is a computer scientist who worked at Bell Labs alongside Unix creators Ken Thompson and Dennis Ritchie and contributed greatly to Unix and its school of thought. ...
Dennis Ritchie Dennis MacAlistair Ritchie (born September 9, 1941) is a computer scientist notable for his influence on ALTRAN, B, BCPL, C, Multics, and Unix. ...
The C Programming Language, second edition, by Brian Kernighan and Dennis Ritchie, widely regarded to be the authoritative reference on C. The C Programming Language (sometimes referred to as K&R) is a well-known computer science book written by Brian Kernighan and Dennis Ritchie, the latter of whom originally...
External links - Description and original mail by Duff at Lysator
- Article at FOLDOC
- Article at the Jargon File
- Article at CodeMaestro
- Google copy of original USENET post
- Simon Tatham's coroutines in C utilizes the same switch/case trick
- Adam Dunkels' protothreads also uses nested switch/case statements
|
Feeds |
Contact