本来想转一篇江南一散人（原点技术）的文章, 但觉得可以写得再简略一些，于是就写了个简化版本。不算原创，算是改写了一下吧，其中插入了一些笔者个人的补充、段落顺序调整以及简化。
1983年11月，一位叫Tom Duff的大牛在编写串口通信程序时遇到了一个需求：从一个地址from拷贝count个字节到另一个地址to.
怎么样？很简单吧。我们伸手就来。
void send(uint8_t* to, uint8_t* from, uint16_t count)
{
do {
// suppose count is always > 0
*to = *from++;
} while (--count > 0);
}
代码多么清晰、明了、干净、自然！还有什么问题？还有一个大问题：性能不够好。
哦，对了，好像不止这一个问题，还有内容覆盖的问题。比如，若to位于from和from+count之间，这不是把尚未拷贝的部分给写坏了么？不过这个问题不在本文讨论范围之内，也并不难解决，我们就先假设不存在内容覆盖问题。
为什么说性能不够好呢？
因为“无用指令”太多，并且无法充分发挥CPU的ILP（指令级并行）技术。
来看一下汇编：
send:
pushq %rbp
movq %rsp, %rbp
movq %rdi, -8(%rbp) ;参数to压栈
movq %rsi, -16(%rbp) ;参数from压栈
movl %edx, %eax
movw %ax, -20(%rbp) ;参数count压栈
.L2:
movq -16(%rbp), %rax ; *to = *from++;
leaq 1(%rax), %rdx
movq %rdx, -16(%rbp)
movzbl (%rax), %edx
movq -8(%rbp), %eax
movb %dl, (%rax)
movzwl -20(%rbp), %eax ; while(--count > 0);
subl $1, %eax
movw %ax, -20(%rbp)
cmpw $0, -20(%rbp)
jg .L2
nop
popq %rbp
ret
讲解下汇编：
- x64上优先使用寄存器传递，对于send()函数，第一个参数to存放在寄存器 rdi 中，第二个参数from存放在 rsi 中，第三个参数 count 存放在寄存器 edx 中。
- 第2~7行，把三个参数分别压入栈中；
- 第9~14行，对应C语言的*to = *from++；
- 第15~19行，对应C语言的while (–count > 0)；
- 最后几句，恢复栈帧并返回
所以，第9-19行属于热点路径，也就是主循环体。第9-14行属于有效指令，第15-19行对于期望的数据结果来说就是无用指令。
我们看到，热点路径中，无用指令数占了整个热点路径指令数的一半，其开销也占到整个函数的50%！
那么，怎么解决性能不够的问题呢？
联想到之前的博文从“循环展开”谈起, 我们知道，这里要循环展开了。
下面提供2个测试程序。test1.c 是普通写法，test2.c是循环展开。
test1.c
int main()
{
long i=0, k=0;
for(i=0; i<10000000000; i++)
{
k++;
}
return 0;
}
test2.c
int main()
{
long i=0, k=0;
for(i=0; i<10000000000; i+=8)
{
k++;
k++;
k++;
k++;
k++;
k++;
k++;
k++;
}
return 0;
}
下面以本人的笔记本电脑在Windows操作系统下运行Cygwin来测试：
test1.c的执行结果：稳定值是3.x秒
$ gcc test1.c -o test1
$ time ./test1
real 0m3.961s
user 0m3.531s
sys 0m0.000s
test2.c 的执行结果是： 稳定值是2.x秒
$ gcc test2.c -o test2
$ time ./test2
real 0m2.695s
user 0m2.593s
sys 0m0.000s
二者相差的稳定值大约是1.2秒，而这对于总执行时间只有2、3秒的程序来说，已经是一个很大的比例了。
顺便插一句，如果再加上 -O3的优化，上面的2个程序的性能仍能得到极大幅度的提高（大致是由于使用了register），但test2.c的表现仍稍胜test1.c一点。
把 test2.c 转换为对Duff的需求的实现，代码如下：
void send(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = count / 8;
do {
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
} while (--n > 0);
n = count % 8;
while (n-- > 0) {
*to = *from++;
}
}
其实，代码写到这里，已经差不多了。但是Duff还不满意，他觉得底下多出来一坨很不爽，他想把代码行数再减少一点。于是就有了下面这一段被称为Duff Device的代码：
void send(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = (count+7)/8; // count is always > 0
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);
}
}
没太看明白？没关系，我们来做一个实验。先看下面这段代码，它会输出什么呢？
#include <stdio.h>
int test(int count)
{
int i = 0;
int n = (count+7)/8; // suppose count > 0
switch(count % 8)
{
case 0: do {
i++;
case 7: i++;
case 6: i++;
case 5: i++;
case 4: i++;
case 3: i++;
case 2: i++;
case 1: i++;
} while (--n > 0);
}
return i;
}
int main()
{
printf("%d\n", test(20));
return 0;
}
它仍然是打印出20.
这里利用到了switch语句的2个特性：
- case语句后面的break语句不是必须的；若没有则会继续执行下面一行。
- 在switch语句内，case标号可以出现在任意的子语句之前，甚至运行出现在if、for、while等语句内；因为它只是一个label.
它究竟是怎么工作的呢？
首先，n = (count+7)/8得出 n 等于3.
然后，count % 8得出4， 于是走到case 4这条语句，因为没有break，所以就一直走完case 1；
关键来了：
走完case 1之后，继续做while这句，然后发现n自减后为2，又回到了do这句，自此就没有switch什么事了~
再往后，n为2和1的时候会走2遍完整的循环体，加上最开始switch的4句语句，总共是：2*8+4=20 句 i++.
解释完毕。所以并没有那么难以理解，对吧。
其实个人觉得，写程序也并不一定要写成 Duff Device 这样，只要写成前一个版本的循环展开就可以了，毕竟程序的可读性也很重要。不过要是说起防御性编程，达夫设备则是一个让人无可辩驳的好例子。啊，这难道就是防御性编程的鼻祖吗？
(END)
