热门问题
时间线
聊天
视角

達夫裝置

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

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