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

[littleshan (我要加入劍道社!)]

※ 引述《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:可能是測試 想法/觀念/多一個選擇的路.
推 purpose:聽過 lea 做乘法比較快，但從來都不懂原理...
推 ledia:硬要用 bit shift 來作, 通常都不會比較快
→ ledia:如果考題改成, 降低以下程式碼的可讀性, 那應該就沒問題了XD
→ suhorng:也許因為lea是加、位移，所以比mul快
→ DrStein:數據相依性太重 整個亂序運行引擎都廢掉 失敗..
→ WPC001:中肯推,除非是開發compiler或是CPU, 否則還是丟給compiler
推 holymars:...原來學長你今天在紙上算的那些神祕符號是這個...
→ ericwang1017:結論太偏激，how about 8051 ?
→ yoco315:樓上 那不就是老舊 compiler 嗎...
→ yoco315:如果是直接 asm 那根本跟編譯氣沒關係啦.. 不覺得偏激 @@
推 VictorTom:推~~雖然變乘5倍那個還沒搞懂是怎麼回事....Orz
→ ericwang1017:8051是MCU,不是compiler..
→ ericwang1017:且51的compiler有的也不老舊..
→ littleshan:沒辦法把a/1024轉成a>>10的compiler也只能用老舊形容
推 loveme00835:XD
推 ericinttu:  XD
→ firejox:    XD
→ akasan:     XD
推 xatier:     XD
→ tinlans:每次看到這種考題，就在想這些出題者把做 compiler 的人的
→ tinlans:心血看成什麼了...
推 Domos:推 做compiler的人看到這種題目會哭笑不得
推 xatier:推tinlans大觀點
→ VictorTom:推XD
推 angleevil:應該是硬體公司才搞得鬼
推 flylover:XD