为什么这会提高性能？

Question

我有两个for循环基本上在两个不同的数组中查找(每个数组的峰值大小约为2-4k),并根据这些值在第三个数组中设置一个值.由于一些奇怪的原因,这段代码的性能有两个不同,这取决于我把两个for循环放在哪个顺序.

这是第一次设置.它在我的PC上执行约150毫秒:

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase)
{
    List<double> times = new List<double>();
    TimeTest timeTest = new TimeTest();

    int aLen = a.Length;
    int bLen = b.Length;

    int[,] resultMatrix = new int[a.Length + b.Length, aLen];
    int[] result = new int[a.Length + b.Length];

    timeTest.Start();

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++)
    {
        for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++)

        {
            resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1];
        }
    }

现在,如果我只改变循环的顺序,就像这样

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++)
{
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++)
 {
        resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1];
    }
}

该方法的总运行时间下降到约400毫秒.循环次序的简单交换如何将性能提高近300%？我想它是某种缓存或指针性能的东西？

Answer 1

这是一个数据安排的事情.将内存视为单维数组.这就是事物实际安排在磁盘上的方式(就计算机而言.)因此,在创建多维数组时,当您更改循环顺序时,您将更改数组的遍历方式.你不是按顺序阅读,而是从一个位置跳到另一个位置.

多维数组对您来说是这样的:

就像这样对电脑来说.最佳遍历方式的索引如下箭头所示:

因此,当您更改数组循环时,数组的遍历方式如下:

因此,您会获得更多缓存未命中和更差的执行算法.