快速訪問矩陣

Question

我需要訪問一個帶有C++代碼的二維矩陣。如果矩陣是mat[n][m]，我要訪問（在for循環）這些位置：

mat[x][y], mat[x-1][y-m-1], mat[x-1][y], mat[x][y-1] 

下一輪迭代我必須做的：

x=x+1 

，然後再：

mat[x][y], mat[x-1][y-m-1], mat[x-1][y], mat[x][y-1] 

什麼可能是這些位置最接近內存加速我的代碼的最佳方式？

Answer 1

由於您沒有提供足夠的信息，因此很難說哪種方法更好。

你可以嘗試展開你的循環來連續訪問內存。

例如，從mat[x][y]讀取4次，然後mat[x-1][y-m-1] 4次，然後mat[x-1][y] 4次，然後mat[x][y-1] 4次。之後，您在一次迭代中處理加載的4組數據。

我敢打賭，瓶頸不是內存訪問本身。它應該是內存地址的計算。這種內存訪問方法可以寫入SIMD加載，因此可以減少內存地址計算的3/4時間成本。

如果您必須按順序處理您的任務，則可以嘗試不使用多維訂閱。例如：

for(x=0; x<n; x++) 
    doSomething(mat[x][y]); 

可以用做：

for(x=y; x<n*m; x+=m) 
    doSomething(mat[0][x]); 

在你避免一個lea指令第二種方式。

Answer 2

如果你正在水平迭代，將矩陣排列爲mat [y] [x]，特別是如果它是一個數組數組（矩陣的佈局在你的回答中不清晰）。

Answer 3

如果我得到這個正確的結果，你會遍歷整個陣列，儘管你只提到x = x + 1作爲更新（y沒有）。然後我會看到陣列爲一維，單個計數器i從0變爲總陣列長度。然後四個值在每個循環訪問將

mat[i], mat[i-S-m-1], mat[i-S], mat[i-1] 

其中S是步幅（行或根據你的表現列）。無論內存佈局如何，這都需要較少的地址計算。它也需要較少的索引檢查/更新，因爲只有一個計數器i。另外，S+m+1是不變的，所以你可以這樣定義它。