用 C++ 追求效能（進階）：移動語意、分支預測與 SIMD 的常數因子之戰

為什麼你的迴圈明明是 O(n)，換個寫法卻快了三倍？

你已經讀過入門篇，知道 C++ 快在編譯、值語意與快取友善。於是你信心滿滿地寫了一段加總程式，開了 -O2，結果發現一件怪事：把資料先排序再跑同一個迴圈，竟然比不排序快了好幾倍——而排序本身還多花了時間。演算法複雜度沒變、資料量沒變、編譯器旗標沒變，怎麼會這樣？

答案藏在 CPU 內部一個入門篇沒談的機制：分支預測（branch prediction）。現代處理器不是乖乖地一條指令做完再做下一條，它在猜你接下來會走哪條路、會用哪塊資料，並提前動工。當它猜對，速度飛快；當它猜錯，前面白做的工全部作廢。排序後的資料讓 if 的結果變得「可預測」，CPU 幾乎不再猜錯，於是同一個迴圈就快了。

這篇進階文章假設你已經理解快取列與值語意，要往更深一層走：當大 $O$ 與快取都調好之後，剩下的常數因子藏在哪裡？ 我們會談移動語意如何消滅多餘複製、分支預測與無分支寫法、SIMD 向量化的真實面貌、指標別名（aliasing）如何偷走你的效能，以及——也許最重要的——如何正確地測量，才不會被自己的基準測試騙了。

移動語意：別再複製那些注定要丟掉的資料

入門篇讚揚值語意：Point b = a; 真的把資料複製一份，互不干擾。這很安全，但有個代價——當被複製的來源馬上就要被丟掉時，那次複製是純粹的浪費。

考慮這段函式回傳一個大 vector：

std::vector<int> make_data() {
    std::vector<int> v(10'000'000, 7);
    return v;   // v 是個區域變數，回傳後它就消失了
}

int main() {
    std::vector<int> result = make_data();  // 真的會把一千萬個 int 複製一份嗎？
}

直覺上，return v 似乎要把一千萬個整數從 make_data 的 v 複製到 main 的 result，然後 v 被銷毀。複製完又銷毀，這 4000 萬位元組的搬運完全是白做工。

C++11 引入的移動語意（move semantics）解決了這件事。vector 內部其實只有三個小東西：一個指向堆積資料的指標、一個 size、一個 capacity。「移動」不搬那一千萬個整數，而是把這三個小欄位的「所有權」轉交給目的地，再把來源的指標設成 nullptr——整個動作只是幾個指標的交換，$O(1)$，與資料量無關。

#include <vector>
#include <utility>

int main() {
    std::vector<int> a(10'000'000, 7);
    std::vector<int> b = std::move(a);  // 把 a 的內臟「移交」給 b，不複製資料
    // 此後 a 處於有效但未指定的狀態（通常為空），b 接管了那塊堆積記憶體
    return b.size();  // 10000000
}

std::move 並不真的「移動」任何東西——它只是把 a 轉型成一個「右值參考（rvalue reference）」，告訴編譯器「a 接下來可以被掏空，請呼叫移動建構子而非複製建構子」。

看一個例子：複製 vs 移動的代價差距

下面對照同一個大字串，分別用複製與移動塞進 vector：

#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <utility>

int main() {
    const int N = 200'000;
    std::string big(1000, 'x');  // 每個一千字元

    // 情境一：每次都複製
    {
        std::vector<std::string> v;
        auto t0 = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < N; ++i) {
            std::string tmp = big;     // 複製來源
            v.push_back(tmp);          // 又複製進 vector
        }
        auto t1 = std::chrono::high_resolution_clock::now();
        std::cout << "複製: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count()
                  << " ms\n";
    }

    // 情境二：把暫存字串移動進去
    {
        std::vector<std::string> v;
        auto t0 = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < N; ++i) {
            std::string tmp = big;        // 這次複製不可避免（big 還要用）
            v.push_back(std::move(tmp));  // 但進 vector 時用移動，省一次深複製
        }
        auto t1 = std::chrono::high_resolution_clock::now();
        std::cout << "移動: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count()
                  << " ms\n";
    }
    return 0;
}
// 輸出（數字依機器而定，趨勢一致）：
// 複製: 95 ms
// 移動: 52 ms

差別在於 push_back(std::move(tmp)) 省下了把一千字元再深複製一次的成本。

