作者： | 来源：互联网 | 2023-10-13 16:13
本文由编程笔记#小编为大家整理，主要介绍了冷知识：达夫设备(Duff'sDevice)效率真的很高吗?相关的知识，希望对你有一定的参考价值。ID：技术让梦想更伟大
本文由编程笔记#小编为大家整理，主要介绍了冷知识：达夫设备(Duff&＃39;s Device)效率真的很高吗?相关的知识，希望对你有一定的参考价值。
ID：技术让梦想更伟大
作者:李肖遥
wechat链接:https://mp.weixin.qq.com/s/b1jQDH22hk9lhdC9nDqI6w
相信大家写业务逻辑的时候，都是面向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 );
}
}
咋的一看，这啥玩意啊，switch/while 这组合能编译通过吗？您可别怀疑，还真能。这个就是达夫设备（Duff‘s Device)
什么是达夫设备
百度百科说法如下：
在计算机科学领域，达夫设备（英文：Duff‘s device）是串行复制（serial copy）的一种优化实现，通过汇编语言编程时一常用方法，实现展开循环，进而提高执行效率。这一方法据信为当时供职于卢卡斯影业的汤姆·达夫于1983年11月发明，并可能是迄今为止利用C语言switch语句特性所作的最巧妙的实现。
达夫设备是一个加速循环语句的C编码技巧。其基本思想是--减少循环测试的执行次数。
简单讲下背景
时间要回到1983年，那是一个雨过天晴的夏天，在卢卡斯影业上班的程序员Tom Duff，他是想为了加速一个实时动画程序，实现从一个数组复制数据到一个寄存器这样一个功能，真脸如下。
一般情况下，若要将数组元素复制进存储器映射输出寄存器，较为直接的做法如下所示
do {
/* count > 0 assumed （假定count的初始值大于0） */
*to = *from++;
/* Note that the ‘to‘ pointer is NOT incremented
（注意此处的指针变量to指向并未改变） */
} while(--count > 0);
但是达夫洞察到，若在这一过程中将一条switch和一个循环相结合，则可展开循环，应用的是C语言里面case 标签的Fall through特性，实际就是没有break继续执行。实现如上代码所示。
其实第一版是这样写的：
void send(to, from, count)
register short *to, *from;
register int count;
{
/* count > 0 assumed */
do {
*to++ = *from++;
} while (--count > 0);
}
这段代码等价于：
void send(register short* to, register short* from, register int count)
{
/* count > 0 assumed */
do {
*to++ = *from++;
} while (--count > 0);
}
但是在这种使用场景下，不易于移植和应用，然后他就更新了第二版，代码如下：
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);
}
这种写法减少了比较次数，在汇编层面单纯讲到下面代码的时候
总共有6条指令。大家可以用godbolt.org/ 测一下。如下(汇编测试参考网上资源，大家可以自行测试)
subl $1,-4(%rbp)
cmp1 $0,-4(%rgp)
setg %al,
testb %al,%al
je ,L8
jmp ,L7
如果原始count是256，就这一部分指令减少（256-256/8）*6=（256-32）*6=1344。对应6条指令：
movl -36(%rbp),%eax
leal 7(%rax),%edx
testl %eax,%eax
cmovs %edx,%eax
sarl $3,%eax
movl %eax,-4(%rbp)
但是这个版本在通用性能还不够，count一定要是8的倍数，所以经过了这两个版本的发展，最终才有了上述那个最终版本的诞生。虽然性能上没有什么优化，但是最终版的达夫设备，count不局限于一定是8的倍数了！
实现机制、代码解析
实现机制
在达夫解决这个问题的时候，当时的C语言对switch语句的规范是比较松的，在switch控制语句内，条件标号（case）可以出现在任意子语句之前，充作其前缀。
此外若未加入break语句，则在switch语句在根据条件判定，跳转到对应的标号，并在开始执行后，控制流会一直执行到switch嵌套语句的末尾。
利用这种特性，这段代码可以从连续地址中将count个数据复制到存储器中，映射输出寄存器中。
另一方面，C语言本身也对跳转到循环内部提供了支持，因而此处的switch/case语句便可跳转到循环内部。
代码解析
首先说下这段代码，编译没问题，我们写个代码如下：
#include <iostream >
using namespace std;
int main()
{
int n = 0 ;
switch (n) {
case 0 : do {cout <<" 0 " << endl;
case 1 : cout <<" 1 " << endl;
case 2 : cout <<" 2 " << endl;
case 3 : cout <<" 3 " << endl;
} while ( -- n > 0 );
}
}
根据n的不同输入，实验结果如下
| n的值 | 程序输出 |
|---|
0 |
0 1 2 3 |
1 |
1 2 3 |
2 |
2 3 0 1 2 3 |
3 |
3 0 1 2 3 0 1 2 3 |
这段代码的主体还是do-while循环，但这个循环的入口点并不一定是在do那里，而是由这个switch(n)，把循环的入口定在了几个case标号那里。
即程序的执行流程是：
程序执行到了switch的时候，就会根据n的值，直接跳转到 case n那里，再当它执行到while那里时，就会判断循环条件。若为真，则while循环开始，程序跳转到do那里开始执行循环；为假，则退出循环，即程序中止。（这个swicth语句就再也没有用了）
我们再看以下代码，这里 count 个字节从 from 指向的数组复制到 to 指向的内存地址，是个内存映射的输出寄存器。它把 swtich 语句和复制 8 个字节的循环交织在一起, 从而解决了剩余字节的处理问题 (当 count % 8 ！= 0)。
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 );
}
}
switch内的表达式计算被8除的余数。执行开始于while循环内的哪个位置由这个余数决定，直到最终循环退出（没有break）。Duff‘s Device这样就简单漂亮地解决了边界条件的问题。
性能表现
我们一般使用用for循环或者while循环的时候，如果执行循环内容本身用不了多少时间，本质上时间主要是消耗在了每次循环的比较语句上边。
而事实上，比较语句是有很大优化空间的，我们假设你要循环10000次，结果你从第一次开始就不断的比较是否达到上界值，这是不是很徒劳呢？
我们写一个达夫设备的函数用来测试执行时间(参考网上资源，这个测试不难，不同测试会有不同效果，大家可以自行测试一下)：
int duff_device(int a)
{
resigter x = 0;
int n = (a) / 10;
switch(a%10){
case 0：do{ x++;
case 9：x++;
case 8：x++;
case 7：x++;
case 6：x++;
case 5：x++;
case 4：x++;
case 3：x++;
case 2：x++;
case 1：x++;
}while(--n>0)
}
return x;
}
测试主函数如下
#include
#define count 999999999
long int overtime = count;
int main()
{
printf("over %d",duff_device(overtime));
return 0;
}
执行时间如下
现在我们看一下传统的循环的执行时间,其测试代码如下：
int classical(int a)
{
register x=0;
do{
x ++;
}while(--a>0);
return x;
}
测试主函数如下
#include
#define count 999999999
long int overtime = count;
int main()
{
printf("over %d",classical(overtime));
return 0;
}
执行时间如下
结果显示达夫设备确实缩短了不少时间，这里x的定义是要用register关键字，这样cpu就会把x尽可能存入cpu内部的寄存器，新的cpu应该会有很通用寄存器使用。
值得一提的是，针对串行复制的需求，标准C语言库提供了memcpy函数，而其效率不会比斯特劳斯鲁普版的达夫设备低，并可能包含了针对特定架构的优化，从而进一步大幅提升执行效率。
从不同角度看达夫设备
从语言的角度来看
我个人觉得这种写法不是很值得我们借鉴。毕竟这不是符合我们“正常”逻辑的代码，至少C/C++标准不会保证这样的代码一定不会出错。
另外， 这种代码冷知识，估计有很多人根本都没见过，如果自己写的代码别人看不懂，估计会被骂的。
从算法的角度来看
我觉得达夫设备是个很高效、很值得我们去学习的东西。把一次消耗相对比较高的操作“分摊“到了多次消耗相对比较低的操作上面，就像vector中实现可变长度的数组的思想那样，节省了大量的机器资源，也大大提高了程序的效率。这是值得我们去学习的。
总结
达夫设备能实现的优化效果日趋在减弱，时代在变化，语言在发展，硬件设备在变化，编译器性能优化，除非特殊的需求下，一般还是没必要做像这种层次的性能考量的。不过，这种奇妙的 switch-case 写法经常研究一下还是很有乐趣的，你们觉得呢……
关注微信公众号『技术让梦想更伟大』，后台回复“m”查看更多内容，回复“加群”加入技术交流群。
长按前往图中包含的公众号关注
京公网安备 11010802041100号