c# - 最快的数组寻址

Question

我在存储图像信息的数组上运行图像分析代码。不幸的是，代码非常繁重，运行一帧平均需要 25 秒。我看到的主要问题是数组寻址。哪个是运行二维数组最快的，并且在

水平然后垂直

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

然后垂直然后水平？

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

最重要的规则是，在您进行剖析之前，一切都是理论。我不同意那些坚持分析就是一切的人(没有一些理论，你就像一个 cargo 崇拜者把椰子放在耳朵上等待飞机来)但你的理论总是错误或不完整的，所以分析至关重要。

一般来说，我们希望内部扫描是水平的(就数组而言，而不是图像，尽管对于大多数格式来说都是一样的)。原因是像这样的数组:

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 缓存中然后完全使用的连续 block 进行扫描，而不是从一个 block 扫描到另一个 block 并且需要定期更改 CPU 缓存内容。

如果您尝试并行化算法，这一点就更为重要。就输入和输出而言，您希望每个线程都处理自己的连续内存块，而不是像单线程代码那样遭受糟糕的缓存命中率，而且还导致彼此的缓冲区变脏和需要刷新。这可能是并行化导致速度提升和并行化实际上减慢速度之间的区别。

另一件事是二维数组 byte[,] 与数组数组 byte[][] 之间的区别，您在问题中的评论“array[y][x]”让我想知道您是否正在使用。用前者获取arr[1,2]的逻辑是:

1. 检查边界
2. 计算位置(简单快速算术)
3. 检索值。

对于后者，逻辑是:

1. 检查边界
2. 通过指针获取数组。
3. 检查边界
4. 检索值。

内存缓存命中率也较低。后者在需要“锯齿状”结构时有好处，但这里不是这种情况。 2D 几乎总是比数组的数组快。

我认为不太可能有帮助的事情，但我肯定会在您的情况下尝试它们:

您可能会从执行 1d <=> 2d 逻辑中得到提升。有一个一维数组，其中 idx = y * width + x。它应该不会产生明显的差异，但值得一试。

优化确实尝试提升对 .Length 的调用并省略不必要的边界检查，因此您可能会发现手动提升和切换到指针算法不会有任何收获，但在您真正确实需要缩短时间，这当然值得分析。

最后。您是否分析过您的代码在扫描数组而不执行任何操作时的速度有多快？可能是代码的另一部分才是真正的瓶颈，而您正在修复错误的地方。