可以更快地执行更复杂的循环吗？

Question

我在准备在 C++ 中实现类似 python 的 ",".join(vector) 函数时发现了这一点。我想比较消除用于避免在字符串开头放置额外 ',' 的内部 if first element 条件是否有意义。我写了以下函数：

long long test1() // 38332ms
{
    long long k = 0;
    for (long long i = 0; i < 10000000000; ++i)
    {
        if (i != 0)
        {
            k += 2;
        }
        k += 1;
    }

    return k;
}

long long test2() // 45272ms
{
    long long k = 0;
    k += 1;
    for (long long i = 1; i < 10000000000; ++i)
    {
        k += 2; // in the real code it might be impossible to merge
        k += 1; // those operations
    }

    return k;
}

我使用简化代码使条件跳转更有意义。我期望分支预测能够最小化差异。令我惊讶的是，第一个功能表现得更好。我正在测试 VS2015 下的调试设置。编译器没有执行任何优化——我检查了程序集。我还尝试移动一些东西——移动函数定义、调用顺序、限制常数。比例大致相同。

可能的解释是什么？

编辑：我没有分析这个特定的场景，而是试图得到一些关于这种行为的可能原因的通用答案。我的猜测是 CPU 在分支预测期间执行某种启发式方法，并且在我的特定情况下，我的特定 CPU 更擅长预测 test1 中的这个分支。这只是我的直觉，所以我在犹豫它是否正确。有没有人考虑一下我的猜测？

Answer 1

因为你在调试模式下编译，你的循环可能 stores/reloads k 到内存每次迭代（循环计数器也是如此）。未优化代码中的微小循环通常是存储转发延迟的瓶颈（在 Intel Haswell 上约为 5 个周期），而不是任何类型的吞吐量瓶颈。

My guess is that CPU is performing some kind of heuristics during the branch prediction and that in my specific case the my specific CPU was better at predicting this branch in the test1.

这说不通。完美的分支预测可以将分支的成本降低到零，而不是使其为负。

即执行两个 ADD 指令 + 一个分支不会比只执行两个 ADD insn 更快，除非还有其他不同的东西。

据推测，处于调试模式的 MSVC 最终为 test1 编写的代码比为 test2 编写的代码要好。也许它在一个增量中将 k 保存在寄存器中，而不是使用内存目标进行两个增量？

如果您发布了 asm，可能会告诉您编译器的不同之处使第一个版本运行更快，但这不会有用或有趣。（并且与分支预测无关；它应该预测至少有 99.999% 的成功率，所以实际的分支指令几乎是免费的。）

Read Agner Fog's microarch pdf 如果您想了解 CPU 的内部工作原理，以及如何预测汇编指令循环的速度运行.

参见为什么它毫无意义且浪费时间，并且对于了解什么是快什么是慢没有用。

优化不仅会以常数因子加快一切速度，还会改变您将遇到的瓶颈类型。（例如 k 将存在于寄存器中，因此 k+=1 仅具有 ADD 指令的延迟，而不是内存往返的延迟）。当然，合并成 k+=3，并证明 i!=0 分支只发生一次，然后剥离该迭代。

更重要的是，结果是编译时常量，因此理想情况下，两个函数都将编译为一条指令，将结果放入 return 值寄存器。不幸的是，gcc6.2、clang3.9 和 icc17 都无法为版本 1 执行此操作，因此看起来手动剥离第一次迭代非常有帮助。

但是对于 test2，所有编译器都可以轻松地将其编译为 movabs rax, 29999999998 / ret.

相关：优化编译器对这些函数做了什么

如果您想查看编译器输出，请使用函数参数而不是常量。你已经return结果了，很好。

我把你的函数放在 the Godbolt Compiler explorer 上（它最近添加了比 icc13 更新的英特尔编译器版本）。

clang-3.9 愚蠢地将 cmov 用于 test1，从 -O1 到 -O3。一个可预测的分支最好用跳跃来完成，如果它没有被完全剥离的话。（也许无符号循环计数器/上限会帮助编译器弄清楚发生了什么，但我没有尝试。）

gcc 对 test1 使用条件分支，对 test2 使用函数参数计数器版本。分支看起来很合理，i!=0 的情况是 CMP/JE 的失败未采用的一侧。但它实际上仍然将循环计数器计数到最大值，并递增 k.

在 test2 gcc 中运行增加循环计数器并在循环外将其相乘。

ICC17 非常积极地展开 test1，使用多个整数寄存器作为累加器，因此多个 ADD 或 INC 可以并行发生。 IDK 如果它有帮助的话，因为它溢出了它的一个累加器，带有一个内存目标 ADD。实际上，我认为它展开得足够多了，因为内存目标 ADD（在 Intel Haswell 上）的瓶颈，而不是整数 ALU ADD/INC 上的瓶颈，~20 uop 循环每次迭代仅从 5 到 6 个周期减慢指令（Haswell 上每个时钟 4 个）。它在不同的寄存器中执行 +=2 和 +=1，并在最后组合（我假设，我只是查看了具有 cmp rdx, 1249999999 结束条件的循环。有趣的是它如何积极地设法优化循环而没有只是像 test2 一样将它优化到一个常数。

可以更快地执行更复杂的循环吗？

Can more complex loop be executed faster?

c++

loops

cpu-architecture

branch-prediction