這是個有趣的問題..

網路上許多文章提到用 bitwise 可增進程式效能,例如:

k = i*2 ,可用 k = i<<1 取代; 而  k = i*8,可用 k=i<<3 取代,

手邊一些 topic 後來發現,這些「秘密」似乎不完全絕對,

也可能與 compiler 優化結果有所差異,也可能與 machine 本身處理有所差異。

這裡紀錄下吾人所實測之結果,以供日後備查之。

 

1. 測試環境與說明

AMD II X2 245 ,XP 作業系統, Visual C++ 2008

以下測試均以 Microsoft 提供之 QueryPerformance 系列函式測時,

測試次數為 UINT_MAX ,累計計時。

 

2. 位移運算子 (<<, >>)

位移運算子常用來做乘、除法之加速,若是拿來取代乘法、除法勢必較快;此次測試內容大致如下

unsigned i=1, j=1, bit, k=UINT_MAX;
for(bit=0; bit<32; ++bit){
    // start to timing
    while(--k) i+=j<<bit;
    // end to timing
}

 

不論是左移或右移,這裡出來的結果普遍性都是在 9.95 secs 上下 (也間接證實, shift operator 不論是移幾個 bits,都是花一樣的時間)。

 

3. 加法運算

加法運算之測時分較多細項進行測時,主要只有分 加二次、加四次、加八次,因這三個可以表示 *2, *4, *8,也就是說這三個都可以用位元運算子取代。結果如下表所示

 

express elaspe(msecs)
k+=j+j 9573.609216
k+=j+j+j+j 8466.982815
k+=j+j+j+j+j+j+j+j 12256.07109
k+=j+j+j+j+j+j+j+j+j+j+j+j+j+j+j+j 17922.53932

 看到結果讓人有點意外,j+j 執行一次加法與位元運算快一點 (這結果容易飄),但連加 4 次的 j+j+j+j 速度卻明顯比 shift operator 快!接下來再加 8 次、16 次就沒什麼特別,速度都明顯降下來。

於是又有一些疑惑產生:a. 若中繼放 register unsigned tmp,先將 j 加四次丟給 tmp,再將 tmp 加四次,出來結果會比 k=j << 4 還快嗎?  b. 連加三次呢?速度如何?

關於 a 的問題,答案是否定的。但這只是一次性測試, 若 j*16 這種運算式在程式碼中會寫到很多次,的確設個暫存變數去存下來會好些。其它的就看表說故事吧...

express elaspe(msecs)
k+=j+j+j 9388.825116
k+=j+j+j+j 8466.982815
k+=j+j+j+j+j 9020.37298
k+=j+j+j+j+j+j 12088.30899
k+=j+j+j+j+j+j+j 10723.34026
k+=j+j+j+j+j+j+j+j 12256.07109
k+=j+j+j+j+j+j+j+j+j+j+j+j+j+j+j+j 17929.79024
k+=tmp+tmp 18175.86956
k+=tmp+tmp+tmp+tmp 22103.66234

 

得到的結論是

(1) 用 shift 未必比加法來得快。

(2) 在進行 *5 之前 (如 *4 *3 *2) ,可考慮使用加法取代乘法與 shift operator。

edisonx 發表在 痞客邦 留言(2) 人氣()