加载中…
个人资料
南冠彤
南冠彤
  • 博客等级:
  • 博客积分:0
  • 博客访问:415,310
  • 关注人气:59
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

(转)达夫设备(Duff's Device)的详细说明

(2012-05-19 17:20:08)
标签:

杂谈

分类: CPP/C

http://blog.csdn.net/kingmax26/article/details/5252657

http://oss.org.cn/kernel-book/ccfaq/node380.html

前几天在网上看见了一段代码,叫做“Duff's Device”,后经验证它曾出现在Bjarne的TC++PL里面: 

 void send( int * to, int * from, int count)
         
 //    Duff设施,有帮助的注释被有意删去了  
 
{
         
 int (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   = 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 ( --  > 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   =   0  !=  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>中实现可变长度的数组的 思想那样,节省了大量的机器资源,也大大提高了程序的效率。这是值得我们学习的。

 

 

 

void duff_memcpy( char* to, char* from, size_t count )

 {

    size_t 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,是用Tom Duff的名字来命名的。很有名的一个东西,用来优化拷贝的,据说和Rob Pike此牛还有点儿关系~!不过注意,原始的duff’s device中的to可是不变的,因为它指向一个映射到内存的寄存器。

这是个很棒的迂回循环展开法, 由 Tom Duff 在 Lucasfilm 时所设计。它的 ``传统" 形态, 是用来复制多个字节: 
    register 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 个字节从 from 指向的数组复制到 to 指向的内存地址 (这是个内存映射的输出寄存器, 这也是为什么它没有被增加)。它把  swtich 语句和复制 8 个字节的循环交织在一起, 从而解决了剩余字节的处理问题 (当 count 不是 8 的倍数时)。相信不相信, 象这样的把  case 标志放在嵌套在 swtich 语句内的模块中是合法的。当他公布这个技巧给 C 的开发者和世界时, Duff 注意到 C 的 swtich  语法, 特别是 ``跌落" 行为, 一直是被争议的, 而 ``这段代码在争论中形成了某种论据, 但我不清楚是赞成还是反对"。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有