C/C++優化數據結構，數組的數組或只是陣列

與使用16字節4V4一個字節矩陣的程序工作：C/C++優化數據結構，數組的數組或只是陣列

unsigned char matrix[4][4];

和一些256字節16v16一個字節矩陣：

unsigned char bigMatrix[16][16];

很多時候，由於數據操作，我不得不在程序中循環列循環，導致緩存未命中。

將性能提高，如果我使用一個數組來代替，即

unsigned char matrix[16]; 
unsigned char matrix[256];

，並通過使用一些變量來檢索元素訪問的元素，即

matrix[variableA*variableB + i];

其中variableA的* variableB的+我的需求每次我想訪問一個元素時都要重新計算。

我只想要速度優化和內存沒有問題。這會有所幫助嗎，例如在某些性能受到影響或損失的情況下，還是差別太小甚至不在乎？

來源

2009-02-09 Milan

我會說，太小而不在乎，但我會等待一個真正知道更好的人給出一個真實的答案。 – sykora 2009-02-09 12:08:13

它沒有區別。數據在任何一種情況下都以完全相同的方式進行佈局，並且也以相同的方式進行訪問。即使它不會生成完全相同的程序集，我也會感到驚訝。

但是，對於256byte的表，在任何情況下都不可能發生緩存未命中。 CPU的L1緩存通常在32到128KB之間，所以我懷疑你在任何情況下都會遇到很多緩存未命中。

來源

2009-02-09 12:09:33 jalf

+1這只是一個更大的緩衝區的問題 – 2009-02-09 12:12:04

你說每次訪問元素時都需要重新計算variableA*variableB+i，這種情況在任何情況下都會發生，即使使用多維數組也是如此。唯一的區別是，在多維數組中，編譯器會發出此代碼，因此您不會看到它，而在一維數組中，您可以在源代碼中看到代碼。

來源

2009-02-09 12:16:57 Motti

如果您對數組進行順序訪問，則大線性數組可能會稍快，因爲您在每個索引處都保存了乘法運算。如果你正在逐列循環，那麼你正在順序訪問;至少在[行] [列]符號中，與我曾經談過的每個人都是「標準」符號。

我懷疑你的256元素陣列會在現代硬件上導致緩存未命中，但我願意被證明是錯誤的。 cachegrind告訴你什麼？

來源

2009-02-09 12:18:15

您可以使用指針以相同的方式遍歷任一數組。 – strager 2009-02-09 13:17:50

儘管編譯代碼的行爲速度同樣快，但還是有一些設計問題：索引代碼的重用可能會最大化。

這樣做的最好方法是將它包裝在一個容器中，該容器知道如何以最快的方式循環它的元素。他們爲此得到了一個名字：一個'內部迭代器'，正如GoF設計模式「迭代器」模式中所提到的。

一個簡單的例子：

template< int N > 
struct CNxN { 
    typedef int t_row[N]; 
    typedef t_row t_matrix[N]; 
    t_matrix m_Contents; 

    template< typename Functor > 
    void each(Functor & f) { 
     for(int col = 0; col != N; ++col) 
      for(int row = 0; row != N; ++row) 
       f(m_Contents[row][col]); 
    } 
}; 

// client code 
CNxN<3> matrix = { { {1,1,1},{1,1,1},{1,1,1} } }; 

struct sum { 
     long result; 
     sum():result(0){} 
     void operator()(int i){ result +=i; } 
}; 
matrix.each(sum); 
assert(sum.result==0); 
assert(has_performed_in_the_fastest_possible_way);//;)

來源

2009-02-09 12:18:58 xtofl

在每個函數中使用指針代替索引來提高速度。雖然可以通過編譯器進行優化。提供stl迭代器會很好，所以stl算法可以在你的矩陣上使用（儘管其中一些可能沒有用）。 – strager 2009-02-09 13:19:27

事實上：類似於stl的迭代器會更好。馬修威爾遜寫了一本關於這本書的好書（必讀！）。你也是對的，我主要想展示重用風格。 – xtofl 2009-02-10 12:21:08

jalf大多是正確的。 L1高速緩存被分成塊，塊的大小取決於處理器，但大小爲32字節。所以，如果你一次只讀一個字節的內存，你會得到每32個字節（或任何塊大小）的緩存缺失。現在，英特爾芯片在這裏非常聰明，可以檢測順序讀取並預取數據，從而減少緩存未命中的影響。

4x4矩陣極有可能位於單個L1塊（或高速緩存行）中，因此按行或列訪問它幾乎沒有什麼區別。當然，你不想把矩陣分成兩個緩存行，所以對齊的內存很重要。

但是，16x16矩陣不適合緩存行。所以，如果你跳過數組處理列，你會得到很多緩存未命中。正如jalf所說，對索引的計算幾乎沒有什麼區別，因爲CPU和內存之間的比例很高（即，可以爲每個緩存未命中執行大量的CPU工作）。

現在，如果您主要是以列定位的方式處理矩陣，那麼您的最佳選擇是轉置所有矩陣（交換行與列），因此您的內存訪問將更順序並且緩存未命中次數將會減少，並且CPU將能夠更好地預取數據。所以，與其組織這樣的矩陣：

0 1 2 .... 15 
16 17 18 .... 31 
.... 
240 241 242 .... 255

，其中數字是內存從矩陣的開始偏移，從而組織：

0 16 32 ... 240 
1 17 33 ... 241 
... 
15 31 47 ... 255

來源

2009-02-09 12:25:16 Skizz

當我在學校的一個我的CS老師堅持認爲，如果你爲單數製作數組，它會更快。那一天，我是很惱火......

來源

2009-02-09 12:27:33

很多時候由於數據操縱我被迫循環逐列[...]

你不能兩者兼得：要麼如果矩陣足夠大，則按行或按列方式循環將導致緩存未命中（請參閱Skizz' answer）。針對更經常執行的循環類型進行優化。

如果內存消耗不是問題，您也可以考慮保存矩陣及其轉置。

來源

2009-02-09 12:28:23 Christoph

C/C++優化數據結構，數組的數組或只是陣列

回答

相關問題