但這裡有個更深刻的轉折：對於 make_data 那個回傳區域變數的例子，現代編譯器連移動都不做——它直接套用 複製省略（copy elision），特別是具名回傳值最佳化（NRVO, Named Return Value Optimization）。編譯器讓 make_data 裡的 v 一開始就建在 main 的 result 該在的位置，根本沒有第二份物件，也就沒有任何複製或移動。C++17 起，對於回傳「純右值（prvalue）」如 return std::vector<int>(...) 的情形，這種省略是強制保證的。

所以慣用法的結論很反直覺：回傳大物件時，直接 return v; 就好，不要寫成 return std::move(v);——後者反而會妨礙 NRVO，逼編譯器退回去做移動，畫蛇添足。

分支預測：CPU 是個會賭博的處理器

回到開頭那個「排序後變快」的謎題。現代 CPU 採用管線（pipeline）：把一條指令拆成取指、解碼、執行、寫回等多個階段，像工廠流水線一樣讓多條指令重疊進行。問題來了——遇到 if 時，CPU 還沒算出條件結果，卻不能讓流水線空轉等待，於是它猜一個方向先做下去。

猜對了，流水線滿載，效率極高。猜錯了，已經投機執行的那些指令必須全部清空（pipeline flush），重新從正確的分支開始。一次預測失誤（branch misprediction）的代價，在現代處理器上約是 15 到 20 個時脈週期——相當於十幾條指令的時間憑空蒸發。

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

int main() {
    const int N = 30'000'000;
    std::vector<int> data(N);
    for (int i = 0; i < N; ++i) data[i] = std::rand() % 256;

    // 是否排序，是這個實驗唯一的變因
    // std::sort(data.begin(), data.end());  // 試試把這行註解掉再打開

    auto t0 = std::chrono::high_resolution_clock::now();
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        if (data[i] >= 128) {   // 這個分支會被預測
            sum += data[i];
        }
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    std::cout << "sum=" << sum << "  "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count()
              << " ms\n";
    return 0;
}

未排序時，data[i] >= 128 的結果是隨機的，CPU 約有一半機率猜錯，流水線不斷被清空。排序後，前半段全部小於 128（一路猜「不進入」）、後半段全部大於等於 128（一路猜「進入」），預測器幾乎全中。實測下，排序版的迴圈本體常快上 3 到 6 倍——即使你把排序的時間也算進去，對重複掃描多次的場景仍然划算。

動手算一下：無分支（branchless）的代價模型

既然預測失誤這麼貴，能不能乾脆消除分支？把上面的條件累加改寫成不含 if 的算術：

// 有分支版本
if (data[i] >= 128) sum += data[i];

// 無分支版本：用比較結果（0 或 1）當作遮罩
sum += data[i] * (data[i] >= 128);

(data[i] >= 128) 在 C++ 中產生 0 或 1，乘上去等於「條件成立才加」。這段沒有跳轉，CPU 不需要預測，每次都做固定的乘加，執行時間穩定。

我們用一個簡化模型估算何時該無分支化。設迴圈每次迭代的基礎成本為 $c$ 個週期，分支預測失誤率為 $p$，每次失誤額外付 $m \approx 18$ 個週期：

$$ T_{\text{有分支}} \approx c + p \cdot m, \qquad T_{\text{無分支}} \approx c + k $$

其中 $k$ 是無分支版本多出的固定算術成本（通常 $1\sim2$ 週期）。當資料隨機、$p \approx 0.5$ 時，$p \cdot m \approx 9$ 週期，遠大於 $k$，無分支大勝。但當分支高度可預測（$p \approx 0.01$）時，$p \cdot m \approx 0.18$，反而比 $k$ 還小——這時保留分支更快。

結論：無分支不是萬靈丹。它在「資料隨機、難以預測」時才划算；對於高度規律的分支，硬要無分支化反而拖慢。這也是為什麼盲目套用「優化技巧」很危險——你得先知道真實的預測失誤率，而那要靠 profiler（如 perf stat 的 branch-misses 計數）量出來，不能靠猜。

SIMD：一條指令算八個數

入門篇提過 -O2 會做「自動向量化」，但只是一筆帶過。這裡把它攤開。SIMD 是 Single Instruction, Multiple Data 的縮寫——CPU 有一組寬暫存器（如 AVX2 的 256 位元），一條指令就能對 8 個 32 位元浮點數同時做加法，而不是一個一個算。

理想情況下，編譯器會自動把你的純量迴圈轉成 SIMD 版本：

// 你寫的是樸素的逐元素相加
void add_arrays(const float* a, const float* b, float* out, int n) {
    for (int i = 0; i < n; ++i) {
        out[i] = a[i] + b[i];
    }
}
// 在 -O3 -march=native 下，編譯器可能把它向量化成
// 每次迭代用一條 AVX 指令處理 8 個 float

