代碼執行效率深度解析（三）：CPU 快取與局部性原理實戰

前兩篇探討演算法與編譯器優化，本文聚焦硬體層面的關鍵因素——CPU 快取與記憶體局部性。同樣的邏輯，不同的迴圈結構可能導致數倍效能差距，根源在於能否善用 L1/L2 快取。

反直覺的迴圈效能案例

// 寫法 A：融合迴圈
for (int i = 0; i < 100; i++) {
  DoSomethingA();
  DoSomethingB();
}

// 寫法 B：分離迴圈
for (int i = 0; i < 100; i++) DoSomethingA();
for (int i = 0; i < 100; i++) DoSomethingB();

直覺認為寫法 A 減少迴圈開銷（計數器遞增、條件跳轉）應更快。但實測往往寫法 B 顯著更快。原因在於快取局部性。

CPU 快取層級與 Cache Line

• L1 Cache：核心獨享，~32-64 KB，延遲 1-4 週期
• L2 Cache：核心共享/獨享，~256 KB-1 MB，延遲 10-20 週期
• L3 Cache：多核共享，~8-32 MB，延遲 30-50 週期
• 主記憶體：延遲 100-300 週期

關鍵機制：CPU 以 Cache Line（通常 64 bytes） 為單位從較慢層級載入資料。讀取某位址後，其鄰近 64 bytes 同步載入 L1。

局部性兩大維度

為何分離迴圈更快？

寫法 A 交替執行 A/B，導致 A 的熱資料在 B 執行期間從 L1 退出（快取污染），下輪迴圈需重新載入。寫法 B 密集執行 100 次 A，資料長駐 L1，再密集執行 B，**最大化時間局部性**。

實戰優化模式

1. 結構體陣列 (AoS) vs 陣列結構體 (SoA)

// AoS：同一座標 x/y 相鄰，適合逐點處理
struct Point { public int X, Y; }
Point[] points = new Point[N];

// SoA：x 陣列、y 陣列分離，適合向量化運算
int[] xs = new int[N];
int[] ys = new int[N];

若迴圈只處理 X，SoA 避免載入無用 Y，節省快取頻寬；若需同時處理 X/Y，AoS 更佳。

2. 迴圈分塊

大矩陣運算時，將迴圈拆分為適合 L1/L2 大小的塊，確保工作集駐留快取。

3. 避免偽共享

多執行緒寫入同一 Cache Line 不同變數會導致核心間快取同步風暴。對齊 64 bytes 或使用 ThreadLocal<T>。

Profiling 工具驗證

靜態代碼分析無法準確預測快取行為。必須使用：

• Visual Studio Profiler (CPU Usage + Hardware Counters)
• PerfView / ETW (Cache Misses, Branch Mispredictions)
• BenchmarkDotNet 配合 HardwareCounters 屬性

結論：演算法與編譯器優化是基礎，但記憶體存取模式決定效能上限。理解快取機制，設計符合局部性原理的資料結構與迴圈，是高效能程式設計的核心技能。