C duff's device

C Duff's device is a loop unrolling technique that combines a switch statement inside a while loop, allowing the loop condition and case labels to interact. It eliminates loop overhead by processing multiple iterations per loop cycle, originally invented for fast memory copying.

Use Duff's device when loop overhead matters and you need to process arrays in bulk without conditional branching.

This example demonstrates Duff's device for efficient array copying.

// compile: gcc -O2 -o duffs duffs.c
// run: ./duffs
// description: loop unrolling with Duff's device
 
#include <stdio.h>
#include <string.h>
#include <time.h>
 
// Naive loop: one element per iteration
void copy_simple(int *dst, const int *src, int n) {
    for (int i = 0; i < n; i++) {
        dst[i] = src[i];
    }
}
 
// Duff's device: 8 elements per loop cycle
void copy_duffs(int *dst, const int *src, int n) {
    int count = (n + 7) / 8;  // round up to nearest multiple of 8
 
    switch (n % 8) {
    case 0: do {
        *dst++ = *src++;
    case 7: *dst++ = *src++;
    case 6: *dst++ = *src++;
    case 5: *dst++ = *src++;
    case 4: *dst++ = *src++;
    case 3: *dst++ = *src++;
    case 2: *dst++ = *src++;
    case 1: *dst++ = *src++;
            } while (--count > 0);
    }
}
 
int main() {
    int src[1000], dst[1000];
 
    // Initialize source
    for (int i = 0; i < 1000; i++) {
        src[i] = i;
    }
 
    // Test correctness
    copy_duffs(dst, src, 1000);
    printf("Copy successful: dst[500] = %d\n", dst[500]);
 
    // Benchmark (simple version)
    clock_t start = clock();
    for (int iter = 0; iter < 1000; iter++) {
        copy_simple(dst, src, 1000);
    }
    clock_t simple_time = clock() - start;
 
    // Benchmark (Duff's device)
    start = clock();
    for (int iter = 0; iter < 1000; iter++) {
        copy_duffs(dst, src, 1000);
    }
    clock_t duffs_time = clock() - start;
 
    printf("Simple: %ld cycles\n", simple_time);
    printf("Duffs:  %ld cycles\n", duffs_time);
    printf("Speedup: %.2fx\n", (double)simple_time / duffs_time);
 
    return 0;
}

Loop unrolling principle:

• Process multiple iterations per loop cycle
• Reduces branch misprediction and loop overhead
• Modern compilers often do this automatically with -O2 or -O3

Why Duff's device is confusing:

• switch inside do-while is unusual
• switch case labels are jumped to on first iteration
• Subsequent iterations fall through all cases
• Requires careful handling of non-multiple-of-8 counts

Modern alternatives:

• Compiler loop unrolling (usually better)
• SIMD intrinsics (vectorization)
• Manual unrolling (clearer than Duff's device)
• Memcpy for copying (optimized by compiler)

Practical uses (rare today):

• Very tight inner loops where every cycle matters
• When compiler can't unroll effectively
• Embedded systems with limited optimization
• Graphics/game engines with custom memory operations

Correctness caveats:

• Off-by-one errors are easy
• count = (n + 7) / 8 for rounding up
• Test thoroughly with various sizes
• Edge cases: n=0, n=1, n=7, n=8, n=9

Performance notes:

• Modern CPUs have branch prediction and pipelining
• Duff's device may not be faster than simple loop with -O3
• Compiler optimization often beats manual unrolling
• Only worth it if profiling shows loop overhead is a bottleneck

Readability trade-off:

• Duff's device is infamous for being hard to understand
• Clear, commented code is usually preferred
• Use only if performance is critical and proven
• Consider inline assembly or compiler hints instead