Try harder.

一种循环展开的优化方法:达夫设备(Duff device)

2019.09.01

写这篇博客的动机来源于在 v2ex 看到的一个很有意思的帖子。帖子楼主贴了一段方舟编译器的开源代码,然后说感觉是本科生的作业。但马上被回复帖子的大佬指出,代码其实是使用了一种循环优化方法,叫做达夫设备。华为代码乱不乱我不管,先来看一看达夫设备是怎么做的。

1. What it for?

根据 wiki:

In the C programming language, Duff’s device is a way of manually implementing loop unrolling by interleaving two syntactic constructs of C: the do-while loop and a switch statement. Its discovery is credited to Tom Duff in November 1983, when Duff was working for Lucasfilm and used it to speed up a real-time animation program.

简而言之,达夫设备就是结合使用 C 语言中的 switch 和 do-while 语句,来实现循环展开的一种方法,其主要功能是减少对循环条件的判定次数。

2. How it does?

考虑这么一种场景:我们需要将一定长度的数据写到某 io 接口。一般我们的实现(此处借用 Duff 在 K&R C 中的原始代码)像这样:

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

这个代码简单易懂,完全没有毛病。每进行一次循环操作,就检测一次循环条件。

那么从优化的角度来看,我们有没有方法来减少对循环条件的判定次数?

马上一种很直观的方法就浮现出来了:我们将数据分组送,代码类似于:

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

但是 Tom Duff 有一种他自己惯用的方式,即 Duff’s device,其代码如下:

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);
    }
}

这个代码初看令人费解,费解的主要原因在于我们真的能这么把 switch 和 do-while 结合起来这么使用吗? Duff 的原话是:But it compiles and runs just fine.

举个例子,假设 count 是 20,首先 switch 从 case 4 开始,然后 fall through 执行到 case 1,遇到一个 loop 的结束位置,此时 n > 0, 代码跳转到 do-while loop body 开始的地方,也就是 case 1 内执行。所以 switch 语句只被执行了一次,然后就是正常的 do-while 语句的执行。直到 n 为 0,整个数据传送结束。

其中让人不解的地方也就是 do-while 语句竟然能跳转到 switch 语句的内部执行,而且这个竟然是真的允许的。

3. 总结

达夫设备作为一个 loop unwind 的方法,结合使用 switch 和 do-while 语句,减少了对循环条件的检查次数,并且自动处理了数据中的剩余部分。

但其也并不一定是适用于所有场景的。

引用 wiki 上的几句话:

When numerous instances of Duff’s device were removed from the XFree86 Server in version 4.0, there was an improvement in performance and a noticeable reduction in size of the executable.[7] Therefore, when considering this code as a program optimization, it may be worth running a few benchmarks to verify that it actually is the fastest code on the target architecture, at the target optimization level, with the target compiler, as well as weighing the risk that the optimized code will later be used on different platforms where it is not the fastest code.

测一测果然才是硬道理。

引用