热门问题
时间线
聊天
视角

達夫設備

来自维基百科，自由的百科全书

Remove ads

在計算機科學領域，達夫設備（英文：Duff's device）是串行複製（serial copy）的一種優化（英語：Program optimization）實現，通過匯編語言編程時一常用方法，實現展開循環，進而提高執行效率。這一方法據信為當時供職於盧卡斯影業的湯姆·達夫（英語：Tom Duff）於1983年11月發明，並可能是迄今為止利用C語言switch語句（英語：Switch statement）特性所作的最巧妙的實現。

優化背景

在編程時，循環展開注重於利用批量處理，減少總處理分支數。而在串行複製數據時，當總循環次數無法被展開後循環的增量整除時，一般就用直接跳轉到展開後循環體中部的方式，完成零餘數據的複製流程。

因此，根據循環展開的思想，針對串行複製數據的需要，湯姆·達夫以每次迭代時賦最多8個值的方式，用C語言寫出了一個優化實現，成功優化了串行複製的效率。

原版代碼

若要將數組元素複製進存儲器映射輸出寄存器，較為直接的做法如下所示： 

send(to, from, count)
register short *to, *from;
register count;
{
    do {                /* 假定了count > 0 */
        *to = *from++;    
    } while (--count > 0);
}

注意這段代碼所實現的並非「存儲器到存儲器」的複製，因而不需*to++，採用循環展開將循環體展開為8疊（eight-fold），代碼如下： 

send(to, from, count)
register short *to, *from;
register count;
{
    register n = count % 8;
    while (n-- > 0) {
        *to = *from++;
    }
    n = count / 8;
    if (n == 0) return;     
    do {
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
    } while (--n > 0)
}

達夫洞察到可以利用上匯編程序員的跳轉到循環體內的技術，這可以通過交錯一條switch語句和一個循環來實現，即把switch的case標記在循環體內對應於count/8的餘數的各個點上[1]： 

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);
	}
}
Remove ads

實現機制

達夫設備基於匯編語言編程中常用的「在複製時最小化判斷數和分支數」所用算法，並以C語言實現。代碼看起來雖與環境格格不入，但仍可與C語言相容，其因有二：

一方面，C語言對switch語句的規範較松。達夫設備發明時，正值《C程序設計語言》第一版引領C語言規範，而按其中規定，在switch控制語句內，條件標號（case）可以出現在任意子語句之前，充作其前綴。另外，若未加入break語句，則在switch語句在根據條件判定，跳轉到對應標號，並開始執行後，控制流會無視其餘條件標號限定，一直執行到switch嵌套語句的末尾，此即switch語句的「穿透」（fallthrough）特性[2]。利用以上特性，這段代碼便可從連續地址中將count個數據複製到存儲器映射輸出寄存器中。

另一方面，C語言對跳轉到循環內部提供了支持[3]，因而此處的switch/case語句便可跳轉到循環內部。

許多C語言編譯器會仿效匯編語言的編程方式，將switch語句轉換為轉移表，從而提高執行效率。在C語言中，switch語句默認的「穿透」特性長期以來亦備受爭議，而達夫也發覺，「這段代碼成為了這一討論中某些觀點的論據，但我不確定到底是支持還是否定（這些觀點）。」

性能表現

更多信息 功能等價的版本 switch和while不交錯 ...

從速度上說，由於採用了循環展開技巧，使所需處理的分支數減少，從而降低了在處理分支時，中斷與刷新流水線的巨大運算開銷，因而相較於簡單、直接的循環代碼，這段代碼的執行效率較高。另外，由代碼易知，若不帶switch語句，則這段代碼只能複製8*n個數據項，而若count無法為8整除，則仍有count%8（即count除於8的餘數）項未處理；有鑑於此，此間嵌入了switch/case語句，負責處理零餘數據。

但是，達夫設備亦有其局限性。在某些環境下，利用switch/case語句處理零餘數據項，有時並非最優選擇；相對應的，若採用雙循環機制可能反倒更快（實現一個展開後的循環複製8*n個數據項，和另一循環複製零餘數據項）。究其肇因，則常是由於編譯器無法針對達夫設備進行優化，但亦可能是因某些架構的流水線與分支預測（英語：Predication (computer architecture)）機制有所差異[4]。除此以外，據測試來看，當從XFree86 Server 4.0代碼中清理掉所有達夫設備代碼後，執行效能卻大幅提升[5]。因此，若打算使用達夫設備，最好先針對所用的硬件架構、優化等級和編譯器對達夫設備進行基準測試（英語：Benchmark (computing)），而後再做定奪。

Remove ads

斯特勞斯魯普版代碼

原版的達夫設備僅能滿足將數據複製到一個（存儲器映射）寄存器的需求。若要在存儲地址間串行複製數據，則在每次引用指針to時，都需進行一次自增操作，如下所示： 

  *to++ = *from++;

此版代碼摘自比雅尼·斯特勞斯特魯普著《C++程序設計語言》一書的「這段代碼有何用？（what does this code do?）」練習部分，而他之所以如此修改，很可能是因考慮到編程新手一般對存儲器映射輸出寄存器一無所知。值得一提的是，針對串行複製的需求，標準C語言庫提供了memcpy函數，而其效率不會比斯特勞斯魯普版的達夫設備低，並可能包含了針對特定架構的優化，從而進一步大幅提升執行效率[6][7]。

參見

  • 協程 – 受達夫設備的影響，有人採用C/C++的「switch穿透」特性實現協程[8]。
  • Jensen設備（英語：Jensen's Device）

參考資料

外部連結

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads