最快的陣列尋址

Question

我在存儲圖像信息的陣列上運行圖像分析代碼。不幸的是，代碼非常繁重，平均需要25s才能完成一幀。我看到的主要問題是數組尋址。這是最快通過2D陣列運行並在那裏在

所有的任何差異水平然後垂直

for (int y = 0; y < array.Length; ++y) 
    for (int x = 0; x < array[].Length; ++x) 
     //Code using array[y][x] 

和垂直然後horrizontal？

for (int x = 0; x < array[].Length; ++x) 
    for (int y = 0; y < array.Length; ++y) 
     //Code using array[y][x] 

此外，我試圖避免直接尋址和使用指針。

for (int y = 0; y < array.Length; ++y) 
    int* ptrArray = (int*)array[0]; 
    for (int x = 0; x < array[].Length; ++x, ++ptrArray) 
     //Code using ptrArray for array[y][x] 

或

for (int x = 0; x < array[].Length; ++x) 
    int* ptrArray = (int*)array[0]; 
    for (int y = 0; y < array.Length; ++y, ptrArray += array[].Length) 
     //Code using ptrArray for array[y][x] 

任何幫助不勝感激。 最大

Answer 1

一種選擇是使用反向循環（啓動for() loop從array.Length下降到0）

這會加快速度升技。

例如，

for (int x = array[].Length-1; x >= 0; --x) 
    int* ptrArray = (int*)array[0]; 
    for (int y = array.Length-1; y >= 0 ; --y, ptrArray += array[].Length) 
     //Code using ptrArray for array[y][x] 

Answer 2

我不知道，但你已經拿出例子。所以你可以在一個循環中運行你的代碼示例並自己分析它。

var sw = new Stopwatch(); 
sw.Start(); 
ExecuteMyCode(); 
sw.Stop(); 
Console.WriteLine("Time: " + sw.Elapsed); 

您可能能夠通過使用多線程構建like Parallel.ForEach，以加快處理。如果你的循環中的代碼避免了循環迭代之間的依賴關係，這將會工作得很好。

Answer 3

你會不安全嗎？指針。陣列的問題在於，您仍然對每個訪問進行邊界檢查。指針刪除。注意這是完全支持C＃的 - 但你需要把它放到一個不安全的塊中。這也意味着你必須能夠運行不安全的代碼，這並不總是給定的。

http://msdn.microsoft.com/en-us/library/28k1s2k6.aspx

具有代碼示例。

Answer 4

如果可能，請嘗試重新分配陣列，使第一維小於第二維。它會大大加快速度。 另一個解決方案是像上面提出的那樣在一維數組中重新分配數據。

Answer 5

務必確保您的最內層循環訪問連續內存。

這通常是您的圖像的行。請注意，在矩形陣列中，您應該將其作爲最後一個索引：array[y,x]。

this paper表明內置的C＃矩形數組（具有多個索引）相當慢。我之前讀過這篇文章，但這是我得到的唯一參考。我會從一個線性數組開始，併爲每一行計算一次偏移量。非託管只會幫助你在非常微不足道的情況下。

如果一個框架需要25秒，那麼它要麼huuuuge，要麼你做非常複雜的處理。在這種情況下，如果您爲每個輸出像素訪問許多輸入像素，則只需花費精力優化內存訪問。

Answer 6

最重要的規則是，除非你的個人資料，它是所有的理論。我並不認爲那些堅持概要分析就是一切的人（沒有一些理論認爲你不比一個把椰子放在耳朵上並等待飛機降臨的貨運教士更好），但是你的理論總是錯誤的或不完整的，所以分析至關重要。

一般來說，我們希望內部掃描是水平的（根據數組而不是圖像，儘管對於大多數格式是相同的）。原因是，以與陣列等：

00 01 02 03 04 05 06 07 08 09 
10 11 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 

這是要被佈局爲：

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 

你想成爲沿可以被裝載到CPU的高速緩存和然後使用連續的塊掃描完全不是從一個塊到另一個塊進行掃描，而是需要定期更改CPU緩存內容。

如果您嘗試平行算法，這一點更爲重要。你希望每個線程都處理它自己的連續的內存塊，只要輸入和輸出都是這樣，而不僅僅是單線程代碼不能處理緩存命中頻率較低的情況，而且會導致對方的緩衝區變髒，需要清爽。這可能是平行化導致速度提升和平行化實際上減慢速度之間的差異。

另一件事是二維數組byte[,]而不是一個數組數組byte[][]，你的問題「數組[y] [x]」中的評論讓我想知道你是否正在使用。同前，得到ARR [1,2]的邏輯是：

1. 檢查邊界
2. 計算位置（簡單快速算術）
3. 檢索值。

對於後者，該邏輯是：

1. 檢查邊界
2. 通過指針獲取陣列。
3. 檢查範圍
4. 檢索值。

還有更好的內存緩存命中頻率。當需要「鋸齒狀」結構時後者具有益處，但這不是這種情況。 2D幾乎總是比數組陣列更快。

事情我沒有看到作爲可能的幫助，但我肯定會嘗試他們在您的情況：

您可能會發現從做你的1D < => 2D邏輯的推動。有一個單維數組，其中idx = y * width + x。它不應該有明顯的區別，但值得嘗試。

的優化會盡力兩個葫蘆呼叫.Length，省略不必要的邊界檢查，所以你會發現手動起重切換到指針運算不會獲得任何東西，但在一個情況下，你真的需要把時間縮短它當然值得剖析。

最後。你有沒有分析你的代碼掃描數組的速度有多快？這可能是代碼的另一部分是真正的瓶頸，你正在修復錯誤的東西。