c - 循环交换与循环平铺

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”:a[0]*a[0], a[0]*a 1 , a[0]*a[2],.... 在大多数架构中，矩阵结构在内存中的存储方式如下:a[0]*a[0], a 1 *a[0], a[2]*a[0](第一行的第一列，然后是第一个原始数据的第二列，....)。假设您的缓存只能存储 5 个元素，而您的矩阵是 6x6。将存储在缓存中的第一个“包”元素是 a[0]*a[0] 到 a[4]*a[0]。您的第一个访问不会导致缓存未命中，因此 [0][0] 存储在缓存中，但第二个是!一个0没有存储在缓存中!然后操作系统将缓存元素包 a 0到 4 .然后你执行第三次访问:a[0]*a[2] 再次超出缓存。另一个缓存未命中!

您可以推测，案例 1 不是解决问题的好方法。它会导致大量缓存未命中，我们可以避免更改以下代码:

案例 2:

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

如您所见，我们正在访问存储在内存中的矩阵。因此它比情况 1 好得多(快)。

关于您发布的关于循环平铺的第三个代码，循环平铺和循环展开是在大多数情况下编译器自动执行的优化。 Here's a very interesting post in stackoverflow explaining these two techniques;

希望对您有所帮助! (对不起我的英语，我不是母语人士)