百萬級二維數組遍歷：行優先還是列優先更高效？

高效遍歷百萬級二維數組：行優先與列優先的性能差異

本文分析了遍歷一個100萬元素的二維數組 matrix[x][y] 的兩種方法，并解釋了其性能差異的根本原因。

兩種遍歷方式如下：

方式一（行優先）：

for (int x = 0; x < size; x++) {   for (int y = 0; y < size; y++) {     // ...操作 matrix[x][y] ...   } }

方式二（列優先）：

for (int y = 0; y < size; y++) {   for (int x = 0; x < size; x++) {     // ...操作 matrix[x][y] ...   } }

雖然直覺上兩種方式效率相近，但實際測試結果顯示存在顯著差異。這并非編譯器優化導致，而是與計算機內存訪問機制直接相關。

二維數組通常采用行優先（row-major）存儲方式，這意味著同一行元素在內存中連續存儲。方式一，外層循環遍歷行，內層循環遍歷列，使得每次訪問 matrix[x][y] 時，內存訪問都是連續的。而方式二，外層循環遍歷列，內層循環遍歷行，導致內存訪問跳躍式進行。

CPU緩存機制使得連續內存訪問速度遠高于跳躍式訪問。連續訪問充分利用CPU緩存，減少內存訪問次數，顯著提高效率。相反，跳躍式訪問頻繁導致緩存失效，需要不斷從主內存加載數據，降低速度。因此，在行優先存儲的二維數組中，方式一（行優先遍歷）效率遠高于方式二（列優先遍歷）。