sfr*_*sfr 4 c optimization loop-unrolling
我试图将这个循环展开 2 倍。
for(i=0; i<100; i++){
x[i] = y[i] + z[i];
z[i] = y[i] + a[i];
z[i+1] = y[i] * a[i];
}
我把它展开到：
for(i=0; i<100; i+=2){
x[i] = y[i] + z[i];
x[i+1] = y[i+1] + z[i+1];
z[i] = y[i] + a[i];
z[i+1] = y[i] * a[i];
}
我不确定如何展开 z[i] 的行，因为原始 for 循环已经有 z[i+1]。任何人都可以帮助我理解这一点吗？
我会说简单地添加 i+1 的行。但是您必须确保它们的顺序正确，因此：
for(i=0; i<100; i+=2){
x[i] = y[i] + z[i];
z[i] = y[i] + a[i];
z[i+1] = y[i] * a[i];
// next iteration
if (i+1 < 100) {
x[i+1] = y[i+1] + z[i+1];
z[i+1] = y[i+1] + a[i+1];
z[i+2] = y[i+1] * a[i+1];
}
}
编辑
为了使其对所有上限（不仅是甚至）安全，您必须在循环中添加一个 if
正如 Adrian Mole 提到的，最好首先检查上限或方便地设置数组的大小
我试图将这个循环展开 2 倍。
你不应该这样做，因为那没有多大帮助。如果您允许，编译器将免费进行展开和优化。您得到的循环不会从展开中受益，并且编译器足够聪明来确定这一点 - 因此它们也不会进行任何展开。所编写的循环会阻止编译器完成其工作。让我们解决它。
首先，我们想要一些可以实际编译的东西。无论元素是整数、浮点数还是双精度数，编译器都会很好地处理所有常见类型。
我们将使用 gcc x86-64 10.2 和-O3选项在 godbolt 上编译它。
让我们开始：
typedef int element;
我们必须假设一些事情。我将做出合理的假设，即a、x和y数组z不重叠。这非常重要 - 如果情况并非如此，则必须在问题中说明（！！）。关键字restrict说明了这一事实：
void test1(elt *restrict a, elt *restrict x, elt *restrict y, elt *restrict z) {
for (int i=0; i<100; i++) {
x[i] = y[i] + z[i];
z[i] = y[i] + a[i];
z[i+1] = y[i] * a[i];
}
}
如果您向此函数提供一个或多个重叠的数组，您将得到未定义的行为，并且很可能会得到不正确的结果。但优化必须基于一些假设 - 否则，即使您最初计划的手动展开通常也是不可能的。
如果我们只是将编译器选项从 更改-O3为-O3 -funroll-loops，我们就会以超过 2 的系数很好地展开此代码。我们强制编译器采取行动，它会强制执行，无论它是否有意义。那么你得到了你想要的东西，结案了，我们回家吧？啊，不，那一点也不有趣——这太低估了我们自己:)
在不强制执行的情况下，编译器“仅”生成按 执行此循环的代码i+=1。
现在观察z[i+1]实际上并不需要。除了最后一个值之外的所有值都被覆盖。它所做的就是将上一次迭代的输出提供给下一次迭代的输入。
我们可以在没有转发存储的情况下重写该函数：
void test2(elt *restrict a, elt *restrict x, elt *restrict y, elt *restrict z) {
elt fwd = z[0];
for (int i=0; i<100; i++){
x[i] = y[i] + fwd;
z[i] = y[i] + a[i];
fwd = y[i] * a[i];
}
z[100] = fwd;
}
编译器已经在每次迭代中生成了一个较少的存储，但仍然仅按 进行迭代i+=1。
转发操作对于优化器来说是个坏消息。一些高端 CPU 具有足够聪明的数据依赖性跟踪和足够长的管道，可以在一定程度上解决这个问题 - 但我们在这里讨论的不是典型的消费者系统（无论如何，还没有）。
为了使每个人的机会均等，每个循环迭代应该是独立的：其输出不应馈送到任何其他输入。fwd我们可以在需要时正确计算 ，而不是计算 的未来值：
void test3(elt *restrict a, elt *restrict x, elt *restrict y, elt *restrict z) {
x[0] = y[0] + z[0];
z[0] = y[0] + a[0];
for (int i=1; i<100; i++){
x[i] = y[i] + y[i-1] * a[i-1];
z[i] = y[i] + a[i];
}
z[100] = y[99] * a[99];
}
这是一个非常好的消息 - 编译器可以轻松证明每个循环迭代的输出是独立的，并且它不仅将循环展开 4 倍，即迭代i+=4，而且还完全矢量化了循环内部，因此循环内的指令加在一起的成本大约与非向量化循环的单次迭代（给予或接受）一样多，但它们的工作量是后者的 4 倍！
请注意，这是通过正确编写 C 代码来实现的。我们没有进行任何微观优化，只是删除了跨循环迭代的转发——这种转发在当今世界必须被视为悲观主义。摆脱它可以让编译器读懂我们的想法:)
现在，如果我们让编译器为更现代的架构生成代码，比如，会怎么样skylake？gcc -O3 -march=skylake-avx512 完全展开循环。此外，循环每次迭代只需要少于一条指令。您没看错：循环的内部部分生成了不到 100 条机器指令 - 只有设置/分解代码才使其数量超过 100 条。
在这一点上，可能不值得做更多的事情 - 我想说，性能相当令人满意。
但是，如果您确实想手动展开循环（例如，如果您这样做是为了完成某些学校作业，而不是因为您关心实际表现，因为这不会变得更好） - 那么现在是时候了这样做，因为让编译器生成良好代码的形式也使得手动展开变得微不足道：
void test4(elt *restrict a, elt *restrict x, elt *restrict y, elt *restrict z) {
x[0] = y[0] + z[0];
z[0] = y[0] + a[0];
x[1] = y[1] + y[0] * a[0];
z[1] = y[1] + a[1];
for (int i=2; i<100; i+=2){
x[i] = y[i] + y[i-1] * a[i-1];
z[i] = y[i] + a[i];
x[i+1] = y[i+1] + y[i] * a[i];
z[i+1] = y[i+1] + a[i+1];
}
z[100] = y[99] * a[99];
}
展开它就像 x4 一样容易，等等。但是对于任何好的编译器和优化构建，这个版本都不会比未展开的版本更好，如果你让编译器使用更好的架构而不仅仅是“基线”x86- 64，那么任何手动展开都是毫无意义的，因为编译器将其完全展开为 Skylake 的不到 110 条机器指令。
但等一下。这是针对int数据类型的。而且，好吧，事实证明这int有点糟糕。是的，现在快速代码的作用不再是拖拽整数——它适用于浮点。图像和视频解码以及音频处理——如今它们都需要大量的浮点计算。因此 CPU 设计者投入了大量的工作来提高效率。
因为float它正好有 100 条指令，完全展开（没有迭代，只是直线代码）。
For double，-O3 -march=skylake-avx512 -funroll-loops它被展开为 3 个大迭代，循环体中有47 条指令。一切都是矢量化的，管道运行得又热又重，而且您将收回为昂贵的 CPU 支付的所有费用。最后。
但我们再次迫使编译器采取行动。事实证明，展开循环那么多并不总是很重要——它取决于运行它的 CPU，而且代码的扩展所带来的好处在某种程度上相形见绌。在生产中，您希望以两种不同的方式编译此函数，在启动时对其进行基准测试，然后选择更快的一种。如果没有-funroll-loops，整个test3函数有 32 条指令长，并且迭代循环体 24 次。每次迭代通过 6 条指令与 RAM（读取和写入的总数）交换超过 120 个字节的数据。平均每条指令 20 个字节（这确实是近似值，我没有仔细观察）。
从我的粗略测量来看，这个double变体的运行内存带宽比原始版本高一个数量级（！）int。
这无疑是一次有趣的冒险。
顺便说一句 - 因为必须说：现代编译器是工程奇迹。我并没有夸大其词。你真的必须前往https://godbolt.org亲自尝试一下！