加速循環(huán)語句的C編碼技巧

相信大家寫業(yè)務邏輯的時候，都是面向if、else、for、while、switch編程。但是你見過switch嵌套do..while嗎？

先上代碼

void send( int * to, int * from, int count)
{
    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/while 這組合能編譯通過嗎？您可別懷疑，還真能。這個就是達夫設備（Duff's Device)

什么是達夫設備

百度百科說法如下：

在計算機科學領域，達夫設備（英文：Duff's device）是串行復制（serial copy）的一種優(yōu)化實現(xiàn)，通過匯編語言編程時一常用方法，實現(xiàn)展開循環(huán)，進而提高執(zhí)行效率。這一方法據(jù)信為當時供職于盧卡斯影業(yè)的湯姆·達夫于1983年11月發(fā)明，并可能是迄今為止利用C語言switch語句特性所作的最巧妙的實現(xiàn)。

達夫設備是一個加速循環(huán)語句的C編碼技巧。 其基本思想是 --減少循環(huán)測試的執(zhí)行次數(shù)。

簡單講下背景

時間要回到1983年，那是一個雨過天晴的夏天，在盧卡斯影業(yè)上班的程序員 Tom Duff ，他是想為了加速一個實時動畫程序，實現(xiàn)從一個數(shù)組復制數(shù)據(jù)到一個寄存器這樣一個功能，真臉如下。

一般情況下，若要將數(shù)組元素復制進存儲器映射輸出寄存器，較為直接的做法如下所示

do {
  /* count > 0 assumed （假定count的初始值大于0） */    
  *to = *from++;            
  /* Note that the 'to' pointer is NOT incremented 
  （注意此處的指針變量to指向并未改變） */
} while(--count > 0);

但是達夫洞察到，若在這一過程中將一條switch和一個循環(huán)相結(jié)合，則可展開循環(huán)，應用的是C語言里面case 標簽的Fall through特性，實際就是沒有break繼續(xù)執(zhí)行。實現(xiàn)如上代碼所示。

其實第一版是這樣寫的：

void send(to, from, count)
register short *to, *from;
register int count;
{
    /* count > 0 assumed */
    do {        
        *to++ = *from++;
    } while (--count > 0);
}

這段代碼等價于：

void send(register short* to, register short* from, register int count)
{
    /* count > 0 assumed */
    do {                          
        *to++ = *from++;
    } while (--count > 0);
}

但是在這種使用場景下，不易于移植和應用，然后他就更新了第二版，代碼如下：

void send2(short* to, short* from, int count)
{
    int n = count / 8;
    do {
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
        *to++ = *from++;
    } while (--n > 0);
}

這種寫法減少了比較次數(shù)，在匯編層面單純講到下面代碼的時候

do... while(--count > 0)

總共有6條指令。大家可以用godbolt.org/ 測一下。如下(匯編測試參考網(wǎng)上資源，大家可以自行測試)

subl  $1,-4(%rbp)
cmp1  $0,-4(%rgp)
setg  %al,
testb %al,%al
je    ,L8
jmp   ,L7

如果原始count是256，就這一部分指令減少（256-256/8）*6=（256-32）*6=1344。對應6條指令：

movl   -36(%rbp),%eax
leal   7(%rax),%edx
testl  %eax,%eax
cmovs  %edx,%eax
sarl   $3,%eax
movl   %eax,-4(%rbp)

但是這個版本在通用性能還不夠，count一定要是8的倍數(shù)，所以經(jīng)過了這兩個版本的發(fā)展，最終才有了上述那個最終版本的誕生。雖然性能上沒有什么優(yōu)化，但是最終版的達夫設備，count不局限于一定是8的倍數(shù)了！

實現(xiàn)機制、代碼解析

實現(xiàn)機制

在達夫解決這個問題的時候，當時的C語言對switch語句的規(guī)范是比較松的，在switch控制語句內(nèi)，條件標號（case）可以出現(xiàn)在任意子語句之前，充作其前綴。

此外若未加入break語句，則在switch語句在根據(jù)條件判定，跳轉(zhuǎn)到對應的標號，并在開始執(zhí)行后，控制流會一直執(zhí)行到switch嵌套語句的末尾。

利用這種特性，這段代碼可以從連續(xù)地址中將count個數(shù)據(jù)復制到存儲器中，映射輸出寄存器中。

另一方面，C語言本身也對跳轉(zhuǎn)到循環(huán)內(nèi)部提供了支持，因而此處的switch/case語句便可跳轉(zhuǎn)到循環(huán)內(nèi)部。

代碼解析

首先說下這段代碼，編譯沒問題，我們寫個代碼如下：

#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 ); 
   } 
}

根據(jù)n的不同輸入，實驗結(jié)果如下

