※ 引述《qazkevin (Linus)》之铭言： : 各位大大好， : 想请教各位一般在用for loop时， : 我们时常会在执行完一次loop後，将变数做i++ or i--， : 想请教各位该如何分析i++ & i--的效能谁比较快!? : 是否要将.c转成assembly去实际看做了些什麽!? : 恳请各位大大给我一点方向~ : Note: 不是i++ & ++i的效能比较 : -- :

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.161.140.38 : ※ 文章网址: https://webptt.com/cn.aspx?n=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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1551707468.A.F44.html