【赤石C++】详解达夫设备

达夫设备

达夫设备（Duff’s device）是 C/C++ 语言中一种串行复制的优化技术，巧妙地利用了 switch 语句的穿透（fallthrough）特性

在早期计算机系统中，编译器优化能力弱，无法自动展开循环，且 CPU 流水线简单，几乎不存在分支预测。因此手动减少分支跳转次数能显著提升性能

考虑一个最简单的 memcpy 函数：

void mymemcpy(const uint8_t* src, uint8_t* dst, size_t size) noexcept {
    for (size_t i = 0; i < size; ++i) {
        dst[i] = src[i];
    }
}

每次循环都要执行：

1. 判断条件（i < size） -> 一次比较
2. 条件跳转（如果为 true，跳回循环体开头，否则跳出） -> 一次分支
3. 更新计数器（++i）

所以，总共需要 N 次分支跳转（即 N 次条件判断 + 跳转）

达夫设备以 8 次操作为一组展开循环。其原理是：

• 初始时，利用 switch 直接跳到对应位置处理余数
• 后续全部通过 do-while 循环批量处理完整的一组（8 次）
• 每 8 次操作才做一次循环条件判断和跳转

void mymemcpy_duff(const uint8_t* src, uint8_t* dst, size_t size) noexcept {
    size_t n = (size + 7) / 8;
    switch (size % 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 (--n > 0);
    }
}

考虑 size = 100 的情况，100 除 8 等于 12 余 4，所以达夫设备需要进行 13 次循环，12 次完整处理 8 字节，1 次处理余下的 4 字节

• 计算循环次数：n = (100 + 7) / 8 = 13
• 处理 4 字节余数：size % 8 = 4，进入case 4分支，同时也进入do-while循环

case 4: *dst++ = *src++;
case 3: *dst++ = *src++;
case 2: *dst++ = *src++;
case 1: *dst++ = *src++;

• 4次复制执行完成后，执行while (--n > 0)，n从13减到12，并进行条件判断
• n > 0的判断成立，do-while跳回循环体开头，执行 8 次完整复制

case 0: *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++;

• 8 次完整复制执行完后，更新计数器，进行判断，跳回循环体开头，依次往复，直到计数器归 0

完整复制 100 字节，普通的 memcpy 需要 100 次分支跳转，而达夫设备仅需要 13 次

题外话

在特定语境下，device有手段/技巧的意思（比如literary device翻译为文学手法而不是文学设备） ，所以Duff's Device更信达雅的翻译是达夫巧构（意为巧妙编程技巧）

参考

https://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87

往期赤石 C++ 系列

<此处插入公众号超链接>