Duff's device
In the C programming language, Duff's device is a way of manually implementing loop unrolling by interleaving two syntactic constructs of C: the - loop and a switch statement. Its discovery is credited to Tom Duff in November 1983, when Duff was working for Lucasfilm and used it to speed up a real-time animation program. Loop unrolling attempts to reduce the overhead of conditional branching needed to check whether a loop is done, by executing a batch of loop bodies per iteration. To handle cases where the number of iterations is not divisible by the unrolled -loop increments, a common technique among assembly language programmers is to jump directly into the middle of the unrolled loop body to handle the remainder. Duff implemented this technique in C by using C's case label fall-through feature to jump into the unrolled body. Original version. 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. His original code, in C, looked as follows: send(to, from, count) register short *to, *from; register count; This code assumes that initial  . The pointer is not incremented as would be required for a memory-to-memory copy. If were always divisible by eight, unrolling this loop eight-fold would produce the following: send(to, from, count) register short *to, *from; register count; Duff realized that to handle cases where is not divisible by eight, the assembly programmer's technique of jumping into the loop body could be implemented by interlacing the structures of a switch statement and a loop, putting the switch's labels at the points of the loop body that correspond to the remainder of : send(to, from, count) register short *to , *from; register count; Duff's device can similarly be applied with any other size for the unrolled loop, not just eight as in the example above. Mechanism. 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 C by virtue of two attributes in C: This leads to what the "Jargon File" calls "the most dramatic use yet seen of fall through in C". C's default fall-through in case statements has  long been one of its most controversial features; Duff himself said that "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against." Although valid in C, Duff's device goes against common C guidelines, such as the MISRA guidelines. Some compilers (e.g. CompCert) are restricted to such guidelines and thus might reject Duff's device. Simplified explanation. The basic idea of loop unrolling is that the number of instructions executed in a loop can be reduced by reducing the number of loop tests, sometimes reducing the amount of time  spent in the loop. For example, in the case of a loop with only a single instruction in the block code, the loop test will typically be performed for every iteration of the loop, that is every time the instruction is executed. If, instead, eight copies of the same instruction are placed in the loop, then the test will be performed only every eight iterations, and this may gain time by avoiding seven tests. However, this only handles a multiple of eight iterations, requiring something else to handle any remainder of iterations. Duff's device provides a solution by first  performing the remainder of iterations, followed by iterating as many times as necessary the multiple of eight similar instructions. To determine the number of remainder iterations, the code first calculates the total number of iterations modulo eight. According to this remainder, the program execution will then "jump" to a codice_1 statement followed by "exactly the number of iterations needed". Once this is done, everything is straightforward the code continues by doing iterations of groups of eight instructions, this has become possible since the remaining number of iterations is a multiple of eight. Duff's device provides a compact loop unrolling  by using the case keyword "both inside and outside the loop". This is unusual because the contents of a case statement are traditionally thought of as a block of code nested inside the case statement, and a reader would typically expect it to end before the next case statement. According to the specifications of C language, this is not necessary; indeed, case statements can appear anywhere inside the switch code block, and at any depth; the program execution will simply jump to the next statement, wherever it may be. Performance. Many compilers will optimize the switch into a branch table  just as would be done in an assembly implementation. The primary increase in speed versus a simple, straightforward loop, comes from loop unwinding that reduces the number of performed branches, which are computationally expensive due to the need to flushand hence stallthe instruction pipeline. The codice_2 statement is used to handle the remainder of the data not evenly divisible by the number of operations unrolled (in this example, eight short moves are unrolled, so the codice_2 handles an extra 1–7 shorts 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; it may also interfere with pipelining and branch prediction on some architectures. When numerous instances of Duff's device were removed from the XFree86 Server in version 4.0, there was an improvement in performance and a noticeable reduction in size of the executable.<ref name="lkml-0008.2/0171"></ref> Therefore, when considering this code as a program optimization, 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, as well as weighing the risk that the optimized code will later be used on different platforms where it is not the fastest code. For the purpose of memory-to-memory copies (which, as mentioned above, was not the original use of Duff's device), the standard C library provides the function codice_4; it will not perform worse than a memory-to-memory copy version of this code, and may contain architecture-specific optimizations that  make it significantly faster.