Read the original article here.

---

The Forbidden Code: Unleashing Duff's Device - The Art of C's Unconventional Control Flow

In the realm of programming, especially low-level languages like C, performance is paramount. Sometimes, achieving maximum speed requires techniques that bend or even appear to break the conventional rules taught in introductory classes. These are the "underground" methods, often elegant in their cleverness but potentially dangerous if misunderstood. Duff's Device is a prime example – a bizarre-looking construct that masterfully exploits C's defined behavior to squeeze out extra performance.

Discovered by Tom Duff in 1983 while working on real-time animation at Lucasfilm, Duff's Device is a classic hack born out of necessity. It's a legendary piece of code that combines two seemingly unrelated C constructs – the do-while loop and the switch statement – in a way that initially looks nonsensical, but is perfectly valid according to the C standard.

The Problem: Loop Overhead and the Remainder

At the heart of many performance-critical tasks lies iteration – repeating an operation many times. Simple loops, while easy to write, introduce overhead:

Loop Overhead: The computational cost associated with managing a loop, including checking the loop condition, incrementing/decrementing counters, and jumping back to the loop's beginning.

For very small loop bodies, this overhead can become a significant portion of the total execution time. Imagine a loop that just copies one piece of data per iteration. Checking the loop condition might take as much time as the copy itself!

Optimizing Loops: Loop Unrolling

A common technique to reduce loop overhead is loop unrolling:

Loop Unrolling: A compiler optimization or manual coding technique where the body of a loop is replicated multiple times to reduce the number of loop iterations and the associated loop overhead (tests and branches).

Instead of copying one item per iteration and checking the condition N times, you might copy 8 items per iteration and check the condition only N/8 times. This significantly reduces the number of costly branch operations required.

The Remainder Problem

Loop unrolling works beautifully when the total number of iterations is perfectly divisible by the unroll factor (e.g., 8 in our example). But what happens if you need to copy 25 items, and you've unrolled the loop 8 times? You can do 3 full iterations (3 * 8 = 24 items), but you're left with 1 item remaining. You can't just run another full unrolled block of 8.

Traditional solutions for this remainder include:

1. A separate, simple loop to handle the remaining iterations before or after the main unrolled loop.
2. Calculating the remainder and using a sequence of individual operations to handle the first few items before entering the unrolled loop, or the last few items after the unrolled loop.

Assembly language programmers often used a more direct approach for the remainder: jumping directly into the middle of the unrolled code block. The Duff's Device brings this assembly-level technique to C.

The "Forbidden" Technique: Introducing Duff's Device

Duff's specific problem was copying 16-bit integers (often short in C) from an array (from) to a memory-mapped output register (to). A memory-mapped register is a hardware location accessed as if it were memory, often used for direct control of devices. Critically, the destination address (to) did not increment; the data was always sent to the same hardware address. The source address (from) did increment.

A simple loop for this might look conceptually like:

while (count > 0) {
    *to = *from++; // Copy one item and advance source pointer
    count--;       // Decrement counter
}

(Note: The original problem had from pointing to an array and to to a register, so *to = *from++; is the core operation)

An 8-times unrolled loop (if count is a multiple of 8):

while (count > 0) {
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    count -= 8;
}

Duff's stroke of genius (or madness, depending on your perspective) was to combine the do-while loop and switch statement to handle the remainder seamlessly before the main unrolled loop body using C's case label fall-through.

The Structure and Mechanism

Here's the conceptual structure of Duff's Device as described:

// Assuming 'count' is the total number of items to copy
// 'from' is the source pointer (gets incremented)
// 'to' is the destination pointer (memory-mapped register, does NOT get incremented in this original case)

switch (count % 8) { // Calculate remainder (0 to 7)
    case 0: do { // Start of the do-while loop
    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++;
                 count -= 8; // Decrement count by the block size
            } while (count > 0); // Loop condition
}

Let's break down how this works, step by step:

1. Initial Remainder Handling: The switch (count % 8) is evaluated only once at the beginning.
2. Jumping In: Based on the remainder, execution jumps to the corresponding case label inside the do-while loop.
   • If count % 8 is 3, execution jumps to case 3:.
   • If count % 8 is 0, execution jumps to case 0:.
