這是個有趣的問題..

網路上許多文章提到用 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 發表在 痞客邦 PIXNET 留言(2) 人氣()


留言列表 (2)

發表留言
  • novus
  • 假如你不了解編譯器的特性又不會分析組合語言,做這類的實驗常常白費時間,不如去看電視算了。

    在大多數編譯最佳化之下,這裡的一長串連加最後都會用乘或位移的組合取代,你應該也注意到了,時間的成長和+號的數量並沒有比例關係。

    這樣的實驗沒意義的原因在於
    1. 你沒辦法確知編譯器選擇指令的演算法,你這次做起來是這樣,在其他的應用場合可能會跑出不同的結果,更不用說不同編譯器可能有不同的指令選擇策略。

    2. 在真實世界當中,影響效能的因素除了指令本身的成本之外,暫存器排擠和 pipeline 相依性也會造成影響。你很難保證把同樣的程式碼塞到不同上下文之後所有的特性皆不變。


    附帶一提,register 關鍵字是為了二三十年前的編譯技術而設,現在的編譯器純粹只是保留做為向前相容而已,不會真的為了這個關鍵字多為你考慮什麼,現在的編譯器都會主動利用register。
  • 現代編譯器對 register 之功用確實不知道,這點感謝您的提醒。 本文會做此試驗,純是來源於篩法之一小段碼 for(i=k*k; i<=end; i+=k+k) 與 for(i=k*k; i<=end; i+=k<<1) 編出來之速度有所異,故做此測時。

    最後感謝您願撥冗給予意見,感激不盡!

    edisonx 於 2011/05/15 16:10 回覆

  • wily
  • 請教大大們, 編譯器編譯的那種程序要如何才能看的到? 就是那些組合語言. 感激不盡!
  • 你所使用的 compiler 為何?

    edisonx 於 2011/12/13 14:32 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