达夫设备

维基百科,自由的百科全书
跳转至: 导航搜索

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

优化背景[编辑]

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

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

原版代码[编辑]

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

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

达夫洞察到,若在这一过程中将一条switch和一个循环相结合,则可展开循环,实现如下所示[註 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);
	}
}

实现机制[编辑]

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

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

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

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

性能表现[编辑]

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

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

斯特劳斯鲁普版代码[编辑]

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

  *to++ = *from++;

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

注释[编辑]

  1. ^ 这段代码所实现的并非“存储器到存储器”的复制,因而不需*to++
  2. ^ 代码中的循环展开大小可按需增减,并不需一定为8。

参考资料[编辑]

本條目部分或全部内容出自以GFDL授權發佈的《自由線上電腦詞典》(FOLDOC)条目Duff's device

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

延伸阅读[编辑]

外部链接[编辑]