二維數組訪問順序對性能的影響：a[i][j] vs a[j][i] 緩存命中率差異

實驗數據

• a[i][j] 顺序訪問：94 秒
• a[j][i] 跳躍訪問：488 秒（慢 5 倍）

測試代碼：三重循環 k(10000) → i(MAX) → j(MAX)，賦零操作。

反汇编對比

指令流幾乎相同，僅寄存器偏移量微調，指令級性能無差異。

根本原因：CPU 緩存行

• 內存按緩存行（典型 64 字節）載入 L1/L2 緩存。
• a[i][j] 連續訪問同一行元素，空間局部性強，一次載入複用多次。
• a[j][i] 跨行訪問，每次只用緩存行 1 個元素，導致緩存未命中頻繁讀主存。

優化建議

1. 數組/結構體順序訪問，提高緩存命中率。
2. 熱點循環減少分支判斷，提高分支預測命中率。
3. 大矩陣運算考慮分塊/循環展開/向量化。

結論

「數據結構佈局 + 訪問模式」決定緩存效率，進而決定實際運行速度。寫高性能代碼時務必考慮內存訪問模式。