達夫裝置

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書

在電腦科學領域，達夫裝置（英文：Duff's device）是串行複製（serial copy）的一種最佳化（英語：Program optimization）實現（英語：implementation），通過匯編語言編程時一常用方法，實現展開迴圈，進而提高執行效率。這一方法據信為當時供職於盧卡斯影業的湯姆·達夫（英語：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);
	}
}

實現機制[編輯]

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

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

另一方面，C語言對跳轉到迴圈內部提供了支援[3]，因而此處的switch/case陳述式便可跳轉到迴圈內部。

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

效能表現[編輯]

功能等價的版本
switch和while不交錯 
send(to, from, count)
register short *to, *from;
register count;
{
    register n = count / 8;
    switch (count % 8) {
        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++;
        case 0: ;
    }
    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陳述式，則這段代碼只能複製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)），而後再做定奪。

斯特勞斯魯普版代碼[編輯]

原版的達夫裝置僅能滿足將數據複製到一個（記憶體對映）暫存器的需求。若要在儲存地址間串行複製數據，則在每次參照指標to時，都需進行一次自增操作，如下所示： 

  *to++ = *from++;

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

參見[編輯]

參考資料[編輯]

本條目部分或全部內容出自以GFDL授權發佈的《自由線上電腦詞典》（FOLDOC）條目Duff's device。

  1. ^ Holly, Ralf. A Reusable Duff Device. Dr. Dobb's Journal. August 1, 2005 [September 18, 2015]. （原始內容存檔於2020-02-26）. 
  2. ^ Brian Kernighan, Dennis Ritchie. The C Programming Language, Second Edition (PDF). Prentice Hall. 1988 [2024-01-19]. （原始內容存檔 (PDF)於2023-03-25）. The switch statement is a multi-way decision that tests whether an expression matches one of a number of constant integer values, and branches accordingly. ……
    Each case is labeled by one or more integer-valued constants or constant expressions. If a case matches the expression value, execution starts at that case. ……
    Because cases serve just as labels, after the code for one case is done, execution falls through to the next unless you take explicit action to escape. ……
    Case labels and default labels are used with the switch statement (Par.A.9.4). ……
    Labels themselves do not alter the flow of control.     
  3. ^ Brian Kernighan, Dennis Ritchie. The C Programming Language, Second Edition (PDF). Prentice Hall. 1988 [2024-01-19]. （原始內容存檔 (PDF)於2023-03-25）. A label has the same form as a variable name, and is followed by a colon. It can be attached to any statement in the same function as the goto. The scope of a label is the entire function. ……
    Because labels have their own name space, they do not interfere with other identifiers and cannot be redeclared.     
  4. ^ James Ralston's USENIX 2003 Journal[失效連結]
  5. ^ 曹子德. Re: [PATCH] Re: Move of input drivers, some word needed from you. Linux Kernel Archive Mailing List. [2013-07-08]. （原始內容存檔於2014-01-08）. 
  6. ^ Wall, Mike. Using Block Prefetch for Optimized Memory Performance (PDF). mit.edu. 2002-03-19 [2012-09-22]. （原始內容存檔 (PDF)於2017-08-30）. 
  7. ^ Fog, Agner. Optimizing subroutines in assembly language (PDF). Copenhagen University College of Engineering: 100 ff. 2012-02-29 [2012-09-22]. （原始內容存檔 (PDF)於2021-03-29）. 
  8. ^ Simon Tatham. Coroutines in C. 2000 [2013-07-07]. （原始內容存檔於2019-11-09）. 

外部連結[編輯]

取自 "https://zh.wikipedia.org/w/index.php?title=达夫设备&oldid=82270283"