Re: [問題] 關於i++ & i--的執行效能

[cole945 (躂躂..)]

※ 引述《qazkevin (Linus)》之銘言：
: 各位大大好，
: 想請教各位一般在用for loop時，
: 我們時常會在執行完一次loop後，將變數做i++ or i--，
: 想請教各位該如何分析i++ & i--的效能誰比較快!?
: 是否要將.c轉成assembly去實際看做了些什麼!?
: 懇請各位大大給我一點方向~
: Note: 不是i++ & ++i的效能比較
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.140.38
: ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1551452231.A.CDC.html
: 推 jerryh001: 就加法器的原理來說應該一樣快？                       03/01 23:0
: 面試時被問這個問題，答案不是一樣快唷

  不知道你有沒有修過計算機組識與結構, 熟讀過算盤本..
  不然這個問題你看完組語也不會能得到什麼 @@

  從 CPU 怎麼做加減法來看, 兩個是一樣的東西,
  一般 general purpose cpu 很難 add 和 sub 的效能不同,
  何況通常 i++ 是     add r0, r1, 1 的話,
  那       i-- 不過是 add r0, r1, -1
  很難有什麼決定性的差別

: → AndCycle: 只能看編譯結果,開最佳化通常都會幫你做掉,輪不到你想    03/02 00:3
: 因為面試時被問，所以想知道這個分析這個效能

  不看最佳化的效能沒有意義, 因為 -O0 就不是考量效能,
  比較好的寫法在 -O0 反而跑出比較差的結果司空見慣
  而且前面也說了, 加減法本一體, i++/i-- 不會有顯然的差異,
  如果你說在 loop 的效能的話, 倒是常聽過一個都市傳說是

  用 i-- 比較快, 因為可以用 conditional branch on zero (cbz)      ; 若 0 跳
                         或 conditional branch on non-zero (cbnz) ; 若非 0 跳
  例如一個 loop

  for (i = 0; i != n; i++) 可以變成       | while (n--) { ... }
  .LOOP:                                  | .LOOP:
     add   r0, r0, 1                      |
     cmp   r0, r1                         |    add  r1, r1, -1
     bne   .LOOP                          |    cbnz r1, .LOOP
  # 假設 r0 是 i, r1 是 n
  # pseudo 指令集, 都簡單英文應該看得懂?

  先說結論, 都講是都市傳說了, 表示這是錯誤的迷思..
  而且還蠻常看到有人故意把程式寫成這樣為了用出 cbnz
  有幾個原因
  1. 現在很多指令集會有 register 的 conditional branch,
     例如 bne r0, r1, .LOOP
  2. 就算不支援 (1) 的做法, 若 CPU 可以 multi-issue (同時執行多指令)
     多出來的 cmp 很容易被隱藏起來
  3. (1)和(2)其實很沒說服力, 最重要的是, compiler 在編譯時,
     會考慮整個 loop 的語意來做最佳化, 不會照本宣科的翻譯.
     通常這樣子的 loop 會有其他東西, 最佳化後 n--, i++ 搞不好就消失了,
     硬要產生 cbnz n-- 其實效率更差

  例如看這段 code:
    int foo (int *p, int n) {
      int sum = 0;
      for (int i = 0 ; i != n; i++)
        sum += p[i];
      return sum;
    }

    int bar (int *p, int n) {
      int sum = 0;
      while (n--) {
        sum += *p++;
      }
      return sum;
    }

  這兩段程式碼, 一個用 i++, 另一用 n--
  兩個 function 在我手邊的 gcc-7.3 會生出一模一樣的結果,
  以 aarch64 為例

  add     x3, x3, x1, uxtw 2  ; end = p + (n << 2)
  .L3:
       ldr     w1, [x2], 4    ; load *p => w1,   p += 4
       add     w0, w0, w1     ; sum += w1
       cmp     x2, x3         ; compare p, end
       bne     .L3            ; loop 如果 p != end
  整個 loop 根本不會產生 i++ 或 n--

  用 C 來達表, 整個 function 像是被改寫成
  int lala (int *p, int n) {
    int sum = 0;
    int *end = p + n;
    if (n) {
      do {
        sum += *p++;
     while (p != end);
    }
    return sum;
  }

  這是 compiler 中蠻重要的是一個 optimization
  在 GCC 叫 Induction Variable Optimization (ivopt)
  在 LLVM 叫 Loop Strength Reduction
  我覺得 GCC 的講法比較貼切 (這也是其中一個 GCC 做的遠比LLVM好的)

  在 loop 中, 會有不同指令使用不同 induction variable (以下簡稱 IV)
  例如 p[i] 可以表達成  {p, +, 4}
       i++ 則是         {0, +, 1}
       n--的話會是      {n, +, -1}
                        {初值, 操作, step)
  使用這些 IV 的指令像是
       load 本身 (load *p)
  或是 compare   (i != n, n != 0 或 p != end)

  1. 而每個 IV 有維護的成本,
     例如 i = i + 1    =>  add   r0, r0, 1
     但對支援 post modification load 的指令集,
     *p++ 可以一次做到 load 或與 update p, 兩個願望一次滿足
     像 aarch64 的  ldr  w0, [x2], 4
     意思是  w0 = load x2
         又  x2 = x2 + 4
     在那 aarch64, 用 p++ 比 i++ 還划算

  2. 而每一個使用 IV 的人也有不同的成本
     例如 load p[i] 其實是對   p + (i << 2) 存取 (假設 4-byte)
     對支援 indexed load 的指令集, 例如 aarch64 可以做到
     ldr  w0, [x1, x2, sxtw 2]   ;  w0 = load x1 + (x2 << 2)
                                 ;  x1 是 base p, x2 是 index i
     但對不支援的指令集要分成兩道以上, 例如 riscv-v
     sll     a1,a1,2
     add     a1,a0,a1
     lw      a0,0(a1)
     對 aarch64 的 load 來說, 使用 i++ 不虧,
     但對 risc-v 就不用

  3. 每一個 IV 或 loop invariant 都會佔用 register, 導致 register 壓力

  經過一個 cost-model 計算所後, (理論上要嘗試所有 IV 的 subset),
  以這個例子, compiler 會知道只使用 {p, +, 4} 一個 IV 給 load 和 compare 用,
  能得到整體最佳解, 若 compare 使用 n-- 反而變差

: → EricTCartman: 你自己不就說要從assembly看了嗎@@                  03/02 10:2
: → EricTCartman: 之前板上有人做過實驗 編譯器最後結果是一樣快       03/02 10:2
: → EricTCartman: 產生的assembly一樣 而且80:20法則 通常系統真正有   03/02 10:2
: → EricTCartman: 效能問題的不會在這種地方                          03/02 10:2
: 感謝大大，我只是猜測分析組語，畢竟我對組語不熟，所以才發文想知道怎麼分析
: 推 FRAXIS: https://godbolt.org/ 用這個看 assembly                  03/02 11:4
: 推 FRAXIS: 然後用 linux perf 去看該 instruction 到底花多少時間     03/02 11:5
: → FRAXIS: 還可以用 pmu tool 看一下到底是卡在 CPU 的哪部分         03/02 11:5
: 感謝大大
  如果你要看到指令層級的東西, 其實一般 perf 不太夠用,
  因為 sample base 易受系統其他程式搶 CPU 影響, 會浮動很大,
  可能要找 cycle-accurate 的 profiler 來看
  另外, 只看組語不夠, 你還是不能知道效能, 你需要特定 CPU 的 pipeline 資料
  同相指令在不同 CPU 實作 (micro-architecture, pipeline) 下會有不同結果,
  (例如 i7, i5, i3 或是不同代的差異)
  指令少但 latency 長, 結果還是比較慢.
  指令多也不一定慢, 在 multi-issue 時平行執行.
  另外還有 data cache miss, branch prediction 的問題, 甚致不是靜態可以看出來的
  沒有 pipeline 的資料, 組語是看不出效能的

: 推 CoNsTaR: 推樓上那網站，學組語相關好用                           03/03 10:5
: 感謝大大
: 推 johnjohnlin: 開 optimize 的時候沒差，但是沒有開兩個差很多       03/03 17:1
: → johnjohnlin: PS 是 C++ iterator 的情況                          03/03 17:1
: → johnjohnlin: 所以我都習慣寫 ++i                                 03/03 17:1
: ※ 編輯: qazkevin (1.161.140.38), 03/03/2019 17:26:49
: 推 cole945: 幫幫大家, 哪一公司部門講出來 XD                        03/04 10:3
: 推 suhorng: 難道是想要問說迴圈倒著跑每次會少一個 cmp 嗎...         03/04 11:3
  有些面試的人其實自已也一知半解..
  幫幫忙講一下哪家公司什麼部門問的, 也算是回饋板友
  嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.135.119
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1551707468.A.F44.html
推 james732: 推
→ djshen: 請問vectorization和loop unroll對效能影響有研究嗎?
推 IhateOGC: leetcode沒優化++i ，這個是考試專用，i--會比較快
→ IhateOGC: 水分到底大部分在大腸吸收還是小腸呢?
→ IhateOGC: 類似這問題
→ IhateOGC: 沒想到版大好認真回
推 TitanEric: 優文
推 bben900911: 感謝優文
推 FRAXIS: 我聽到的說法是 cbnz 的執行檔會小一點點點
→ FRAXIS: 所以在非常非常少的情況下可以減少 i-cache miss
→ cole945: 就拿上面的例子, 改用cbnz, 多一道add, 怎麼會比較小呢?
→ cole945: 用cbnz可能好, 也可能不好, 重點是compiler會幫你算..
→ cole945: 寫while(n--)不保證會生出cbnz
推 xvid: 推
推 LiloHuang: 推
推 adrianshum: 推高質素回應
推 ray2501: 推
推 cutekid: 大推(Y)
推 lc85301: 認真推
推 g5637128: 推
推 Caesar08: 推
推 bill1992: 猛  推一個再仔細看
推 genius945: 推 清楚明瞭
推 newup: 推 真的是優文
推 tommycc: 推
推 chchwy: 神
推 hyun1313: 推
推 christianSK: 強者我朋友 幫推
推 VictorTom: 推:)
推 kindaichitom: push
推 RishYang: 我也想知道哪家公司