3. Fall-Through Executes the Remainder: C's switch statement has a controversial feature: fall-through.

   Case Fall-Through: In a C/C++ switch statement, if a case block does not end with a break, return, or goto statement, execution will continue sequentially into the next case block and subsequent statements. Since there are no break statements between the case labels within the do-while body, execution proceeds sequentially from the jumped-to case label downwards. If the jump was to case 3, the code will execute the statement at case 3:, then case 2:, then case 1:. This executes exactly the number of statements corresponding to the remainder (3 statements).

4. Entering the Main Loop: After executing the statements for the remainder, execution hits the closing brace } of the do-while loop.
5. Loop Condition Check: The while (count > 0) condition is checked.
6. Back to the Top (of the loop): If count > 0, execution jumps back to the beginning of the do-while block (just before case 7: in this structure).
7. Executing Full Blocks: Now, since execution starts from the top of the loop body, it falls through all 8 case labels sequentially (case 7: through case 1:), executing all 8 copy operations. This is the unrolled part.
8. Repeat: The process from step 4 repeats, executing full blocks of 8 copies, until count is no longer greater than 0 after decrementing.

This clever arrangement uses the switch to perform an initial, calculated jump into the loop body to handle the remainder, and then relies on the do-while structure and fall-through to repeatedly execute the full unrolled block. The case 0: label acts as the entry point for the main unrolled loop execution after the remainder (or if the original count was a multiple of 8).

Key Points:

• The switch is evaluated only once.
• The do-while loop structure is paramount. The count -= 8 decrements by the block size, not 1.
• The case labels are unusual in that they appear inside the loop body, defining specific entry points within the unrolled code block.
• Fall-through is essential for executing the correct number of initial "remainder" statements.

This technique can be applied with any unroll factor, not just 8. The count % N determines the initial jump, and the loop body contains N case labels and statements.

The Mechanism: Why It's Valid (And Controversial)

Duff's Device is perfectly valid C due to specific rules in the C standard, particularly concerning the switch statement:

1. Relaxed switch Body Definition: The C standard (dating back to the first edition of The C Programming Language) allows the body of a switch to be any syntactically valid statement (often a compound statement {}). case labels can prefix any substatement within that block, not just statements at the top level. The placement of case labels inside a do-while loop body, which itself is the single statement forming the switch body, is permitted.
2. case Fall-Through: As discussed, the default behavior of falling through from one case to the next in the absence of break is a fundamental (and often debated) feature of C switch statements.
3. Ability to Jump into Loops: C's goto statement and the flow control of switch/case do allow execution to jump into the middle of a structured statement like a loop body (though typically not past variable initializations, which isn't an issue here as variables are declared outside).

The Jargon File, a glossary of hacker slang, famously describes this as "the most dramatic use yet seen of fall through in C."

While valid, Duff's Device often runs afoul of modern coding standards and style guides, such as MISRA C:

MISRA C: A set of software development guidelines for the C programming language used in critical systems (like automotive, aerospace, industrial control) to improve safety, security, and reliability. MISRA guidelines often restrict or forbid unconventional language features like unchecked goto or complex uses of switch fall-through.

Some compilers, particularly those designed for high-assurance systems adhering to strict standards like MISRA (e.g., CompCert), may reject code like Duff's Device unless specifically configured to allow such constructs. This is why it feels like "forbidden code" – it works, but often requires stepping outside recommended best practices for clarity, maintainability, and formal verification.

Performance: Is It Always Faster?

The theoretical performance gain from Duff's Device comes from reducing loop overhead by:

• Fewer Branches: The number of times the loop condition is checked and a jump back to the top occurs is reduced by a factor of the unroll amount. Branches can be computationally expensive, especially on modern pipelined processors, as mispredicted branches can cause the instruction pipeline to be flushed, wasting cycles.
• Compiler Optimization: Compilers can often optimize the switch statement into a branch table:

  Branch Table: A jump table or lookup table used by compilers to implement switch statements efficiently. Instead of a series of comparisons, the remainder value is used as an index into a table of addresses, allowing a direct jump to the correct case label's code. This is very fast.

