前幾天在網上看見了一段代碼，叫做“Duff's Device”，後經驗證它曾出現在Bjarne的TC++PL裡面：
void send( int * to, int * from, int count)
// Duff設施，有幫助的注釋被有意删去了
{
int 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 );
}
}
代碼的結構顯得非常巧妙，把一個switch語句和一個do-while語句糅合在了一起。而在我看過的所有關于C和C++的書中，這樣的代碼都 是毫無道理的。然而，無論是在VS2005還是在GCC4.1.2下，這段代碼都能正确地通過編譯。加上适當的main函數，它都可以正常運作。我百思不 得其解。上網去查，也沒查到好答案。
怎麼辦？先看看它的彙編代碼吧，也許可以通過它的彙編代碼看出它的意思。
gcc -S send.cpp
粗略地一看，彙編代碼都已經上百行了，而且裡面還有一個跳轉表，十幾個标号。一般情況下，幾十行的彙編代碼都已經不太好看懂了，要把這幾百行彙編完全看懂，估計需要花很多時間。
既然直接來太麻煩，那就用簡便一點的方法吧：
#include < iostream >
using namespace std;
int main()
{
int n = 0 ;
switch (n) {
case 0 : do {cout << " 0 " << endl;
case 1 : cout << " 1 " << endl;
case 2 : cout << " 2 " << endl;
case 3 : cout << " 3 " << endl;
} while ( -- n > 0 );
}
}
| n的值 | 程式輸出 |
| 1 2 3 | |
| 1 | 1 2 3 |
| 2 | 2 3 1 2 3 |
| 3 | 3 1 2 3 1 2 3 |
| 其他 | (無輸出) |
這 下終于弄清楚了。原來，那段代碼的主體還是do-while循環，但這個循環的入口點并不一定是在do那裡，而是由這個switch語句根據n，把循環的 入口定在了幾個case标号那裡。也就是說，程式的執行流程是：程式一開始順序執行，當它執行到了switch的時候，就會根據n的值，直接跳轉到 case n那裡（從此，這個swicth語句就再也沒有用了）。程式繼續順序執行，再當它執行到while那裡時，就會判斷循環條件。若為真，則while循環開 始，程式跳轉到do那裡開始執行循環（這時候由于已經沒有了switch，是以後面的标号就變成普通标号了，即在沒有goto語句的情況下就可以忽略掉這 些标号了）；為假，則退出循環，即程式中止。
忙活了幾個小時，終于明白這段代碼是怎麼回事了。回想一下，自己以前也曾寫過類似C的文法但比C文法簡單很多的解釋器，用的是遞歸子程式法。而如果用遞歸下降法來分析這段代碼，是肯定會有問題的。
至于它是怎麼正确編譯并運作的，這需要去研究一下C編譯器，這個以後再說。現在，還是再來看看達夫裝置吧。其實，這個send函數的簽名就已經很具有提示性了：把from數組中的元素拷貝count個到to裡面去。于是有人會說，這個工作簡單，不就這樣嗎：
void my_send( int * to, int * from, int count)
{
for ( int i = 0 ; i != count; ++ i) {
* to ++ = * from ++ ;
}
}
這段代碼的确很簡潔，也是正确的，而且生成的機器碼也比send函數短很多。但是卻忽略了一個因素：執行效率。計算一下就可以知 道，my_send函數裡面的循環條件，即i和count的比較運算的次數，是達夫裝置的8倍！在做整數指派這種耗時很少的工作時，這種耗時相對較高的比 較工作是會大大地影響函數整體的效率的。達夫裝置則是一種非常巧妙的解決辦法（當然，它利用到了編譯器的一些實作上的工作），而且如果把8換成更大的數的 話，效率就還可以提高！
它的思路是這樣的：把原數組以8個int為機關分成若幹個小組，複制的時候以小組為機關複制，即一次複制8個 int。也就是說，在my_send函數中以一次比較運算的代價換來1個int的複制，而在達夫裝置中，卻能以一次比較運算的代價換來8個int的複制。 而switch語句則是用來處理分組時剩下的不到8個的int（這些剩餘的不是數組最後的，而是數組最開始的），很巧妙。
總結：像達夫設 備這樣的代碼，從語言的角度來看，我個人覺得不值得我們借鑒。因為這畢竟不是“正常”的代碼，至少C/C++标準不會保證這樣的代碼一定不會出錯。另外， 這種代碼估計有很多人根本都沒見過，如果自己寫的代碼别人看不懂，這也會是一件很讓人頭疼的事。然而，從算法的角度來看，我覺得達夫裝置是個很高效、很值 得我們去學習的東西。把一次消耗相對比較高的操作“分攤“到了多次消耗相對比較低的操作上面，就像vector<T>中實作可變長度的數組的 思想那樣，節省了大量的機器資源，也大大提高了程式的效率。這是值得我們學習的。
附
void duff_memcpy( char* to, char* from, size_t count )
{
size_t 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);
}
}
duff’s device，是用Tom Duff的名字來命名的。很有名的一個東西，用來優化拷貝的，據說和Rob Pike此牛還有點兒關系～！不過注意，原始的duff’s device中的to可是不變的，因為它指向一個映射到記憶體的寄存器。
這是個很棒的迂回循環展開法, 由 Tom Duff 在 Lucasfilm 時所設計。它的 ``傳統" 形态, 是用來複制多個位元組:
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);
}
這裡 count 個位元組從 from 指向的數組複制到 to 指向的記憶體位址 (這是個記憶體映射的輸出寄存器, 這也是為什麼它沒有被增加)。它把 swtich 語句和複制 8 個位元組的循環交織在一起, 進而解決了剩餘位元組的處理問題 (當 count 不是 8 的倍數時)。相信不相信, 象這樣的把 case 标志放在嵌套在 swtich 語句内的子產品中是合法的。當他公布這個技巧給 C 的開發者和世界時, Duff 注意到 C 的 swtich 文法, 特别是 ``跌落" 行為, 一直是被争議的, 而 ``這段代碼在争論中形成了某種論據, 但我不清楚是贊成還是反對"。