但自動向量化很脆弱，下列任何一項都可能讓編譯器放棄：迴圈內有分支、有函式呼叫（未內聯）、迭代之間有資料相依、迴圈次數編譯期未知、以及——下一節要談的——指標別名疑慮。當自動失敗，你可以用 intrinsics 手動寫 SIMD：

#include <immintrin.h>  // AVX intrinsics

void add_arrays_avx(const float* a, const float* b, float* out, int n) {
    int i = 0;
    for (; i + 8 <= n; i += 8) {
        __m256 va = _mm256_loadu_ps(a + i);   // 載入 8 個 float
        __m256 vb = _mm256_loadu_ps(b + i);
        __m256 vs = _mm256_add_ps(va, vb);    // 一條指令做 8 個加法
        _mm256_storeu_ps(out + i, vs);
    }
    for (; i < n; ++i) out[i] = a[i] + b[i];  // 處理剩餘不足 8 個的尾巴
}

手寫 intrinsics 換來掌控力，但代價是可讀性與可攜性（AVX 只在 x86，ARM 用的是 NEON）。實務上的順序通常是：先讓編譯器自動向量化，用 -march=native 開啟目標 CPU 的指令集，看反組譯確認有沒有用到向量指令；只有在熱點且自動失敗時，才手寫 intrinsics。要注意 -march=native 編出來的執行檔綁定當前 CPU，換到不支援 AVX 的機器會直接當掉。

指標別名：編譯器不敢做的最佳化

這是入門篇完全沒碰、卻常常是「為什麼向量化失敗」的真兇。看這個無辜的函式：

void scale(float* out, const float* in, float factor, int n) {
    for (int i = 0; i < n; ++i) {
        out[i] = in[i] * factor;
    }
}

你覺得編譯器能放心向量化它嗎？不行。因為編譯器無法排除一種可能：out 和 in 指向同一塊（或重疊的）記憶體。如果 out == in + 1，那麼寫入 out[i] 會改到還沒讀的 in[i+1]，逐元素循序執行和八個一起平行執行的結果就會不同。這種「兩個指標可能指向同一塊記憶體」的疑慮叫做指標別名（pointer aliasing）。編譯器秉持「彷彿」規則，寧可保守不向量化，也不能算錯。

要解除這個顧慮，可以用編譯器擴充關鍵字 __restrict（C99 的 restrict 在 C++ 中以 __restrict__ / __restrict 提供），向編譯器承諾「這些指標不會別名」：

void scale(float* __restrict out, const float* __restrict in, float factor, int n) {
    for (int i = 0; i < n; ++i) {
        out[i] = in[i] * factor;  // 現在編譯器敢放心向量化了
    }
}

這也順帶解釋了一個常見現象：為什麼同樣的數值迴圈，Fortran 常被認為比 C++ 快？ 因為 Fortran 的語言規則預設陣列參數不別名，編譯器一開始就能做最激進的最佳化；而 C/C++ 預設指標可能別名，必須由你用 restrict 明確開綠燈。語意上的這一點差異，決定了編譯器敢不敢放手。

警告：__restrict 是你對編譯器的承諾，不是檢查。如果你騙了它——傳進去的指標其實重疊——行為是未定義的（undefined behavior），程式可能算出垃圾還不報錯。只有在你百分百確定不重疊時才用。

你以為你在測效能，其實你在測編譯器的幽默感

寫到這裡，所有技巧都指向同一個前提：你得能正確測量。但微基準測試（microbenchmark）滿地是坑，最經典的一個是——編譯器發現你的計算結果根本沒被使用，就把整段程式碼刪掉了。

// 一個看似在測「一百萬次平方根」的基準
auto t0 = clock();
double x = 0;
for (int i = 0; i < 1'000'000; ++i) {
    x = std::sqrt(i);   // x 每次被覆寫，最後也沒人用
}
auto t1 = clock();
// -O2 下，編譯器發現 x 的值無關緊要，可能把整個迴圈消除
// 你量到的「耗時」接近 0，於是你高興地宣稱 sqrt 免費——大錯特錯

這就是死碼消除（dead code elimination）在搗蛋。防止的辦法是讓結果「逃逸」，使編譯器無法證明它沒用：把結果累加後印出來、寫進 volatile 變數，或用專業基準框架（如 Google Benchmark 的 benchmark::DoNotOptimize）。

正確測量還有幾條鐵律：