這段代碼的主體還是do-while循環(huán)，但這個循環(huán)的入口點并不一定是在do那里，而是由這個switch(n)，把循環(huán)的入口定在了幾個case標號那里。

即程序的執(zhí)行流程是：

程序執(zhí)行到了switch的時候，就會根據(jù)n的值，直接跳轉(zhuǎn)到 case n那里，再當它執(zhí)行到while那里時，就會判斷循環(huán)條件。若為真，則while循環(huán)開始，程序跳轉(zhuǎn)到do那里開始執(zhí)行循環(huán)；為假，則退出循環(huán)，即程序中止。（這個swicth語句就再也沒有用了）

我們再看以下代碼，這里 count 個字節(jié)從 from 指向的數(shù)組復制到 to 指向的內(nèi)存地址，是個內(nèi)存映射的輸出寄存器。它把 swtich 語句和復制 8 個字節(jié)的循環(huán)交織在一起, 從而解決了剩余字節(jié)的處理問題 (當 count % 8 ！= 0)。

void send( int * to, int * from, int count)
{
    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內(nèi)的表達式計算被8除的余數(shù)。執(zhí)行開始于while循環(huán)內(nèi)的哪個位置由這個余數(shù)決定，直到最終循環(huán)退出（沒有break）。Duff's Device這樣就簡單漂亮地解決了邊界條件的問題。

性能表現(xiàn)

我們一般使用用for循環(huán)或者while循環(huán)的時候，如果執(zhí)行循環(huán)內(nèi)容本身用不了多少時間，本質(zhì)上時間主要是消耗在了每次循環(huán)的比較語句上邊。

而事實上，比較語句是有很大優(yōu)化空間的，我們假設你要循環(huán)10000次，結(jié)果你從第一次開始就不斷的比較是否達到上界值，這是不是很徒勞呢？

我們寫一個達夫設備的函數(shù)用來測試執(zhí)行時間(參考網(wǎng)上資源，這個測試不難，不同測試會有不同效果，大家可以自行測試一下)：

int duff_device(int a)
{
    resigter x = 0;
    int n = (a) / 10;
    switch(a%10){
        case 0：do{ x++;
        case 9：x++; 
        case 8：x++;   
        case 7：x++;  
        case 6：x++;   
        case 5：x++;   
        case 4：x++;   
        case 3：x++;   
        case 2：x++;   
        case 1：x++;   
        }while(--n >0)
    }
    return x;
}

測試主函數(shù)如下

#include < Windows.h >
#define count 999999999
long int overtime = count;
int main()
{
    printf("over %d",duff_device(overtime));
    return 0;
}

執(zhí)行時間如下

現(xiàn)在我們看一下傳統(tǒng)的循環(huán)的執(zhí)行時間,其測試代碼如下：

int classical(int a)
{
    register x=0;
    do{
        x ++;
    }while(--a >0);
    return x;
}

測試主函數(shù)如下

#include < Windows.h >
#define count 999999999
long int overtime = count;
int main()
{
    printf("over %d",classical(overtime));
    return 0;
}

執(zhí)行時間如下

結(jié)果顯示達夫設備確實縮短了不少時間，這里x的定義是要用register關鍵字，這樣cpu就會把x盡可能存入cpu內(nèi)部的寄存器，新的cpu應該會有很通用寄存器使用。

值得一提的是，針對串行復制的需求，標準C語言庫提供了memcpy函數(shù)，而其效率不會比斯特勞斯魯普版的達夫設備低，并可能包含了針對特定架構(gòu)的優(yōu)化，從而進一步大幅提升執(zhí)行效率。

從不同角度看達夫設備

從語言的角度來看

我個人覺得這種寫法不是很值得我們借鑒。畢竟這不是符合我們“正常”邏輯的代碼，至少C/C++標準不會保證這樣的代碼一定不會出錯。

另外， 這種代碼冷知識，估計有很多人根本都沒見過，如果自己寫的代碼別人看不懂，估計會被罵的。

從算法的角度來看

我覺得達夫設備是個很高效、很值得我們?nèi)W習的東西。把一次消耗相對比較高的操作“分攤“到了多次消耗相對比較低的操作上面，就像vector中實現(xiàn)可變長度的數(shù)組的思想那樣，節(jié)省了大量的機器資源，也大大提高了程序的效率。這是值得我們?nèi)W習的。

總結(jié)

達夫設備能實現(xiàn)的優(yōu)化效果日趨在減弱，時代在變化，語言在發(fā)展，硬件設備在變化，編譯器性能優(yōu)化，除非特殊的需求下，一般還是沒必要做像這種層次的性能考量的。

不過，這種奇妙的 switch-case 寫法經(jīng)常研究一下還是很有樂趣的，你們覺得呢……