Edison.X. Blog

這是個有趣的問題..

網路上許多文章提到用 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，也就是說這三個都可以用位元運算子取代。結果如下表所示

 看到結果讓人有點意外，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 這種運算式在程式碼中會寫到很多次，的確設個暫存變數去存下來會好些。其它的就看表說故事吧...

得到的結論是

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

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