前言:
现时我们对“雨过天晴支持win10吗”大致比较讲究,同学们都需要剖析一些“雨过天晴支持win10吗”的相关资讯。那么小编同时在网上网罗了一些有关“雨过天晴支持win10吗””的相关文章,希望同学们能喜欢,大家快快来了解一下吧!相信大家写业务逻辑的时候,都是面向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);}
这种写法减少了比较次数,在汇编层面单纯讲到下面代码的时候
do... while(--count > 0)
总共有6条指令。大家可以用godbolt.org/ 测一下。如下(汇编测试参考网上资源,大家可以自行测试)
subl $1,-4(%rbp)cmp1 $0,-4(%rgp)setg %al,testb %al,%alje ,L8jmp ,L7
如果原始count是256,就这一部分指令减少(256-256/8)*6=(256-32)*6=1344。对应6条指令:
movl -36(%rbp),%eaxleal 7(%rax),%edxtestl %eax,%eaxcmovs %edx,%eaxsarl $3,%eaxmovl %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 <Windows.h>#define count 999999999long 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 <Windows.h>#define count 999999999long 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 写法经常研究一下还是很有乐趣的,你们觉得呢……
标签: #雨过天晴支持win10吗