循环交换与循环平铺

Question

哪种优化更好，哪种情况下更好？为什么？

凭直觉，我越来越觉得循环平铺将一般 是一个更好的优化。

怎么样了下面的例子？ 假设一个缓存在任何时候只能存储大约20个元素。

Original Loop: 
for(int i = 0; i < 10; i++) 
{ 
    for(int j = 0; j < 1000; j++) 
    { 
     a[i] += a[i]*b[j]; 
    } 
} 

Loop Interchange: 
for(int i = 0; i < 1000; i++) 
{ 
    for(int j = 0; j < 10; j++) 
    { 
     a[j] += a[j]*b[i]; 
    } 
} 

Loop Tiling: 
for(int k = 0; k < 1000; k += 20) 
{ 
    for(int i = 0; i < 10; i++) 
    { 
     for(int j = k; j < min(1000, k+20); j++) 
     { 
      a[i] += a[i]*b[j]; 
     } 
    } 
} 

Answer 1

你在问题中暴露的前两种情况大致相同。事情会在以下两种情况下真正改变：

案例1：

for(int i = 0; i < 10; i++) 
{ 
    for(int j = 0; j < 1000; j++) 
    { 
     b[i] += a[i]*a[j]; 
    } 
} 

在这里，您正在访问矩阵 “一” 如下：a [0] * A [0]，A [0] *一个1，一个[0] * A [2]，....在大多数结构中，矩阵结构被存储在存储器等：A [0] *一个[0]，一个1 *一个[0]，A [ 2] * a [0]（第一行的第一列后跟第一个原始的第二列，....）。设想你的缓存只能存储5个元素，而你的矩阵是6x6。将存储在缓存中的元素的第一个“pack”将是[0] * a [0]到a [4] * a [0]。你的第一次访问不会导致缓存未命中，所以[0] [0]被存储在缓存中，但第二个是！一个0不存储在缓存中！然后操作系统将缓存元素包0到4。然后你做第三次访问：一个[0] * a [2]将再次超出缓存。另一个缓存错过！

你可以colcude，案例1不是问题的一个很好的解决方案。它会导致大量的高速缓存未命中使我们能够避免改变代码如下：

案例2：

for(int i = 0; i < 10; i++) 
    { 
     for(int j = 0; j < 1000; j++) 
     { 
      b[i] += a[i]*a[j]; 
     } 
    } 

在这里，你可以看到，我们正在访问矩阵，因为它是存储在内存中。因此它比情况要好得多（快）1.

关于你张贴了关于循环平铺，环瓷砖也循环展开第三代码，在大多数情况下，编译器优化automaticaly。 Here's a very interesting post in stackoverflow explaining these two techniques;

希望它能帮助！ （我的英语很抱歉，我不是一个母语）