• 永遠開最佳化測（-O2 或 -O3）。-O0 的數字毫無參考價值，這點入門篇已強調。
• 先暖機（warm-up）：第一次跑會把指令與資料載入快取、觸發 CPU 升頻，量第一次往往偏慢。
• 多次取統計量：CPU 有渦輪升頻、作業系統會搶排程、其他程式在競爭快取，單次數字噪音很大。取中位數比平均值穩健，並回報變異。
• 小心測到「快取已熱」的假象：如果你重複跑同一份小資料，第二次起資料全在 L1，測出來的速度在真實情境（冷資料）下根本達不到。

一句話：沒有量測就沒有最佳化。你對效能的直覺，包括本文教你的每個技巧，都必須用嚴謹的數字驗證——否則你可能花一整天「優化」了一段對整體耗時毫無影響的程式，這就是過早優化最常見的悲劇。

重點回顧

• 移動語意把「即將銷毀的物件」的資源所有權 $O(1)$ 轉交，消滅多餘的深複製；但回傳區域變數時直接 return v;，讓編譯器做複製省略（NRVO），別自作聰明加 std::move。
• 分支預測失誤約付出 15～20 個時脈週期。資料可預測（如已排序）時分支很便宜；資料隨機時，無分支寫法可能更快——但要靠實測的失誤率決定，不能盲套。
• SIMD 向量化讓一條指令處理多筆資料；優先靠 -O3 -march=native 自動向量化，熱點且自動失敗時才手寫 intrinsics，並注意指令集可攜性。
• 指標別名是向量化最常見的隱形殺手；__restrict 能向編譯器承諾不重疊以解鎖最佳化，但承諾錯了就是未定義行為。
• 微基準測試陷阱：死碼消除、未暖機、單次量測、快取假象都會騙你。先量測、取統計、防止結果被優化掉，才談得上最佳化。

深入探討（研究所視角）

機器層級的平行：ILP、亂序執行與 Roofline 模型

本文的分支預測與 SIMD，其實都是 CPU 榨取指令層級平行（Instruction-Level Parallelism, ILP）的手段。現代亂序（out-of-order）核心會在一個約 200 條指令的「重排序緩衝區（Reorder Buffer）」視窗內，找出彼此無相依的指令同時發射到多個執行埠（execution port）。這意味著程式的真實瓶頸往往不是「指令總數」，而是關鍵相依鏈（critical dependency chain）的長度——一連串非得前一個算完才能算下一個的運算。把長相依鏈拆成多條獨立的累加器（例如手動展開迴圈、用 4 個 partial sum 變數），能讓多個執行埠並行工作，這是 SIMD 之外另一個常被忽略的常數因子來源。

要系統性地判斷一段程式「該往哪裡優化」，可借用 Roofline 模型。它把效能上限畫成兩段折線：受記憶體頻寬限制的斜坡，與受計算吞吐限制的水平頂。橫軸是運算強度（arithmetic intensity，每搬一位元組做幾次浮點運算），縱軸是可達 FLOPS。落在斜坡上的程式是 memory-bound——再怎麼向量化也沒用，該做的是改善資料局部性（接回入門篇的快取與 SoA）；落在頂端的才是 compute-bound，這時 SIMD 與 ILP 才是正解。這個框架能幫你避免把力氣花錯地方。

多核心時代的隱形敵人：偽共享與記憶體模型

當你從單執行緒走向多執行緒，會撞上一個入門篇與本文前面都沒提的鬼魅——偽共享（false sharing）。回憶快取列是 64 位元組的搬運單位。若兩個執行緒各自更新兩個邏輯上獨立、但恰好落在同一條快取列的變數，硬體的快取一致性協定（如 MESI）會以為它們在爭搶同一塊資料，每次寫入都迫使對方的快取列失效、重新同步。結果是兩個本該完全平行的執行緒，效能塌陷得像在搶同一把鎖。解法是用對齊（alignas(64)）或填充（padding）把熱資料分到不同快取列。

更底層地，C++11 起有了正式的記憶體模型（memory model）與 std::atomic。std::memory_order_relaxed、acquire、release、seq_cst 等記憶體序，精確規範了多核心下記憶體操作的可見性與重排序界線。這讓你能寫出無鎖（lock-free）資料結構，用最弱、夠用的記憶體序換取效能——這正是高效能並行程式庫的核心。理解到這一層，你會發現「C++ 追求效能」最終是一場與硬體記憶體階層、快取一致性協定、處理器亂序引擎的精細協商。每一次你寫下 alignas、選一個 memory_order、或拆開一條相依鏈，都是在替整顆晶片重新編排一支讓資料流最順的舞——這份與機器對話的能力，正是系統思維與一般程式設計的分水嶺。