c# - 通过后续索引扫描二维数组并不总是更快吗？

Question

假设 x 是第一个索引，y 是第二个索引(由于较少缓存未命中)，垂直扫描二维数组显然更快。

然而，令我惊讶的是，当我需要使用垂直条纹(条纹宽度为 3)扫描阵列时，如果我垂直处理单个条纹，我得到的结果比我这样做时差 5%横向。有人可以解释一下这怎么可能吗？

(编辑:实际上“垂直”方法中的数组访问确实更快，但是这种方法使用了更多的循环这减慢了整个事情比我们从更少的缓存未命中中获得的更多；查看答案)。

下面的代码只是一个示例，但是当我在 BenchmarkDotNet 中对我的扫描线填充算法实现中扫描数组的相同方法进行基准测试时，我得到了相同的性能差异。

这是我的 C# 基准测试:

private void ProcessVerticalStripesHorizontally(int[,] matrix)
{
    int size = matrix.GetLength(0);
    for (int x = 1; x < size - 1; x++)
    {
        for (int y = 0; y < size; y++)
        {
            // should be slowe because x is changed often
            var value = matrix[x, y];
            var valueLeft = matrix[x-1, y];
            var valueRight = matrix[x+1, y];
        }
    }
}

private void ProcessVerticalStripesVertically(int[,] matrix)
{
    int size = matrix.GetLength(0);
    for (int x = 1; x < size-1; x++)
    {
        // should be faster because x doesn't change often
        for (int y = 0; y < size; y++)
        {
            var value = matrix[x, y];
        }
        for (int y = 0; y < size; y++)
        {
            var valueLeft = matrix[x - 1, y];
        }
        for (int y = 0; y < size; y++)
        {
            var valueRight = matrix[x + 1, y];
        }
    }
}

[Test]
public void AccessToArrayTest()
{
    int size = 5000;
    var matrix = new int[size, size];
    ProcessVerticalStripesHorizontally(matrix);
    ProcessVerticalStripesVertically(matrix);

    for (int run = 0; run < 5; run++)
    {
        Console.WriteLine("run " + run + ": ");

        var stopwatch = Stopwatch.StartNew();
        for (int iteration = 0; iteration < 5; iteration++)
        {
            ProcessVerticalStripesHorizontally(matrix);
        }
        Console.WriteLine("processing stripes horizontally: " 
        + stopwatch.ElapsedMilliseconds + " ms");

        stopwatch.Restart();
        for (int iteration = 0; iteration < 5; iteration++)
        {
            ProcessVerticalStripesVertically(matrix);
        }
        Console.WriteLine("processing stripes vertically: " 
        + stopwatch.ElapsedMilliseconds + " ms");
        Console.WriteLine();

    }
}

结果:

run 0: 
processing stripes horizontally: 454 ms
processing stripes vertically: 468 ms

run 1: 
processing stripes horizontally: 441 ms
processing stripes vertically: 456 ms

run 2: 
processing stripes horizontally: 437 ms
processing stripes vertically: 453 ms

run 3: 
processing stripes horizontally: 437 ms
processing stripes vertically: 456 ms

run 4: 
processing stripes horizontally: 441 ms
processing stripes vertically: 449 ms

Answer 1

通过分析您的代码，我可以看到 ProcessVerticalStripesHorizo​​ntally 方法的复杂度为 O(n^2) - 它将执行 n*n 次循环。

同时，ProcessVerticalStripesVertically 方法的复杂度为 O(n*3n) - 它将执行 n*n*3 次循环。

因此，如果您的矩阵是 100 x 100，我们将具有以下内容:

ProcessVerticalStripesHorizo​​ntally 100 * 100 = 10,000 循环次数ProcessVerticalStripesVertically 100 * 100 * 3 = 30,000 循环次数