Micro-Optimization-Myths

#cpp #performance #pattern

這篇在解決什麼

STL-Pitfalls 收的是「編得過但語意或複雜度是錯的」。這篇收的是另一種——寫法是對的，但你對它成本的直覺是錯的。

最常見的兩個誤判是一對的：

高估算術：以為 %、/ 很貴，於是換成 if 判斷加減法。
低估分支：以為 if 只是「比一下」，幾乎免費。

兩個誤判疊在一起，就會做出「用一個不可預測的分支去省一個根本不存在的除法」這種淨虧的交換。下面每條都附本機實測（12th Gen i5-12500H、g++ 14.3.0 -O2）。

先講結論的結論：在 LeetCode 的規模上，這篇講的東西全部量不到

題目給的 n 通常是 10⁴、10⁵ 量級，判題的雜訊遠大於這些差異。這篇的用途是校準直覺，不是拿來調效能。真正該用它的時機是：當你正打算「為了效能」把清楚的寫法改成不清楚的寫法時，先看一眼這裡，多半會發現不值得。

一、`/` 和 `%` 常常根本不是除法

除數是編譯期常數 → 編譯器改用 magic number

x % 10 不會編出除法指令。編譯器用的是「乘以 2ᴺ/10 的近似值再右移 N 位」這招：

int x;  return x % 10;

movsxd  rax, edi
mov     edx, edi
imul    rax, rax, 1717986919   ; ← 0x66666667 ≈ 2³⁴ / 10
sar     edx, 31                ; ┐ 負數補正
sar     rax, 34                ; │
sub     eax, edx               ; ┘
lea     edx, [rax+rax*4]       ; ┐ 由商回推餘數：x - (x/10)*10
mov     eax, edi               ; │
add     edx, edx               ; │
sub     eax, edx               ; ┘

一個乘法、幾個位移與加減，全程沒有分支。

signed 要為負數付補正費，unsigned 更短

上面那兩行 sar edx, 31 / sub eax, edx 是符號補正——因為 C++ 規定 -7 / 2 == -3（向零取整）而不是 -4，編譯器必須額外處理負數。換成 unsigned 就全部消失：

; unsigned x;  return x / 10;
mov  eax, edi
mov  edx, 3435973837
imul rax, rdx
shr  rax, 35            ; ← 沒有任何補正指令

連 `/ 2` 都不是單純的位移

這是最反直覺的一條。很多人相信「x / 2 就是 x >> 1」，對 signed 型別不成立：

; int x;  return x / 2;          ; unsigned x;  return x / 2;
mov eax, edi                     mov eax, edi
shr eax, 31    ; ┐ 補正           shr eax        ; ← 就這一條
add eax, edi   ; │
sar eax        ; ┘

x % 2 差更多：unsigned 是單一條 and eax, 1，signed 要五條（因為 -3 % 2 必須等於 -1，& 1 會給出 1）。

想手動「優化」成位移之前，先確認型別是 unsigned

把 x / 2 手寫成 x >> 1 在 signed 上不只是沒必要，還改變了語意（-7 >> 1 == -4，-7 / 2 == -3）。正確的做法是讓值的型別誠實地反映它非負的事實，然後把最佳化留給編譯器——它做得比手寫更完整。

除數來自執行期變數 → 這才是真的 `idiv`

; int f(int x, int d) { return x / d; }
mov  eax, edi
cdq
idiv esi          ; ← 真正的除法指令

這才是那個「除法很貴」的都市傳說的來源。

成本一覽（每次操作，2²⁴ 筆資料取平均）

  常數 % 10  (unsigned)      0.408 ns
  常數 / 2   (unsigned)      0.368 ns
  常數 / 2   (signed)        0.401 ns
  常數 % 10  (signed)        0.680 ns
  常數 / 10  (signed)        0.760 ns
  執行期 % d (idiv)          1.394 ns
  執行期 / d (idiv)          2.009 ns

常數除法比真除法快 2–5 倍，而且彼此之間的差距都在 1 ns 以內。記住這個尺度，下一節要拿它跟分支比。

二、真正貴的是「猜不到的分支」

分支本身不貴，猜錯才貴。現代 CPU 是深管線的，預測錯要把已經開始執行的十幾層指令全部丟掉重來。所以同一個 if，成本完全取決於它好不好猜。

成本隨成立機率呈倒 U 型

同一段程式（if (v[i]) acc += 3; else acc += 7;）與其無分支等價版（acc += 7 - 4 * v[i]）對比，只改變 v[i] 為真的機率：

  成立機率    有分支      無分支      分支多付
      0%     0.405 ns   0.359 ns    +0.046 ns
      1%     0.427 ns   0.324 ns    +0.103 ns
      5%     0.839 ns   0.348 ns    +0.491 ns
     25%     2.424 ns   0.336 ns    +2.088 ns
     45%     3.222 ns   0.277 ns    +2.945 ns   ← 最慘
     50%     3.242 ns   0.344 ns    +2.898 ns   ← 最慘
     75%     2.423 ns   0.304 ns    +2.119 ns
     99%     0.433 ns   0.338 ns    +0.095 ns
    100%     0.397 ns   0.340 ns    +0.057 ns

一個五五波的分支比一次真除法還貴

對照上一節：不可預測的分支多付約 2.9 ns，而執行期除數的 idiv 只要 1.4–2.0 ns，常數 % 10 更只要 0.68 ns。也就是說「用 if 換掉 %」在最壞情況下是拿 2.9 ns 去省 0.68 ns，淨虧四倍。
反過來，機率壓到 1% 以下或 99% 以上時分支幾乎免費——這就是為什麼「快速路徑 + 罕見的慢速路徑」是好模式，而「五五波的資料相依判斷」是壞模式。

