開銷在線性存儲器空間尋址2D陣列

Question

是否在以線性方式多維數組尋址的尋址值作爲

values[row_num*row_width + column_num] 

相比值[行] [COL時招致額外的計算的乘法/加法]？還是編譯器將後者轉換爲前者？

Answer 1

編譯器是否將後者 轉換爲前者？

是的。如果您對連續的內存位置進行索引，則高速緩存將對您有利。

Answer 2

假設您正在比較索引到分別爲int values[M*N]和int values[M][N]，那麼這些將在實踐中創建等效代碼。

但是，如果您使用values[row][col]來索引例如int (*values)[N]，那麼這是另一回事...

Answer 3

這取決於。如果聲明一個這樣的數組：

int values[m][n]; 

則編譯器優化的訪問，即，使用的存儲器中的線性片段並計算右偏移（如在你的僞代碼）。

但是，如果你聲明一個數組是這樣的：

int **values; 
values = new int*[m]; 
for (size_t i = 0; i < m; ++i) values[i] = new int[n]; 

那麼編譯器不能優化像

values[row][col] 
// same as 
*(*(values+row) + col) 

即數組訪問這樣的代碼會產生額外的內存訪問。而且，由於在當前的體系結構中，存儲器訪問比計算偏移量更昂貴幾個數量級，所以這種更維數組的類型比使用線性存儲器和計算塊（或者讓編譯器在可能的情況下計算）效率更低偏移。