However, the reality of performance optimization is complex. Duff's Device might not always be the fastest solution:

1. Compiler Effectiveness: Not all compilers are equally good at optimizing Duff's Device. Some might not generate optimal branch tables or might struggle with the unusual control flow.
2. Pipeline & Cache Interaction: On modern CPUs, complex control flow can interfere with instruction pipelining and cache efficiency in unexpected ways. The benefits of reduced branches might be offset by other factors.
3. XFree86 Example: The text mentions that when instances of Duff's Device were removed from the XFree86 graphics server (a complex, performance-sensitive codebase) in version 4.0, performance improved and the executable size decreased. This is a real-world example where the "clever" optimization proved detrimental on the target architectures and compilers.
4. Alternative Implementations: Sometimes, a simpler approach with two distinct loops (one unrolled loop for the main work, a simple loop for the remainder) can perform better, as it might be easier for the compiler to optimize and potentially avoids the complexities of jumping into the loop body.

Therefore, like any optimization, benchmarking is crucial. You must measure the performance of Duff's Device against simpler alternatives on your specific target hardware, compiler, and optimization levels to determine if it actually provides a benefit. Using it speculatively based purely on theory is risky.

For standard memory-to-memory copies (memcpy), the standard C library provides the memcpy function. This function is typically implemented in highly optimized assembly language, often using architecture-specific instructions (like SIMD) and techniques far more advanced than Duff's Device. It is almost always the fastest and safest option for such tasks. Duff's Device is more relevant when the destination isn't a simple memory address (like a memory-mapped register that doesn't increment) or when you need absolute minimal overhead and are operating in a restricted environment where memcpy isn't suitable or available.

Related Underground Techniques

Duff's Device isn't the only technique that uses unconventional control flow or compiler exploitation:

• Computed GOTO: A non-standard C extension (though supported by GCC and others) that allows jumping to an address stored in a pointer variable (goto *address_variable;). This is another way to implement jump tables or state machines, similar in spirit to how the switch in Duff's Device facilitates jumping to different points.
• Coroutines: Duff's Device's pattern of jumping into a block and then looping can be adapted to implement lightweight coroutines in C/C++ without requiring separate stacks. The switch state remembers where execution left off, and the fall-through/loop structure resumes from that point on the next "call." Simon Tatham's coroutine implementation is a famous example using a similar nested switch/case trick. Adam Dunkels' Protothreads use a related pattern for even lighter-weight concurrency.
• Jensen's Device: An older, Algol-era programming trick using "call by name" parameters to effectively pass code blocks into functions, allowing for compact ways to express mathematical series or operations on data structures. Not directly related to control flow like Duff's, but another example of clever language exploitation.
• Pigeon's Device: A less famous relative that intertwines switch/case with if/else statements, achieving different complex control flow patterns.

These techniques belong to the "forbidden" category because they prioritize cleverness and raw performance potential over typical concerns like readability, maintainability, and strict adherence to conventional programming style or guidelines. They are powerful tools in the hands of an expert who understands their mechanics and limitations but can easily lead to bugs and unmanageable code if used improperly or without deep understanding.

Conclusion: A Legacy of Cleverness

Duff's Device remains a fascinating piece of C programming lore. It stands as a testament to how a deep understanding of a language's core mechanics, even its seemingly quirky features like switch fall-through, can be leveraged for powerful optimizations.

While often supplanted by better compiler technology or standard library functions like memcpy, and frequently discouraged by modern coding standards, understanding Duff's Device provides valuable insight into:

• The nature of loop optimization and the remainder problem.
• How low-level techniques (like assembly jumps) can be translated into high-level languages.
• The specific, sometimes surprising, rules of the C language standard.
• The trade-offs between performance, readability, and maintainability in code design.

It's a prime example of the "underground" code – a technique that's complex, potentially dangerous, but undeniably clever and historically significant in the quest for maximum performance. While you might not use it in your everyday coding, knowing how it works unlocks a deeper appreciation for the clever hacks that shape programming history.