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进入循环。