C语言冷知识：Duff's Device(达夫设备)

vlambda
2020-03-25

C语言冷知识：Duff's Device(达夫设备)

相信大家主要都是写业务逻辑的if else程序员，面向if、else、for、while、switch编程。但是你见过switch嵌套do..while吗？

void send( int * to, int * from, int count){ int 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)。咋一看，这玩意能编译通过？别说，还真能。

这是语言律师在炫技吗？不是，这东西在当时确实也有一些实用价值（不过大家不要学，在公司写代码写这个，估计会被老大打死）。

1983年，在卢卡斯影业（没错，就是星球大战那个卢卡斯）上班的程序员Tom Duff，为了加速一个实时动画程序发明了这一写法。

Tom Duff

应用的是C语言里面case 标签的Fallthrough特性（其实就是没有break继续执行）。

简单讲下背景。最早他是想实现从一个数组复制数据到一个寄存器。

duff 写的第一版（大众版）

第一次是这样写的(略有修改，补了返回值声明）：

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

开头一坨，你可能没加过，但是其实C语言课本里应该都有讲过，这种“古早”的函数定义方式：把参数和参数类型分离。其实等价于：

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

先忽略register可能更清晰一点（暂时忽略越界、覆盖这种事）：

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

一般人应该都是这么写的。但是他的使用场景下，count永远是8的倍数，然后他就写了第二版（我直接去掉了古早的语法）。

duff 写的第二版（特化版）

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

你可能觉得这代码太丑了，有啥意义。也无非就是减少了，比较次数。其实在汇编层面讲 do... while(--count > 0) 这个代码（不算里面的逻辑）是6条指令（不同编译器可能不同）。大家可以用godbolt.org/ 测一下。

如果原始count是256，但就这一部分指令减少（256-256/8）*6=（256-32）*6=1344。当然这个并不准确，因为写法2 引入了额外的除法操作（int n = count/8)，对应6条指令：

实际减少的指令约为1344-6*32=1152条。当然这个数字也不一定准，可能我还有遗漏。大家不要较真啦。大概就是确实会减少指令数。

这样就够了吗。达夫又写了第三版！也就是最终的达夫设备。

duff写的第三版（Duff's Device)

void send3(short* to, short* from, int count){ int 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); }}

这一版，其实在性能上较第二版，并没有什么提升。这一版的意义在于将第二版的思想，在通用性上完成了进化！我们可以发现，最终版的达夫设备，count不局限于一定是8的倍数了！而第二版存在这个限制。

然而时至今日，达夫设备到底还能否提高性能是存疑的，因为编译器也早已今非昔比。在代码里显式地用这种Trick的方式进行优化，可能反而阻碍了编译器潜在的优化。

vlambda博客
学习文章列表