达夫设备（Duff's device）

平板电脑查找丢失设备：使用查找我的iPad或Find My Device服务 #生活技巧# #数码产品使用技巧# #平板电脑使用小窍门#

在计算机科学领域，达夫设备（英文：Duff's device）是串行复制（serial copy）的一种优化实现，通过汇编语言编程时一常用方法，实现展开循环，进而提高执行效率。这一方法据信为当时供职于卢卡斯影业的汤姆·达夫于1983年11月发明，并可能是迄今为止利用C语言switch语句特性所作的最巧妙的实现。 

目录

1 优化背景 2 原版代码 3 实现机制 4 性能表现 5 斯特劳斯鲁普版代码 6 注释 7 参考资料 8 延伸阅读 9 外部链接

优化背景

在编程时，循环展开注重于利用批量处理，减少总处理分支数。而在串行复制数据时，当总循环次数无法被展开后循环的增量整除时，一般就用直接跳转到展开后循环体中部的方式，完成剩余数据的复制流程。

因此，根据循环展开的思想，针对串行复制数据的需要，汤姆·达夫以每次迭代时赋最多8个值的方式，用C语言写出了一个优化实现，成功优化了串行复制的效率。

原版代码

若要将数组元素复制进存储器映射输出寄存器，较为直接的做法如下所示[注 1]：

1 do { /* count > 0 assumed （假定count的初始值大于0） */ 2 *to = *from++; /* Note that the 'to' pointer is NOT incremented （注意此处的指针变量to指向并未改变） */ 3 } while(--count > 0);

达夫洞察到，若在这一过程中将一条switch和一个循环相结合，则可展开循环，实现如下所示[注 2]：

1 send(to, from, count) 2 register short *to, *from; 3 register count; 4 { 5 register n = (count + 7) / 8; 6 switch(count % 8) { 7 case 0: do { *to = *from++; 8 case 7: *to = *from++; 9 case 6: *to = *from++; 10 case 5: *to = *from++; 11 case 4: *to = *from++; 12 case 3: *to = *from++; 13 case 2: *to = *from++; 14 case 1: *to = *from++; 15 } while(--n > 0); 16 } 17 }

实现机制

达夫设备基于汇编语言编程中常用的“在复制时最小化判断数和分支数”所用算法，并以C语言实现。代码看起来虽与环境格格不入，但仍可与C兼容，其因有二：

一方面，C语言对switch语句的规范较松。达夫设备发明时，正值《C程序设计语言》第一版引领C语言规范，而按其中规定，在switch控制语句内，条件标号（case）可以出现在任意子语句之前，充作其前缀。另外，若未加入break语句，则在switch语句在根据条件判定，跳转到对应标号，并开始执行后，控制流会无视其余条件标号限定，一直执行到switch嵌套语句的末尾，此即switch语句的“掉落”（fall-through）特性。利用以上特性，这段代码便可从连续地址中将count个数据复制到存储器映射输出寄存器中。

另一方面，C语言对跳转到循环内部提供了支持，因而此处的switch/case语句便可跳转到循环内部。

许多C语言编译器会仿效汇编语言的编程方式，将switch语句转换为转移表，从而提高执行效率。在C语言中，switch语句默认的“掉落”特性长期以来亦备受争议，而达夫也发觉，“这段代码成为了这一讨论中某些观点的论据，但我不确定到底是支持还是否定（这些观点）。”

性能表现

从速度上说，由于采用了循环展开技巧，使所需处理的分支数减少，从而降低了在处理分支时，中断与刷新流水线的巨大运算开销，因而相较于简单、直接的循环代码，这段代码的执行效率较高。另外，由代码易知，若不带switch语句，则这段代码只能复制8*n个数据项，而若count无法为8整除，则仍有count%8（即count除于8的余数）项未处理；有鉴于此，此间嵌入了switch/case语句，负责处理剩余数据。

但是，达夫设备亦有其局限性。在某些环境下，利用switch/case语句处理剩余数据项，有时并非最优选择；相对应的，若采用双循环机制（先实现一个展开后循环，复制8*n个数据项，而后再实现另一循环，复制剩余数据项），可能反倒更快。究其肇因，则常是由于编译器无法针对达夫设备进行优化，但亦可能是因某些架构的流水线与转移预测机制有所差异[1]。除此以外，据测试看，当从XFree86 Server 4.0代码中清理掉所有达夫设备代码后，执行性能却大幅提升[2]。因此，若打算使用达夫设备，最好先针对所用的硬件架构、优化等级和编译器对达夫设备进行基准测试，而后再做定夺。

斯特劳斯鲁普版代码

原版的达夫设备仅能满足将数据复制到一个（存储器映射）寄存器的需求。若要在存储地址间串行复制数据，则在每次引用指针to时，都需进行一次自增操作，如下所示：

此版代码摘自比雅尼·斯特劳斯特鲁普著《C++程序设计语言》一书的“这段代码有何用？（what does this code do?）”练习部分，而他之所以如此修改，很可能是因考虑到编程新手一般对存储器映射输出寄存器一无所知。值得一提的是，针对串行复制的需求，标准C语言库提供了memcpy函数，而其效率不会比斯特劳斯鲁普版的达夫设备低，并可能包含了针对特定架构的优化，从而进一步大幅提升执行效率[3][4]。

注释

参考资料

本条目部分或全部内容出自以GFDL授权发布的《自由在线电脑词典》（FOLDOC）条目Duff's device。

^ James Ralston's USENIX 2003 Journal ^ 曹子德. Re: [PATCH] Re: Move of input drivers, some word needed from you. Linux Kernel Archive Mailing List. ^ Wall, Mike. Using Block Prefetch for Optimized Memory Performance. mit.edu. 2002-03-19 [2012-09-22]. ^ Fog, Agner. Optimizing subroutines in assembly language. Copenhagen University College of Engineering. 100 ff. 2012-02-29 [2012-09-22].

延伸阅读

比雅尼·斯特劳斯特鲁普, C++程序设计语言第三版. Addison-Wesley, ISBN 0-201-88954-4 布莱恩·柯林汉与丹尼斯·里奇, C程序设计语言.

外部链接

汤姆·达夫本人对达夫设备机制的解释（英文） Duff's device, C-FAQ.com（英文） A Reusable Duff Device, Dr.Dobb's Journal（英文） 汤姆·达夫本人在USENET上的原始讨论（英文）

网址：达夫设备（Duff's device） https://www.yuejiaxmz.com/news/view/644439

相关内容

pytorch 设置变量的device=‘cpu’ or ‘cuda‘
pytorch中的model=model.to(device)使用说明
批量设备管理简介：如何高效管理大量物联网设备
IoT物联网设备OTA固件升级开发实践——设备管理运营类
如何获取用户绑定的设备列表
如何调用API获取设备组的设备列表
“Vue.js与智能家居：构建设备分类管理系统“ “创建现代化智能家居设备控制面板的最佳实践“ “如何用Vue实现智能家居设备的状态管理与控制“ “简洁又实用：打造一款高效的智能家居设备管理平台“ “
家庭桥接谷歌Nest设备插件: 使用Google智能设备管理API
如何开发设备
建筑节能新篇章智能设备双十一特惠攻略

随便看看