在 C 中展开 For 循环

Question

我正在尝试将这个循环展开 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]。谁能帮我理解一下？

Answer 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 提到的，最好首先检查上限或方便地设置数组的大小

Answer 2

I am trying to unroll this loop by a factor of 2.

你不应该，因为那没有多大帮助。如果您允许，编译器将免费进行展开和优化。你得到的循环不会从展开中受益，编译器足够聪明来确定这一点——所以他们也不做任何展开。所写的循环会阻止编译器完成它们的工作。让我们修复它。

首先，我们想要一些可以实际编译的东西。元素是整数、浮点数还是双精度数并不重要 - 编译器会很好地处理所有常见类型。

我们将使用带有 -O3 选项的 gcc x86-64 10.2 在 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。

转发操作对优化器来说是个坏消息。一些高端 CPUs 有足够聪明的数据依赖跟踪和足够长的管道来在一定程度上解决它——但我们在这里不是在谈论典型的消费者系统（无论如何，现在还不是）。

为了让每个人的机会均等，每个循环迭代都应该是独立的：它的输出不应该提供给任何其他输入。我们可以在需要的时候计算它，而不是计算 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，而且 also 它完全向量化了循环内部，因此循环内的指令加在一起的成本大约与非向量化循环的单次迭代（give 或 take）一样多，但是它们做 4 倍的工作！

注意，这是通过正确编写 C 代码实现的。我们没有做任何微优化，只是删除了跨循环迭代的转发 - 这种转发在当今世界必须被视为悲观。摆脱它授权编译器读懂我们的想法 :)

现在，如果我们让编译器为更现代的架构生成代码，比如 skylake，会怎样？ gcc -O3 -march=skylake-avx512 完全展开循环。此外，循环每次迭代 少于一条指令 。您没看错：循环的内部部分产生不到 100 条机器指令 - 只有 setup/breakdown 代码让它超过 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，那么任何手动展开都是毫无意义的，因为编译器将其完全展开为少于 110 条 Skylake 机器指令。

但是等一个 minizel。那是针对 int 数据类型的。而且，好吧，事实证明 int 有点糟糕。是的，绕过 int 并不是现在快速代码所做的事情——它适用于浮点数。图像和视频解码以及音频处理——如今它们都需要大量的浮点计算。所以 CPU 设计师投入了大量工作来提高效率。

对于 float 正好是 100 条指令，完全展开（没有迭代，只是直线代码）。

对于 double，-O3 -march=skylake-avx512 -funroll-loops 展开为 3 次大迭代，循环体中有 47 条指令。一切都是矢量化的，管道运行又热又重，您将收回为昂贵的 CPU 支付的所有钱。终于。

但我们再次强迫编译器的手。事实证明，将循环展开那么多并不总是至关重要 - 这取决于 CPU 你运行它的作用，并且代码的扩展带来的好处有些相形见绌。在生产中，您希望以两种不同的方式编译此函数，在启动时对其进行基准测试，然后选择更快的一种。如果没有 -funroll-loops，整个 test3 函数的长度为 32 条指令，循环体迭代 24 次。每次迭代与 RAM 交换超过 120 字节的数据（读取和写入的总数）在 6 条指令中。平均每条指令 20 个字节（这真的很近似，我没有仔细看）。

从我的粗略测量来看，这个 double 变体运行s 的内存带宽比原始 int 版本高一个数量级 (!)。

这肯定是一次有趣的冒险。

顺便说一下 - 因为不得不说：现代编译器是工程的奇迹。我没有夸张。您真的必须前往 https://godbolt.org 并亲自尝试一下！

在 C 中展开 For 循环

Unrolling For Loop in C

c

optimization

loop-unrolling