Duff's Device

computer_science compsci design_pattern optimisation technique

Partial loop unrolling with switch and do while

A Duff's Device is a technique in languages that have switch statements with case fallthrough and do-while loops that can jumped into without hitting the do statement, such as C. The technique involves partial manual loop unrolling such that there are $K$ copies of the business logic within the do-while loop that executes the business logic $K$ times per iteration and performs $\lfloor\frac{N}{K}\rfloor$ total iterations, where $N$ is the desired total number of executions. If $N$ is always guaranteed to be an integer multiple of $K$ then nothing else is needed. However, for instances where $N$ can be any number then a switch statement, embedded into the do-while loop is needed to jump in and perform the first $N\bmod{K}$ executions.

Example

The C code:

#include <stdio.h>

int main()
{
    int count = 12;

    // Duff's device
    {
        int result = 0;
        int loop = (count + 7) / 8;
        int subloop = count % 8;
        printf("   C:%d L:%d S:%d R:%d\n", count, loop, subloop, result);
        switch(subloop)
        {
            case 0: do {    printf("0: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
            case 7:         printf("7: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
            case 6:         printf("6: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
            case 5:         printf("5: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
            case 4:         printf("4: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
            case 3:         printf("3: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
            case 2:         printf("2: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
            case 1:         printf("1: C:%d L:%d S:%d R:%d\n", count, loop, subloop, ++result);
                        } while (--loop > 0);
        }
        printf("   C:%d L:%d S:%d R:%d\n", count, loop, subloop, result);
    }

    return 0;
}

Outputs:

   C:12 L:2 S:4 R:0
4: C:12 L:2 S:4 R:1
3: C:12 L:2 S:4 R:2
2: C:12 L:2 S:4 R:3
1: C:12 L:2 S:4 R:4
0: C:12 L:1 S:4 R:5
7: C:12 L:1 S:4 R:6
6: C:12 L:1 S:4 R:7
5: C:12 L:1 S:4 R:8
4: C:12 L:1 S:4 R:9
3: C:12 L:1 S:4 R:10
2: C:12 L:1 S:4 R:11
1: C:12 L:1 S:4 R:12
   C:12 L:0 S:4 R:12

Duff's Device

Example

Tacitus