最快的阵列寻址

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，省略不必要的边界检查，所以你会发现手动起重切换到指针运算不会获得任何东西，但在一个情况下，你真的需要把时间缩短它当然值得剖析。

最后。你有没有分析你的代码扫描数组的速度有多快？这可能是代码的另一部分是真正的瓶颈，你正在修复错误的东西。