判斷一個分支好不好猜

問「它的結果跟前幾次有沒有關聯」：

好猜：迴圈邊界（每輪都成立，只有最後一次不成立）、參數檢查、nullptr 檢查、錯誤處理——結果幾乎恆定。
難猜：對隨機資料的比較。經典例子是未排序陣列上的 if (v[i] > threshold)，以及本篇的起點：兩個隨機位數相加會不會進位（機率恰好 45/100，正中最慘區）。

怎麼把分支變不見

讓兩個分支都變成「算一個值」，不要各自帶副作用：

// 有分支：兩邊各自做一件事，編譯器很難合併
if (sum >= 10) { out.push_back(sum - 10); carry = 1; }
else           { out.push_back(sum);      carry = 0; }

// 無分支：先算好值，動作只寫一次 → 編譯器發 setg + cmovle
carry = sum >= 10;
out.push_back(sum - 10 * carry);

副作用寫兩次，等於把分支釘死

上面「有分支」版之所以難救，關鍵在 push_back 在兩個分支各寫了一次。編譯器沒辦法把兩個不同的副作用用 cmov 合併，只好保留跳躍。就算你要用 if，也該先算好值、再統一執行動作——這樣至少給了編譯器把分支消掉的機會。

這也表示上面那張表的數字是「刻意留住分支」量出來的

為了測到分支本身的成本，我加了 -fno-if-conversion -fno-if-conversion2，否則 GCC 會自己把那個簡單的 if/else 轉成無分支形式。這反過來說明了一件更重要的事：兩邊都便宜又沒有副作用時，編譯器多半已經幫你消掉分支了，手動去「優化」它純屬白工。

三、合起來看：0002-Add-Two-Numbers 的現場

直式加法的每一位要做「取這位的值、算進位」。兩種寫法：

if (sum >= 10) { ... sum - 10 ...; carry = 1; } else { ...; carry = 0; }   // 分支減法
carry = sum / 10;  ... sum % 10 ...                                        // divmod
carry = sum >= 10; ... sum - 10 * carry ...                                // 無分支減法

純算術迴圈實測（20000 組 × 100 位）：

  分支減法      9.77 ms      ← 「省下除法」的那個
  divmod        4.25 ms      −56%
  無分支減法     3.03 ms      −69%

想省除法的寫法慢了一倍以上，因為省下的除法本來就不存在，而換來的分支正好落在 45% 的最慘區。

但在完整解法裡，這三者其實分不出勝負

加回 new ListNode(...) 之後，allocator 與指標追逐主導一切——算術大約只佔總時間三成，我連續兩次量到的差距分別是 −5% 和 −30%，雜訊比訊號大。方向一致（divmod 不會輸），但幅度不可信，所以我不會宣稱一個精確數字。
這正是本篇的重點：真正該關心的是配置與記憶體存取，不是那幾個 cycle 的算術。

四、怎麼自己驗證

看編譯器到底發了什麼指令

g++ -std=c++20 -O2 -S -masm=intel -o - x.cpp | less

把可疑的算式包成一個小函式再看，比在整包程式裡找容易得多。找 idiv 就知道有沒有真除法，找 j+條件碼（jle、jne…）就知道分支有沒有被消掉，找 cmov／set 就知道被消掉了。

量時間

用 volatile 或把結果累加進 volatile 變數，避免整段迴圈被最佳化掉。
資料量要大到蓋過計時器誤差（上面用 2²⁴）。
同一組數字至少跑兩次。差異在 10% 以內的結論，多半是雜訊。

`perf`（如果權限允許）

perf stat -e branches,branch-misses ./a.out

能直接看到誤預測率，是分支問題最直接的證據。但很多發行版預設把硬體計數器鎖住，會得到 No supported events found；要 root 調 /proc/sys/kernel/perf_event_paranoid（設為 1 或更低）才開得起來。沒權限時就退回計時法。

五、判斷法則

動手「優化」算術之前，依序問：

除數／模數是編譯期常數嗎？ 是的話它已經不是除法了，別動它。
我是不是在用一個分支換掉一個算術運算？ 那個分支好猜嗎？五五波的話這筆交易穩虧。
兩個分支是不是各帶一次副作用？ 先算值、再統一動作，讓編譯器有機會消掉分支。
型別該是 unsigned 嗎？ 非負的值宣告成 unsigned，符號補正的指令自動消失——比手寫位移安全也更有效。
算術真的是瓶頸嗎？ 有 new／malloc／指標追逐在場的話，答案幾乎永遠是「不是」。

問不出來就照第四節去量，別憑感覺改。

0002-Add-Two-Numbers — 本篇的起點：進位用 divmod 還是 if (sum >= 10)，兩個誤判在同一行相遇
0067-Add-Binary — 同一個 carry 迴圈換成 base 2，正好示範 divmod 版換進位制零成本、減法版要重寫
0043-Multiply-Strings — carry 可以大到 8，- 10 那套徹底失效，只能用 divmod
0007-Reverse-Integer — 整題就是反覆 % 10 與 / 10，而且必須處理負數，正是 signed 補正的現場
0136-Single-Number — 位元運算取代條件判斷的極端範例，XOR 全程無分支
0338-Counting-Bits — i >> 1 與 i & 1 用在 unsigned 語意上，對照本篇「別對 signed 手寫位移」
STL-Pitfalls — 姊妹篇。那篇是「編得過但錯」，這篇是「對，但成本跟你想的不一樣」