这为什么会提高性能？

Question

我有两个循环，基本上查找两个不同的阵列（每个峰值大约2-4k的大小），并根据这些值在第三个数组中设置一个值。出于某种奇怪的原因，这段代码的性能之间有两个不同因素，具体取决于我放置两个for循环的顺序。

这是第一个设置。它执行在我的电脑中〜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

这是一个数据安排的事情。将内存视为单维数组。这就是事实上如何安排在磁盘上（就计算机而言）。因此，在创建多维数组时，当您更改循环顺序时，您将更改数组如何遍历。不是按顺序阅读，而是从一个位置跳到另一个位置。

---

多维数组看起来像这样给你：

而且像这样的电脑。穿越的最佳方式有下面的箭头以下指标：

所以，当你改变你的阵列循环数组进行遍历这样的：

因此，你得到更多的高速缓存未命中和性能较差的算法。

Answer 2

这很可能与缓存命中/未命中有关。区别在于顺序vs散布访问，其大小超过一个缓存行的大小。

对于普通的C++循环，它也有助于使循环向后在循环中获得一些性能。不知道它如何适合.NET。

Answer 3

数据的局部性，局部性，局部性。维基百科（它说它比我更好）：

线性数据结构：经常发生局部性，因为代码包含的循环倾向于通过索引来引用数组或其他数据结构。顺序局部性是空间局部性的一种特殊情况，当相关数据元素被线性排列和访问时会发生。例如，一维数组中的元素从基地址到最高元素的简单遍历将利用数组在存储器中的顺序局部性[2]。当线性遍历遍历具有相同结构和大小的相邻数据结构的较长区域时，发生更一般等距的局部性，并且除此之外，不是整个结构都在访问中，而是仅仅是结构的相互对应的相同元素。当矩阵表示为行的顺序矩阵并且要求访问矩阵的单个列时，就是这种情况。

Answer 4

我记得在Code Complete中读到这个。在大多数语言中，数组是按顺序设置最后一个索引设置的，所以当迭代最后一个索引时，您直接访问一行中的字节，而不是在迭代第一个时跳过。

Answer 5

你的直觉是对的，它是一个缓存问题。 @Mike Daniels在下面提出问题基本上描述了完全相同的问题。第二位代码将获得更多的缓存命中。

Fastest way to loop through a 2d array?

但是，嘘我们不应该关心的性能吗？ :)

Answer 6

我也会认为数组a和b的相对大小会有所不同。

如果a.length较大而b.length较小，则第二个选项应该更快。相反，如果a.length较小且b.length较大，则第一个选项会更快。 问题是避免内部循环的设置/拆卸成本。

顺便说一句，你为什么有

INT ALEN =则为a.length;

但是直接调用a.Length？好像你应该选择一个或另一个。