这种优化技术的名称是什么？

Question

以下优化技术的名称是什么?为什么它比以前的实现更好？

const int size = 100;
int arr1[size];
int arr2[size];

双环

for(int i=0; i<size; ++i)
    arr1[i] = 1;

for(int i=0; i<size; ++i)
    arr2[i] = 1;

转到单环

for(int i=0; i<size; ++i) {
    arr1[i] = 1;
    arr2[i] = 1;
}

编辑

备选方案如下；

• 指针混叠
• 循环不变码运动
• 复制伊莉森
• 环路融合
• 回路展开

Answer 1

维基百科将这种优化称为https://en.wikipedia.org/wiki/Loop_fusion。这个想法是，对于这两个循环，循环控制流的开销不会增加一倍。如果组合循环的内存访问模式很差，这可能不会对性能产生预期的影响，但由于您的示例中的两个循环都按顺序访问相邻的内存块，因此硬件应该能够有效地处理它。

在转换之前，每个循环都这样做：

1. 用0初始化i。
2. 加载常量size。
3. 如果是i >= size，跳到8。
4. 加载开始数组的地址arr1。
5. 将常量1存储在地址arr1 + i。
6. i增量为1。
7. 跳到3。
8. 结束

然后立即：

1. 用0初始化i。
2. 加载常量size。
3. 如果是i >= size，跳到16。
4. 加载开始数组的地址arr2。
5. 将常量1存储在地址arr2 + i。
6. i增量为1。
7. 跳到11点。
8. 结束

任何编译器可能做的第一件事是将“加载常量size”和“加载地址arr”从循环体中移出。然而，总工作量与有用工作的比率却不是很好。将其与组合循环进行比较：

1. 用0初始化i。
2. 加载常量size。
3. 如果是i >= size，跳到10。
4. 加载开始数组的地址arr1。
5. 将常量1存储在地址arr1 + i。
6. 加载开始数组的地址arr2。
7. 将常量1存储在地址arr2 + i。
8. i增量为1。
9. 跳到3。
10. 结束

将子弹点作为机器指令的一种衡量标准，并不是最精确地解释性能的方法。您需要知道实际硬件支持什么指令才能实际比较所需指令的数量。

Answer 2

它被称为环路融合 (或者循环干扰，正如维基百科所指出的那样)，正如你可能理解的那样，在没有相互参照的情况下，两个相邻的循环可以在相同的范围内迭代。

请注意，这并不一定总是提高速度。

Answer 3

在我看来，这更像是悲观！

您完全破坏了循环中访问的数据的内存局部性，并可能导致大量缓存丢失。

确定的唯一方法当然是测量它，但是突然得出结论，这是一种“优化”，仅仅因为您在i上只进行了一半的增量和比较，这是愚蠢的。