Re: [問題] 面試考題程式最佳化

看板C_and_CPP作者littleshan (我要加入劍道社!)時間13年前 (2011/06/14 16:32)推噓12(12推 0噓 15→)

留言27則, 19人參與討論串3/10 (看更多)

※ 引述《proach (pazroach)》之銘言： : ※ 引述《apey ()》之銘言： : : hi : : 以下是我今天面試所遇到的考題, 來這裡請教大家 : : a,b是 unsigned int : : 最佳化以下兩段程式碼 1 跟 2 : : 1.if ( (a/24) > b ) return 1; : : 2.a=(b/1024)*10; : 一般考這種題目，無非是想考你 << 與 >> 的用法。 : 很不幸得，對一些 CPU來說， >>1 與 >>2所需的 clocks數量不一樣多， : 可以看機械碼確認此事。 : 萬一這個 CPU有配備 single cycle multiplication and hardware divider， : 也許老實去用除法或乘法還比較快一些。同意這篇看法為了驗證 compiler 是否有能力進行最佳化我寫了如下的兩段 code int foo(unsigned int a, unsigned int b) { if( (a/24) > b) return 1; return 0; } unsigned int bar(int b) { return (b/1024)*10 } 使用 Visual C++ 以 /O2 選項 compile 後得到的 assembly 如下： _foo PROC mov eax, -1431655765 ; aaaaaaabH mul DWORD PTR _a$[esp-4] shr edx, 4 cmp DWORD PTR _b$[esp-4], edx sbb eax, eax neg eax ret 0 這邊應該會有很多人納悶，-1431655765 這東西是三小？為什麼要乘這個數？我們先來把它表示成二進位： -1431655765 = 10101010101010101010101010101011b 這數字非常地漂亮...看起來就像是循環小數一樣，而實際上也是： 0.666666...(十進位) = 0.10101010101010... (二進位) 而 mul 指令在計算過乘法後，會把高位的 32bit 存在 edx 因此做完這次乘法後，相當於 edx 擁有 a*(2/3) 的整數部份下面的 shr edx, 4 就很容易理解：把 edx 除以 16 所以 edx 的值會變成 a*(2/3) / 16 = a/24 底下應該就不用說明了注意 a/24 > b 不可以改成 a > b*24 或 a/8 > b*2+b 因為 b 在乘法運算後可能溢位，導致比較結果不正確 _bar PROC mov eax, DWORD PTR _b$[esp-4] shr eax, 10 ; 0000000aH lea eax, DWORD PTR [eax+eax*4] add eax, eax ret 0 (b/1024)*10 看起來就很簡單了第一個 shr 就是計算 b>>10 後面的 lea 則是利用 x86 的 address generation unit 把得到的結果乘五倍最後一行 add 把乘五倍的結果加上自己，相當於乘十倍 gcc 的 compile 結果除了在第二段 code 中改用兩次 lea 計算十倍以外其它地方則和 VC 大同小異結論：除非這家公司只能用特定平台的老舊 compiler，或是自己就在寫 compiler 否則他們的 code 可能充滿 << >> 之類的位元運算，不但沒比較快，還要小心莫名奇妙的 bug 建議原 po 仔細考慮一下再決定要不要去 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.15.163

推

ericinttu

06/14 17:37, , 1^F

06/14 17:37, 1^F

推

purpose

06/14 17:57, , 2^F

06/14 17:57, 2^F

推

ledia

06/14 18:34, , 3^F

06/14 18:34, 3^F