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

看板C_and_CPP (C/C++)作者cole945 (躂躂..)時間5年前 (2019/03/04 21:51)推噓23(23推 0噓 8→)

留言31則, 25人參與討論串2/2 (看更多)

※ 引述《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

03/04 21:58, 5年前 , 1^F

03/04 21:58, 1^F

→

djshen

03/04 22:30, 5年前 , 2^F

03/04 22:30, 2^F

推

IhateOGC

03/05 00:04, 5年前 , 3^F

03/05 00:04, 3^F