達夫設備

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

## 優化背景

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

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

## 原版代碼

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

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

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

```c
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的餘數的各個點上：

```c
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）特性。利用以上特性，這段代碼便可從連續地址中將`count`個數據複製到存儲器映射輸出寄存器中。

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

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

## 性能表現

功能等價的版本`switch`和`while`不交錯

```c
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`個數據項，和另一循環複製零餘數據項）。究其肇因，則常是由於編譯器無法針對達夫設備進行優化，但亦可能是因某些架構的流水線與預測 (電腦架構)機制有所差異。除此以外，據測試來看，當從XFree86 Server 4.0代碼中清理掉所有達夫設備代碼後，執行效能卻大幅提升。因此，若打算使用達夫設備，最好先針對所用的硬體架構、優化等級和編譯器對達夫設備進行基準測試 (電腦)，而後再做定奪。

## 史特勞斯魯普版代碼

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

```c
  *to++ = *from++;
```

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

## 參見

- 協程 – 受達夫設備的影響，有人採用C/C++的「`switch`穿透」特性實現協程。
- Jensen設備

## 外部連結

- 湯姆·達夫本人對達夫設備機制的解釋
- Duff's device , C-FAQ.com
- A Reusable Duff Device , Dr.Dobb's Journal