前几天在网上看见了一段代码,叫做“Duff's Device”,后经验证它曾出现在Bjarne的TC++PL里面:
void send( int * to, int * from, int count)
// Duff设施,有帮助的注释被有意删去了
{
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语句和一个do-while语句糅合在了一起。而在我看过的所有关于C和C++的书中,这样的代码都是毫无道理的。然而,无论是在VS2005还是在GCC4.1.2下,这段代码都能正确地通过编译。加上适当的main函数,它都可以正常运行。我百思不得其解。上网去查,也没查到好答案。
怎么办?先看看它的汇编代码吧,也许可以通过它的汇编代码看出它的意思。
gcc -S send.cpp
粗略地一看,汇编代码都已经上百行了,而且里面还有一个跳转表,十几个标号。一般情况下,几十行的汇编代码都已经不太好看懂了,要把这几百行汇编完全看懂,估计需要花很多时间。
既然直接来太麻烦,那就用简便一点的方法吧:
#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的值 程序输出
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那里(从此,这个swicth语句就再也没有用了)。程序继续顺序执行,再当它执行到while那里时,就会判断循环条件。若为真,则while循环开始,程序跳转到do那里开始执行循环(这时候由于已经没有了switch,所以后面的标号就变成普通标号了,即在没有goto语句的情况下就可以忽略掉这些标号了);为假,则退出循环,即程序中止。
忙活了几个小时,终于明白这段代码是怎么回事了。回想一下,自己以前也曾写过类似C的语法但比C语法简单很多的解释器,用的是递归子程序法。而如果用递归下降法来分析这段代码,是肯定会有问题的。
至于它是怎么正确编译并运行的,这需要去研究一下C编译器,这个以后再说。现在,还是再来看看达夫设备吧。其实,这个send函数的签名就已经很具有提示性了:把from数组中的元素拷贝count个到to里面去。于是有人会说,这个工作简单,不就这样吗:
void my_send( int * to, int * from, int count)
{
for ( int i = 0 ; i != count; ++ i) {
* to ++ = * from ++ ;
}
}
这段代码的确很简洁,也是正确的,而且生成的机器码也比send函数短很多。但是却忽略了一个因素:执行效率。计算一下就可以知道,my_send函数里面的循环条件,即i和count的比较运算的次数,是达夫设备的8倍!在做整数赋值这种耗时很少的工作时,这种耗时相对较高的比较工作是会大大地影响函数整体的效率的。达夫设备则是一种非常巧妙的解决办法(当然,它利用到了编译器的一些实现上的工作),而且如果把8换成更大的数的话,效率就还可以提高!
它的思路是这样的:把原数组以8个int为单位分成若干个小组,复制的时候以小组为单位复制,即一次复制8个 int。也就是说,在my_send函数中以一次比较运算的代价换来1个int的复制,而在达夫设备中,却能以一次比较运算的代价换来8个int的复制。而switch语句则是用来处理分组时剩下的不到8个的int(这些剩余的不是数组最后的,而是数组最开始的),很巧妙。
总结:像达夫设备这样的代码,从语言的角度来看,我个人觉得不值得我们借鉴。因为这毕竟不是“正常”的代码,至少C/C++标准不会保证这样的代码一定不会出错。另外,这种代码估计有很多人根本都没见过,如果自己写的代码别人看不懂,这也会是一件很让人头疼的事。然而,从算法的角度来看,我觉得达夫设备是个很高效、很值得我们去学习的东西。把一次消耗相对比较高的操作“分摊“到了多次消耗相对比较低的操作上面,就像vector<T>中实现可变长度的数组的思想那样,节省了大量的机器资源,也大大提高了程序的效率。这是值得我们学习的。
分享到:
相关推荐
本文档为alpha混合最初的设计文档,由Thomas Porter和Tom Duff两位提出并编撰
Direct Methods for Sparse Matrices (I. S. Duff, A. M. Erisman, J. K. Reid).pdf
Duff&P----s-食品零售行业洞察2020年春季篇(英文)-2020.7-25页精品报告2020.pdf
波特·达夫 一个闲置的项目,用嵌入式TeX重写了Markdown中经典的合成纸,以进行数学计算。 使用所需的任何内容进行编辑: 似乎可以应对。... 用于创建SVG格式图。 去做 需要从原始PDF中提取“点灰”图像并导入。...
达芙数据的东西,因此达芙。
用法 var Duff = require ( 'duff.js' ) var result = Duff . duff ( ORIGNAL_OBJECT , TARGET_OBJECT , OPTIONS ) result . errors // array of error messages result . value // boolean value specifying ...
波特-达夫算子奥斯汀·海斯特CS 6420-计算机视觉UMSL SP2021,Sanjiv Bhatia教授目的分配的目的是实现Porter-Duff运算符以合成图像。 操作员将通过驱动程序进行测试。 任务Porter-Duff运算符用于合成带有二进制掩码...
- 采用Duff's Device等技术优化循环结构。 - 避免深度递归,考虑迭代实现。 6. **使用查表法**: - 对于复杂但重复的计算,如三角函数等,预先计算好结果存入表格,运行时直接查找。 ### 提升运行速度: 1. **
Book Description The first book on parallel MATLAB and the first parallel computing book focused on the design, code, debug, and test techniques required to quickly produce efficient parallel programs...
Duff 是一个 Unix 命令行实用程序,用于快速查找给定文件集中的重复项。 Duff 是用 C 编写的,应该在大多数现代 Unices 上构建和运行。
下面列出的特性未必奇怪,有的算是有趣。 1)a[2] 等价于 2[a] “aabbccdd”[5] 等价于 5[“aabbccdd”] 这条特性可以用于使用数组、指针、字符串,但不能用在变量定义时。...3)Duff’s Device http://en.wikipedia.or
DUFF是Windows的(将是)一种工具,用于查找和处理计算机文件系统和/或网络上的重复文件。 它将具有许多内置和基于插件的文件比较层,重复标记和文件集处理程序。
练习 23: Duff's Device 练习 24: 输入输出与文件 练习 25: 可变参数函数 练习 26: 编写第一个真正完整的C程序 练习 27: 编程的创新与保守 练习 28: Makefile项目构建文件 练习 29: 库和链接 练习 30: 自动化测试 ...
Matlab频谱分析程序.pdf
求解Chen系统的最大lyapunov指数。求解方法为定义法。两条相轨线的步长为初设距离d0的基础上加上相对分量。求解时直接运行chen_lyapunov.m即可。可移植性强,比如换求其他系统的最大lyapunov指数,只需要改变变量...
DM6193-WS-SU15 纽约大学理工学院综合数字媒体库Web Studio(DM-UY 6193)。 2015年夏季。学院:De Angela L. Duff
使用 ioLight 便携式显微镜检测动物粪便寄生虫
脚本 Scrip 是一种使用解析表达式语法 (PEG) 和解析器(由生成)... Duff paid 500 on behalf of Buff,Gruff and Buff paid 1000 on behalf of Duff,Gruff 解析器结果 解析器接受上述语法的脚本并返回一个 JSON 响应,
我们证明,在圆上压缩时,N $$ ... 这些解决方案描述了弦和波浪的通常叠加,并在横向上附加了BPST瞬时子,类似于Duff,Lü和Pope的规范重音弦。 获得的解决方案之一是在半径不同的两个AdS 3×S 3几何形状之间平滑插值。
内容简介 《你必须知道的495个C语言问题》以问答的形式组织内容,讨论了学习或使用C语言的过程中经常遇到的一些问题。书中列出了C用户经常问的400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数...