C 语言 Duff's device

发表于 | 分类于 | 阅读次数

今天看Simon Tatham有关 C 语言中协程的分析时，看到了一段有趣的代码——Duff’s device。在网上找了很多相关的信息，结果都写的乱七八糟，还好 wiki 上有原版的代码，赶紧抄下来分析一下。

原版代码

原版代码要解决的问题非常简单，就是要将一个数组中的 16-bit units（通常是 short 类型）复制到寄存器中，因为是寄存器所以 to 不需要 ++ 操作。

1
2
3
4
5
6
7
8
send(to, from, count)
register short *to, *from;
register count;
{
    do {                          /* count > 0 assumed */
        *to = *from++;
    } while(--count > 0);
}

如果count总是能被 8 整除，那么可以将循环展开，以减少循环次数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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);
}

但事实上count并不一定总被 8 整除，或者说，甚至和 8 没什么关系。Duff 意识到，为了处理不能被 8 整除的count，汇编程序员通常会使用到一个技巧，那就是跳转到循环体内部。我们知道在汇编中使用跳转非常简单，在 C 中或许可以使用goto（但是会非常麻烦），但是大部分高级编程语言甚至是不提供跳转的。Duff’s device 很好地使用了 switch 语句的特性，巧妙地实现了跳转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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);
    }
}

看这代码，循环次数理想情况下是原来的 1/8，当然也可以不是 8 设置其他值。

注意：Duff’s device 最好只作为一个编程技巧来看，如果要将它使用到具体的项目中，需要考虑更多的因素。事实上部分架构的流水线与转移预测机制不同，或者编译器无法针对 Duff’s device 做优化，导致实际效果并不理想。况且，使用 Duff’s device 使得代码难以理解，使用时需要慎重。

实现机制

要实现 Duff’s device 有两个非常重要的前提：

  1. C 语言中规定，在switch控制语句中，case可以出现在任意子语句之前，充当其前缀。另外，如果没有在case结尾加入break语句，那么在结束当前语句之后，控制流会无视其他case继续执行，直至末尾或break，这个特性被称之为“掉落”（fall-through）特性。
  2. C 语言支持跳转到循环内部，因此在这里可以直接跳转到其他case而不是一定要从case0进入循环。