優化C++ 2-d陣列

我需要一種方法來代表用C雙打的2 d陣列（緻密基質）++，具有絕對最小訪問開銷。優化C++ 2-d陣列

我已經做了各種Linux/UNIX機器和gcc版本的一些時間。向量的STL向量，聲明爲：

vector<vector<double> > matrix(n,vector<double>(n));

並通過matrix[i][j]訪問是訪問不是數組聲明爲5％和更慢的100％之間：

double *matrix = new double[n*n];

通過內聯指數函數matrix[index(i,j)]訪問，其中index(i,j)評估爲i + n * j。 n個指針的數組的每一行的開始處，或在堆棧上限定整個事情作爲恆定大小matrix[n][n] - - 運行在幾乎完全相同的速度指數函數法排列2-d陣列而不STL的其它方式。

當開啓優化時，最近的GCC版本（> 4.0）似乎能夠將STL向量向量編譯成幾乎與非STL代碼相同的效率，但這與機器相關。

我想如果可以使用STL，但必須選擇最快的解決方案。有沒有人有使用GCC優化STL的經驗？

來源

2008-09-30 Chris Johnson

如果您使用GCC，編譯器可以分析您的矩陣訪問並在某些情況下更改內存中的順序。魔術編譯標記被定義爲：

-fipa-matrix-reorg

執行矩陣平整和移調。矩陣展平嘗試用其等價的n維矩陣替換m維矩陣，其中n爲<米。這降低了訪問矩陣元素所需的間接尋址級別。第二個優化是矩陣轉置，試圖改變矩陣的維度的順序，以便改善緩存局部性。兩個優化都需要編程標誌。僅當分析信息可用時才能啓用轉置。

請注意，此選項不由-O2或-O3啓用。你必須自己傳遞它。

來源

2008-09-30 12:19:53

對於矩陣，我的猜測是最快的是使用1D STL數組並重寫（）運算符以將其用作2D矩陣。

但是，STL還定義了一種專門用於不可調整大小的數值數組的類型：valarray。您對就地操作也有各種優化。

的valarray接受作爲參數數值類型：

valarray<double> a;

然後，您可以用切片的，間接的陣列，...當然，你可以繼承的valarray和定義自己的操作符（）（INT i，int j）for 2D arrays ...

來源

2008-09-30 12:08:52 PierreBdR

我給予好評是的valarray，不一定要做出一個自定義的矩陣類型。那麼，自定義矩陣類型可以工作，但仍然應該基於valarray而不是矢量（valarray支持切片，這使得獲得一列就像獲得一行一樣簡單）。 – 2008-09-30 12:12:56

小心繼承std :: valarray;它不是爲繼承而設計的，因爲大部分的「STL」。 – 2008-09-30 13:15:16

只要不向其中添加數據，就可以繼承任何類的STL，因爲構造函數不會被調用。雖然沒有pb添加方法。 – PierreBdR 2008-09-30 13:33:52

我的建議是使用Boost.UBLAS，它提供了快速矩陣/向量類。

來源

2008-09-30 12:08:57

很可能這是局部性的，參考的問題。 vector使用new來分配它的內部數組，所以每行在內存中至少會因爲每個數據塊的頭部而分開;如果在分配內存時內存已經碎片化，它可能會有很長的距離。陣列的不同行可能至少會導致緩存行故障，並可能導致頁面錯誤;如果你真的不走運，兩條相鄰的行可能在共享一個TLB槽的存儲器行上，而訪問它們將會驅逐另一行。

相反的其他解決方案保證所有的數據是相鄰的。如果您調整結構以便儘可能少地使用緩存行，它可以幫助您提高性能。

vector是專爲調整大小的陣列。如果您不需要調整數組大小，請使用常規C++數組。 STL操作通常可以在C++數組上運行。

確保以正確的方向走過陣列，即跨過（連續的存儲器地址）而不是向下走。這將減少緩存故障。

來源

2008-09-30 12:17:09