龙空技术网

冷知识:达夫设备(Duff's Device)效率真的很高吗?

技术让梦想更伟大 131

前言:

现时我们对“雨过天晴支持win10吗”大致比较讲究,同学们都需要剖析一些“雨过天晴支持win10吗”的相关资讯。那么小编同时在网上网罗了一些有关“雨过天晴支持win10吗””的相关文章,希望同学们能喜欢,大家快快来了解一下吧!

相信大家写业务逻辑的时候,都是面向if、elseforwhileswitch编程。但是你见过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吗