Duff’s Device解析：C/C++循环展开优化技术 #

引言 #

Duff’s Device是一种独特的循环展开优化技术，由Tom Duff在1983年发明。本文将深入探讨这种技术的工作原理，以及如何在实际开发中应用它来提升程序性能。

本文主要介绍 Duff’s device 这个知识点，这是一种 C 语言中使用的优化技术，主要用于加速循环展开和减少循环条件判断的开销。它是由 Tom Duff 在 1983 年发明的，最初用作优化图形处理代码。

直接看一段伪代码，常规的我们循环展开的代码就像这样，step 为 1，在 while 循环中逐个判断条件，如果 count 为 80，那就需要循环 80 次条件判断。

send(to, from, count)
register short *to, *from;
register count;
{
    do {                          /* count > 0 assumed */
        *to = *from++;
    } while (--count > 0);
}

之前我在其它文章中有介绍过，条件判断是有开销的，条件判断次数越多，开销肯定越大。

有没有办法减少循环判断条件的次数？如果计数总是可以被 8 整除，可以考虑将这个循环展开 8 倍：

send(to, from, count)
register short *to, *from;
register count;
{
    register n = count / 8;
    do {
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
    } while (--n > 0);
}

这样其实就可以将条件判断的开销降低 8 倍。

上面虽然可以将开销降低 8 倍，但是有个前提条件，循环的次数一定要可以被 8 整除，但实际使用时，可不能保证循环次数一定是 8 的整数倍，这样的代码使用起来太受限了，如何解决呢？

Duff 意识到，为了处理计数不能被 8 整除的情况，可以通过交错使用 switch 语句和循环的结构来实现汇编程序员跳入循环体的技术，将 switch 的 case 标签放在循环体中对应于 count/8 余数的位置：

send(to, from, count)
register short *to, *from;
register count;
{
    register n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    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++;
            } while (--n > 0);
    }
}

Duff’s Device 同样可以应用于任何其他大小的展开循环，不仅仅是上面示例中的 8 的倍数，你也可以改成其他数字。

循环展开的基本思想是通过减少循环条件判断的次数来减少循环中执行的指令数量，有时可以减少在循环中花费的时间。

例如，对于一个代码块中只有一条指令的循环，通常每次执行指令时都会进行循环条件判断。如果在循环中放置 8 个相同指令，那么条件判断将每 8 次迭代执行一次，这可能通过避免 7 次条件判断来节省时间。然而，这只能处理 8 的倍数次迭代，需要其他方法来处理剩余的迭代次数。

Duff’s Device 提供了一种解决方案，首先执行剩余的迭代次数，然后根据需要迭代 8 个相似指令的倍数次。为了确定剩余的迭代次数，代码首先计算总迭代次数对 8 取模。根据这个余数，程序执行将跳转到一个 case 语句，该语句后面跟着正好需要的迭代次数。一旦完成，接下来的操作就很简单了：代码继续执行 8 个指令一组的迭代。

你可能会问，减少了 while 循环条件的判断，但是增加了 switch 判断的次数，这不也会增加开销吗，其实不会，因为编译器会对这种连续数字或者间隔很小数字的 switch 做优化，会自动去掉条件判断的指令。

具体可以看我之前分享过的文章，分支预测