达夫设备

缺乏、安全感 2022-01-10 01:13 199阅读 0赞

**转自: [维基百科][Link 1]**

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

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

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

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

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

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

send(to, from, count)
    register short *to, *from;
    register count;
    {
         
            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);
            }
    }

## 实现机制 ##

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

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

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

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

## 性能表现 ##

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

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

## 斯特劳斯鲁普版代码 ##

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

*to++ = *from++;

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

## 注释 ##

## **[^][Link 17]** 这段代码所实现的并非“存储器到存储器”的复制，因而不需\*to++。 ##

1.  **[^][Link 18]** 代码中的循环展开大小可按需增减，并不需一定为8。

[Link 1]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87
[Link 2]: http://zh.wikipedia.org/wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6
[Link 3]: http://zh.wikipedia.org/wiki/%E8%8B%B1%E6%96%87
[Link 4]: http://zh.wikipedia.org/w/index.php?title=%E7%A8%8B%E5%BA%8F%E4%BC%98%E5%8C%96&action=edit&redlink=1
[Link 5]: http://zh.wikipedia.org/w/index.php?title=%E5%AE%9E%E7%8E%B0_%28%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6%29&action=edit&redlink=1
[Link 6]: http://zh.wikipedia.org/wiki/%E6%B1%87%E7%BC%96%E8%AF%AD%E8%A8%80
[Link 7]: http://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B1%95%E5%BC%80
[Link 8]: http://zh.wikipedia.org/wiki/%E5%8D%A2%E5%8D%A1%E6%96%AF%E5%BD%B1%E4%B8%9A
[Link 9]: http://zh.wikipedia.org/w/index.php?title=Tom_Duff&action=edit&redlink=1
[C]: http://zh.wikipedia.org/wiki/C%E8%AF%AD%E8%A8%80
[switch]: http://zh.wikipedia.org/w/index.php?title=Switch%E8%AF%AD%E5%8F%A5&action=edit&redlink=1
[Link 10]: http://zh.wikipedia.org/wiki/%E5%AD%98%E5%82%A8%E5%99%A8%E6%98%A0%E5%B0%84%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA
[Link 11]: http://zh.wikipedia.org/wiki/%E5%AF%84%E5%AD%98%E5%99%A8
[1]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_note-1
[2]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_note-2
[C 1]: http://zh.wikipedia.org/wiki/C%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E8%AF%AD%E8%A8%80
[Link 12]: http://zh.wikipedia.org/w/index.php?title=%E8%BD%AC%E7%A7%BB%E8%A1%A8&action=edit&redlink=1
[Link 13]: http://zh.wikipedia.org/wiki/%E6%B5%81%E6%B0%B4%E7%BA%BF_%28%E8%AE%A1%E7%AE%97%E6%9C%BA%29
[Link 14]: http://zh.wikipedia.org/w/index.php?title=%E8%BD%AC%E7%A7%BB%E9%A2%84%E6%B5%8B&action=edit&redlink=1
[1 1]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_note-3
[2 1]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_note-4
[Link 15]: http://zh.wikipedia.org/w/index.php?title=%E5%9F%BA%E5%87%86%E6%B5%8B%E8%AF%95_%28%E8%AE%A1%E7%AE%97%E6%9C%BA%29&action=edit&redlink=1
[Link 16]: http://zh.wikipedia.org/wiki/%E6%AF%94%E9%9B%85%E5%B0%BC%C2%B7%E6%96%AF%E7%89%B9%E5%8A%B3%E6%96%AF%E7%89%B9%E9%B2%81%E6%99%AE
[C 2]: http://zh.wikipedia.org/w/index.php?title=C%2B%2B%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E8%AF%AD%E8%A8%80_%28%E4%B9%A6%29&action=edit&redlink=1
[memcpy]: http://zh.wikipedia.org/wiki/Memcpy
[3]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_note-amd2002-5
[4]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_note-fog2012-6
[Link 17]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_ref-1
[Link 18]: http://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87#cite_ref-2