C++优化之谜
Mysteries of C++ optimization
获取以下两个片段：
int main()
{
unsigned long int start = utime();
__int128_t n = 128;
for(__int128_t i=1; i<1000000000; i++)
n = (n * i);
unsigned long int end = utime();
cout<<(unsigned long int) n<<endl;
cout<<end - start<<endl;
}
和
int main()
{
unsigned long int start = utime();
__int128_t n = 128;
for(__int128_t i=1; i<1000000000; i++)
n = (n * i) >> 2;
unsigned long int end = utime();
cout<<(unsigned long int) n<<endl;
cout<<end - start<<endl;
}
我正在用 C++ 对 128 位整数进行基准测试。当执行第一个（只是乘法）时，一切都在大约运行。 0.95 秒。当我还添加移位操作（第二个片段）时，执行时间增加到惊人的 2.49 秒。
这怎么可能？我认为位移位是处理器最轻的操作之一。这么简单的操作怎么会有这么多开销呢？我正在编译时激活 O3 标志。
有什么想法吗？
除非您的处理器可以支持本机 128 位操作，否则这些操作必须通过软件编码才能使用下一个最佳选项。
您的 128 位运算使用与 8 位处理器在使用 16 位运算时相同的方案，这需要时间。
例如，128 位右移一位，使用 64 位寄存器需要：
将最高有效寄存器右移到进位。进位标志将包含移出的位。
将最低有效寄存器右移，带进位。这些位将右移，进位标志被移到最高有效位位置。
如果不支持本机 128 位操作，您的代码将需要两倍于相同 64 位操作的操作；有时更多（例如乘法）。这就是您看到如此糟糕性能的原因。
我强烈建议只在非常需要的地方使用 128 位。
这几天一直困扰着我，所以我决定再调查一下。我最初的回答集中在两个测试之间数据值的差异上。我的断言是，如果其中一个操作数为零，处理器中的整数乘法单元将在更少的时钟周期内完成运算。
虽然有明确记录的指令以这种方式工作（例如整数 除法），但有非常强烈的迹象表明整数乘法是在常数现代处理器中的周期，无论输入如何。英特尔文档中的注释最初让我认为整数乘法的周期数可能取决于输入数据，但似乎不适用于这些指令。此外，我对零和 non-zero 操作数使用相同的指令序列进行了一些更严格的性能测试，结果没有产生显着差异。据我所知， 是正确的。我的错;对不起。
在考虑完全删除此答案的可能性，以便将来不会误导人们时，我意识到关于这个主题还有很多话值得说。我还认为至少还有一种其他方式可以让数据值影响此类计算的性能（包括在最后一节中）。所以，我决定重组和增强我最初答案中的其余信息，开始写作，并且......没有完全停下来。值不值得由你来决定。
信息分为以下部分：
- 代码的作用
- 编译器做什么
- 处理器的作用
- 你能做些什么
- 未回答的问题
代码的作用
它大部分溢出了。
在第一个版本中，n 在第 33 次迭代时开始溢出。在第二个版本中，随着移位，n 在第 52 次迭代开始溢出。
在没有移位的版本中，从第 128 次迭代开始，n 为零（它溢出 "cleanly"，仅在最低有效的 128 位中留下零结果）。
在第二个版本中，右移（除以 4）在每次迭代中从 n 的值中取出比新操作数引入的更多的二因数，因此移位导致某些迭代四舍五入。速算：1到128所有数中二的因数总数等于
128 / 2 + 128 / 4 + ... + 2 + 1 = 26 + 25 + ... + 2 + 1 = 27 - 1
而右移（如果有足够的取自）取出的2的因式个数是128 * 2，多了一倍多。
有了这些知识，我们可以给出第一个答案：从 C++ 标准的角度来看，这段代码大部分时间都在未定义的行为领域，所以所有的赌注都没有了。问题解决了;现在停止阅读。
编译器做什么
如果您仍在阅读，从现在开始我们将忽略溢出并查看一些实现细节。 "The compiler"，在本例中，表示 GCC 4.9.2 或 Clang 3.5.1。我只对 GCC 生成的代码进行了性能测量。对于 Clang，我查看了一些测试用例的生成代码，并注意到了我将在下面提到的一些差异，但实际上我没有 运行 代码；我可能错过了一些事情。
乘法和移位运算均适用于 64 位操作数，因此 128 位操作需要根据这些来实现。一、乘法：n可以写成264nh+nl，其中nh和nl是分别是高 64 位和低 64 位的一半。 i 也是如此。所以，乘法可以写成：
(264 nh + nl)(264 ih + il) = 2128 nh ih + 264 (nh il + nl ih) + nl il
第一项在低 128 位部分没有任何 non-zero 位；它要么全部溢出，要么全为零。由于忽略整数溢出对于 C++ 实现是有效且常见的，因此这就是编译器所做的：完全忽略第一项。
括号仅对 128 位结果的高 64 位贡献位；两次乘法或加法产生的任何溢出也将被忽略（结果 t运行cated 为 64 位）。
最后一项决定了结果的低64位中的位，如果乘法结果超过64位，则需要将额外的位添加到得到的高64位中从前面讨论的括号。 x86-64 汇编中有一个非常有用的乘法指令，它可以完成所需的工作：采用两个 64 位操作数并将结果放入两个 64 位寄存器中，因此高半部分已准备好添加到操作结果中括号。
这就是 128 位整数乘法的实现方式：三个 64 位乘法和两个 64 位加法。
现在，移位：使用与上面相同的符号，nh的两个最低有效位需要成为nl的两个最高有效位，在后者的内容是右移两位。使用 C++ 语法，它看起来像这样：
nl = nh << 62 | nl >> 2 //Doesn't change nh, only uses its bits.
除此之外，nh 也需要移动，使用类似
nh >>= 2;
这就是编译器实现 128 位移位的方式。对于第一部分，有一条 x86-64 指令具有该表达式的确切语义；它叫做 SHRD。使用它可能好也可能坏，正如我们将在下面看到的，两个编译器在这方面做出的选择略有不同。
处理器的作用
... 高度 processor-dependent。 （不……真的吗？！）
关于 Haswell 处理器发生的事情的详细信息可以在 中找到。在这里，我将尝试在更高层次上涵盖更多内容。有关更详细的数据，这里有一些来源：
- Intel® 64 and IA-32 Architectures Optimization Reference Manual
- Software Optimization Guide for AMD Family 15h Processors
- Agner Fog's microarchitecture manual and instruction tables.
我将参考以下架构：
- 英特尔 Sandy Bridge / Ivy Bridge - 缩写 "IntelSB" 前进；
- 英特尔 Haswell / Broadwell - "IntelH" 前进；
- 对于 SB 和 H 之间相同的东西，我将只使用 "Intel"。
- AMD Bulldozer / Piledriver / Steamroller - "AMD" 前进。
我有在 IntelSB 系统上获取的测量数据；我认为它足够精确，只要编译器不出错。不幸的是，当使用如此紧密的循环时，这很容易发生。在测试期间的各个点，我不得不使用各种愚蠢的技巧来避免 GCC 的特性，通常与寄存器使用有关。例如，在编译 比生成最佳汇编的其他情况更简单 代码时，它似乎有一种不必要地混洗寄存器的趋势。具有讽刺意味的是，在我的测试设置中，它倾向于为第二个样本生成最佳代码，使用移位，而为第一个样本生成更差的代码，使得移位的影响不那么明显。 Clang/LLVM 似乎有更少的坏习惯，但话又说回来，我看的使用它的例子更少，而且我没有测量它们中的任何一个，所以这并不意味着什么。为了同类比较，以下所有测量数据均指针对每种情况生成的最佳代码。
首先，让我们将上一节中的 128 位乘法表达式重新排列成一个（可怕的）图表：
nh * il
\
+ -> tmp
/ \
nl * ih + -> next nh
/
high 64 bits
/
nl * il --------
\
low 64 bits
\
-> next nl
（抱歉，我希望它能说明问题）
一些要点：
- 这两个加法只有在它们各自的输入准备好后才能执行；在其他一切准备就绪之前，最后的添加无法执行。
- 理论上，这三个乘法可以并行执行（没有输入取决于另一个乘法的输出）。
- 在上面的理想场景中，一次迭代完成整个计算的总循环次数是一次乘法和两次加法的循环次数之和。
next nl可以早点准备好。这一点，再加上下一个 il 和 ih 的计算成本非常低，意味着下一次迭代的 nl * il 和 nl * ih 计算可以提前开始，可能早于next nh 已经计算出来。
乘法在这些处理器上无法真正完全并行执行，因为每个内核只有一个整数乘法单元，但它们可以通过流水线并发执行。一个乘法可以在 Intel 上的每个周期开始执行，在 AMD 上每 4 个周期开始执行一次，即使之前的乘法尚未完成执行。
以上所有意味着，如果循环体不包含任何其他阻碍，处理器可以重新排序这些乘法以实现尽可能接近上述理想情况的结果。这适用于第一个代码片段。在 IntelH 上，根据 harold 的测量，这正是理想情况：每次迭代 5 个周期由 3 个周期用于一次乘法和一个周期用于两次加法（令人印象深刻，老实说）。在 IntelSB 上，我测量了每次迭代 6 个周期（实际上接近 5.5）。
问题是在第二个代码片段中确实有问题：
nh * il
\ normal shift -> next nh
+ -> tmp /
/ \ /
nl * ih + ----> temp nh
/ \
high 64 bits \
/ "composite" shift -> next nl
nl * il -------- /
\ /
low 64 bits /
\ /
-> temp nl ---------
next nl 不再提前准备好。 temp nl 必须等待 temp nh 准备好，这样才能将两者都送入 composite shift，然后我们才能得到 next nl。即使两个班次都非常快并且并行执行，它们也不只是将一个班次的执行成本添加到迭代中；它们还改变了循环的动态 "pipeline"，就像一种同步屏障。
如果两个班次同时完成，那么下一次迭代的所有三个乘法将同时准备执行，并且它们不能全部并行开始，如上所述；他们将不得不互相等待，浪费周期。在 IntelSB 上就是这种情况，两个班次同样快（见下文）；对于这种情况，我每次迭代测量了 8 个周期。
如果两个班次不同时完成，通常首先完成的是正常班次（复合班次在大多数架构上较慢）。这意味着 next nh 将提前准备好，因此顶层乘法可以为下一次迭代提前开始。但是，其他两个乘法仍然需要等待更多（浪费的）周期才能完成复合移位，然后它们将同时准备就绪，一个将不得不等待另一个开始，浪费更多时间。这是 IntelH 上的情况，由 harold 在每次迭代 9 个周期时测量。
我希望 AMD 也属于最后一类。虽然此平台上的复合移位和正常移位之间的性能差异更大，但 AMD 上的整数乘法也比 Intel 慢（慢两倍以上），使得第一个样本开始时更慢。作为一个非常粗略的估计，我认为第一个版本在 AMD 上可能需要大约 12 个周期，第二个版本大约需要 16 个。不过，如果有一些具体的测量结果会很好。
关于麻烦的复合移位的更多数据，SHRD:
- 在 IntelSB 上，它和简单的转变一样便宜（太棒了！）；简单的班次几乎和它们来的一样便宜：它们在一个周期内执行，两个班次可以在每个周期开始执行。
- 在 IntelH 上，
SHRD 需要 3 个周期来执行（是的，在新一代中它变得更糟），并且任何类型的两个班次（简单或复合）可以开始执行每个周期；
- 在 AMD 上，情况更糟。如果我正确读取数据，执行
SHRD 会使两个轮班执行单元保持忙碌，直到执行完成——没有并行性，也没有可能的流水线；它需要 3 个周期，在此期间没有其他班次可以开始执行。
你能做些什么
我能想到三个可能的改进：
- 在有意义的平台上用更快的东西替换
SHRD；
- 优化乘法以利用此处涉及的数据类型；
- 重构循环。
1. SHRD 可以用两次移位和按位或替换，如编译器部分所述。向右移动两位的 128 位移位的 C++ 实现可能如下所示：
__int128_t shr2(__int128_t n)
{
using std::int64_t;
using std::uint64_t;
//Unpack the two halves.
int64_t nh = n >> 64;
uint64_t nl = static_cast<uint64_t>(n);
//Do the actual work.
uint64_t rl = nl >> 2 | nh << 62;
int64_t rh = nh >> 2;
//Pack the result.
return static_cast<__int128_t>(rh) << 64 | rl;
}
虽然看起来很多代码，但只有中间部分执行实际工作会生成班次和 OR。其他部分仅向编译器指示我们要使用哪些 64 位部分；由于 64 位部分已经在单独的寄存器中，因此在生成的汇编代码中它们实际上是 no-ops。
但是，请记住，这相当于 "trying to write assembly using C++ syntax"，这通常不是一个好主意。我之所以使用它，是因为我已验证它适用于 GCC，并且我试图将此答案中的汇编代码量保持在最低限度。即便如此，还是有一个惊喜：LLVM 优化器检测到我们试图用这两个班次和一个 OR 和...在某些情况下用 SHRD 替换它们（下面有更多相关信息）。
相同形式的函数可用于移位其他位数，小于 64。从 64 到 127，它变得更容易，但形式发生了变化。要记住的一件事是，将要移位的位数作为 运行time 参数传递给 shr 函数是错误的。在大多数体系结构上，可变位数的移位指令比使用常量的指令慢。您可以使用 non-type 模板参数在编译时生成不同的函数 - 毕竟这是 C++...
我认为使用这样的函数在除 IntelSB 之外的所有架构上都有意义，其中 SHRD 已经达到了它所能达到的最快速度。在 AMD 上，它肯定会有所改进。 IntelH 就不太一样了：对于我们的案例，我不认为它会产生什么影响，但通常它可以在一些计算循环结束后削减；理论上可能存在它会使事情变得更糟的情况，但我认为这些情况非常罕见（像往常一样，没有什么可以替代测量）。我认为这不会对我们的循环产生影响，因为它会将事情从 [nh 在一次循环后准备就绪和 nl 在三个循环后准备好] 更改为 [都在两次后准备就绪]；这意味着下一次迭代的所有三个乘法将同时准备就绪，它们将不得不相互等待，基本上浪费了通过轮班获得的周期。
GCC 似乎在所有体系结构上都使用 SHRD，上面的 "assembly in C++" 代码可以用作有意义的优化。 LLVM 优化器使用更细微的方法：它自动为 AMD 优化（替换 SHRD），但不为 Intel 优化，它甚至会反转它，如上所述。正如实现此优化的 the patch for LLVM 上的讨论所示，这可能会在未来的版本中发生变化。现在，如果你想在 Intel 上使用 LLVM 的替代方案，你将不得不求助于汇编代码。
2.乘法优化：测试代码对i使用128位整数，但本例不需要，因为它的值很容易拟合64 位（实际上是 32 位，但这对我们没有帮助）。这意味着 ih 将始终为零；这将 128 位乘法图简化为以下内容：
nh * il
\
\
\
+ -> next nh
/
high 64 bits
/
nl * il
\
low 64 bits
\
-> next nl
通常，我会说 "declare i as long long and let the compiler optimize things" 但不幸的是，这在这里不起作用；两个编译器都采用标准行为，在计算之前将两个操作数转换为它们的通用类型，因此 i 以 128 位结束，即使它从 64 位开始。我们将不得不以艰难的方式做事：
__int128_t mul(__int128_t n, long long i)
{
using std::int64_t;
using std::uint64_t;
//Unpack the two halves.
int64_t nh = n >> 64;
uint64_t nl = static_cast<uint64_t>(n);
//Do the actual work.
__asm__(R"(
movq %0, %%r10
imulq %2, %%r10
mulq %2
addq %%r10, %0
)" : "+d"(nh), "+a"(nl) : "r"(i) : "%r10");
//Pack the result.
return static_cast<__int128_t>(nh) << 64 | nl;
}
我说过我试图在这个答案中避免汇编代码，但这并不总是可能的。我设法哄骗 GCC 为上面的函数生成带有 "assembly in C++" 的正确代码，但是一旦函数被内联，一切都会分崩离析——优化器会看到整个循环体中发生了什么，并将所有内容转换为 128 位。 LLVM 似乎在这种情况下表现良好，但是，由于我在 GCC 上进行测试，所以我必须使用可靠的方法来获取正确的代码。
将 i 声明为 long long 并使用此函数代替普通乘法运算符，我在 IntelSB 上测量了第一个样本每次迭代 5 个周期，第二个样本每次迭代 7 个周期，一个增益在每种情况下一个周期。我希望它也能为 IntelH 上的两个示例减少一个迭代周期。
3. 循环有时可以重组以鼓励流水线执行，当（至少一些）迭代并不真正依赖于以前的结果时，即使它看起来像他们是这样。例如，我们可以将第二个示例的 for 循环替换为如下内容：
__int128_t n2 = 1;
long long j = 1000000000 / 2;
for(long long i = 1; i < 1000000000 / 2; ++i, ++j)
{
n *= i;
n2 *= j;
n >>= 2;
n2 >>= 2;
}
n *= (n2 * j) >> 2;
这利用了一些部分结果可以独立计算并且只在最后汇总的事实。我们还向编译器暗示我们希望对乘法和移位进行流水线处理（并非总是必要，但对于这段代码的 GCC 来说确实有一点不同）。
上面的代码只不过是一个简单的概念验证。真正的代码需要以更可靠的方式处理迭代总数。更大的问题是此代码不会生成与原始代码相同的结果，因为存在溢出和舍入时的行为不同。即使我们在第 51 次迭代时停止循环，以避免溢出，结果仍然会有大约 10% 的差异，因为右移时舍入的方式不同。在实际代码中，这很可能是个问题；但话又说回来，你不会有这样的真实代码，对吗？
假设这种技术适用于不会出现上述问题的情况，我再次在 IntelSB 上测量了这种代码在一些情况下的性能。结果在 "cycles per iteration" 中给出，和之前一样，其中 "iteration" 表示来自原始代码的结果（我将执行整个循环的循环总数除以原始执行的迭代总数代码，而不是重组后的代码，以进行有意义的比较）：
- 上面的代码每次迭代执行 7 个周期，比原来的增加了一个周期。
- 上面的代码用我们的
mul() 函数替换了乘法运算符，每次迭代需要 6 个周期。
重组后的代码确实遭受了更多的寄存器改组，不幸的是这是无法避免的（更多变量）。 IntelH 等较新的处理器进行了架构改进，在许多情况下基本上可以免费移动寄存器；这可以使代码产生更大的收益。为 IntelH 使用 MULX 等新指令可以完全避免一些寄存器移动； GCC 在用 -march=haswell.
编译时确实使用了这样的指令
未回答的问题
None 我们迄今为止的测量结果解释了 OP 报告的以及我在不同系统上观察到的巨大性能差异。
我的初始计时是在远程系统（Westmere 系列处理器）上进行的，当然，很多事情都可能发生；然而，结果出奇地稳定。
在那个系统上，我还尝试用右移和左移执行第二个示例；使用右移的代码始终比其他变体慢 50%。我无法在 IntelSB 上的受控测试系统上复制它，而且我也没有对这些结果的解释。
我们可以将以上所有内容视为编译器/处理器/整体系统行为的不可预测的副作用，但我无法摆脱这里并未解释所有内容的感觉。
确实，如果没有受控系统、精确的工具（计算周期）和查看为每种情况生成的汇编代码，那么对如此紧密的循环进行基准测试并没有多大意义。编译器的特性很容易导致代码人为地引入 50% 或更多的性能差异。
另一个可以解释巨大差异的因素是英特尔 Hyper-Threading 的存在。启用此功能时，内核的不同部分表现不同，并且处理器系列之间的行为也发生了变化。这可能会对紧密循环产生奇怪的影响。
最重要的是，这里有一个疯狂的假设：翻转位比保持不变消耗更多的能量。在我们的例子中，第一个样本大部分时间都使用零值，翻转的位数将比第二个样本少得多，因此后者会消耗更多的功率。许多现代处理器具有根据电气和热限制动态调整核心频率的功能（Intel Turbo Boost / AMD Turbo Core）。这意味着，理论上，在正确（或错误？）条件下，第二个样本可以触发核心频率的降低，从而使相同数量的周期花费更长的时间，并使性能 data-dependent.
在我的 4770K 上对两者进行基准测试（使用 GCC 4.7.3 在 -O2 上生成的程序集）后，我发现第一个每次迭代需要 5 个周期，第二个每次迭代需要 9 个周期。为什么差别这么大？
事实证明这是吞吐量和延迟之间的相互作用。主要杀手是shrd，需要3个周期，在关键路径上。这是它的图片（我忽略了 i 的链，因为它更快并且有足够的空闲吞吐量供它向前 运行，它不会干扰）：
这里的边是依赖关系，不是数据流。
仅基于此链中的延迟，预期时间为每次迭代 8 个周期。但事实并非如此。这里的问题是要发生 8 个周期，mul2 和 imul3 必须并行执行，整数乘法只有 1 个/周期的吞吐量。所以它（其中一个）必须等待一个周期，并通过一个周期来支撑链条。我通过将 imul 更改为 add 来验证这一点，这将每次迭代的时间减少到 8 个周期。将另一个 imul 更改为 add 没有效果，正如基于此解释所预测的那样（它不依赖于 shrd 因此可以提前安排，而不会干扰其他乘法).
这些确切的细节仅适用于 Haswell。
我使用的代码是这样的：
section .text
global cmp1
proc_frame cmp1
[endprolog]
mov r8, rsi
mov r9, rdi
mov esi, 1
xor edi, edi
mov eax, 128
xor edx, edx
.L2:
mov rcx, rdx
mov rdx, rdi
imul rdx, rax
imul rcx, rsi
add rcx, rdx
mul rsi
add rdx, rcx
add rsi, 1
mov rcx, rsi
adc rdi, 0
xor rcx, 10000000
or rcx, rdi
jne .L2
mov rdi, r9
mov rsi, r8
ret
endproc_frame
global cmp2
proc_frame cmp2
[endprolog]
mov r8, rsi
mov r9, rdi
mov esi, 1
xor edi, edi
mov eax, 128
xor edx, edx
.L3:
mov rcx, rdi
imul rcx, rax
imul rdx, rsi
add rcx, rdx
mul rsi
add rdx, rcx
shrd rax, rdx, 2
sar rdx, 2
add rsi, 1
mov rcx, rsi
adc rdi, 0
xor rcx, 10000000
or rcx, rdi
jne .L3
mov rdi, r9
mov rsi, r8
ret
endproc_frame
获取以下两个片段：
int main()
{
unsigned long int start = utime();
__int128_t n = 128;
for(__int128_t i=1; i<1000000000; i++)
n = (n * i);
unsigned long int end = utime();
cout<<(unsigned long int) n<<endl;
cout<<end - start<<endl;
}
和
int main()
{
unsigned long int start = utime();
__int128_t n = 128;
for(__int128_t i=1; i<1000000000; i++)
n = (n * i) >> 2;
unsigned long int end = utime();
cout<<(unsigned long int) n<<endl;
cout<<end - start<<endl;
}
我正在用 C++ 对 128 位整数进行基准测试。当执行第一个（只是乘法）时，一切都在大约运行。 0.95 秒。当我还添加移位操作（第二个片段）时，执行时间增加到惊人的 2.49 秒。
这怎么可能？我认为位移位是处理器最轻的操作之一。这么简单的操作怎么会有这么多开销呢？我正在编译时激活 O3 标志。
有什么想法吗？
除非您的处理器可以支持本机 128 位操作，否则这些操作必须通过软件编码才能使用下一个最佳选项。
您的 128 位运算使用与 8 位处理器在使用 16 位运算时相同的方案，这需要时间。
例如，128 位右移一位，使用 64 位寄存器需要：
将最高有效寄存器右移到进位。进位标志将包含移出的位。
将最低有效寄存器右移，带进位。这些位将右移，进位标志被移到最高有效位位置。
如果不支持本机 128 位操作，您的代码将需要两倍于相同 64 位操作的操作；有时更多（例如乘法）。这就是您看到如此糟糕性能的原因。
我强烈建议只在非常需要的地方使用 128 位。
这几天一直困扰着我，所以我决定再调查一下。我最初的回答集中在两个测试之间数据值的差异上。我的断言是，如果其中一个操作数为零，处理器中的整数乘法单元将在更少的时钟周期内完成运算。
虽然有明确记录的指令以这种方式工作（例如整数 除法），但有非常强烈的迹象表明整数乘法是在常数现代处理器中的周期，无论输入如何。英特尔文档中的注释最初让我认为整数乘法的周期数可能取决于输入数据，但似乎不适用于这些指令。此外，我对零和 non-zero 操作数使用相同的指令序列进行了一些更严格的性能测试，结果没有产生显着差异。据我所知，
在考虑完全删除此答案的可能性，以便将来不会误导人们时，我意识到关于这个主题还有很多话值得说。我还认为至少还有一种其他方式可以让数据值影响此类计算的性能（包括在最后一节中）。所以，我决定重组和增强我最初答案中的其余信息，开始写作，并且......没有完全停下来。值不值得由你来决定。
信息分为以下部分：
- 代码的作用
- 编译器做什么
- 处理器的作用
- 你能做些什么
- 未回答的问题
代码的作用
它大部分溢出了。
在第一个版本中，n 在第 33 次迭代时开始溢出。在第二个版本中，随着移位，n 在第 52 次迭代开始溢出。
在没有移位的版本中，从第 128 次迭代开始，n 为零（它溢出 "cleanly"，仅在最低有效的 128 位中留下零结果）。
在第二个版本中，右移（除以 4）在每次迭代中从 n 的值中取出比新操作数引入的更多的二因数，因此移位导致某些迭代四舍五入。速算：1到128所有数中二的因数总数等于
128 / 2 + 128 / 4 + ... + 2 + 1 = 26 + 25 + ... + 2 + 1 = 27 - 1
而右移（如果有足够的取自）取出的2的因式个数是128 * 2，多了一倍多。
有了这些知识，我们可以给出第一个答案：从 C++ 标准的角度来看，这段代码大部分时间都在未定义的行为领域，所以所有的赌注都没有了。问题解决了;现在停止阅读。
编译器做什么
如果您仍在阅读，从现在开始我们将忽略溢出并查看一些实现细节。 "The compiler"，在本例中，表示 GCC 4.9.2 或 Clang 3.5.1。我只对 GCC 生成的代码进行了性能测量。对于 Clang，我查看了一些测试用例的生成代码，并注意到了我将在下面提到的一些差异，但实际上我没有 运行 代码；我可能错过了一些事情。
乘法和移位运算均适用于 64 位操作数，因此 128 位操作需要根据这些来实现。一、乘法：n可以写成264nh+nl，其中nh和nl是分别是高 64 位和低 64 位的一半。 i 也是如此。所以，乘法可以写成：
(264 nh + nl)(264 ih + il) = 2128 nh ih + 264 (nh il + nl ih) + nl il
第一项在低 128 位部分没有任何 non-zero 位；它要么全部溢出，要么全为零。由于忽略整数溢出对于 C++ 实现是有效且常见的，因此这就是编译器所做的：完全忽略第一项。
括号仅对 128 位结果的高 64 位贡献位；两次乘法或加法产生的任何溢出也将被忽略（结果 t运行cated 为 64 位）。
最后一项决定了结果的低64位中的位，如果乘法结果超过64位，则需要将额外的位添加到得到的高64位中从前面讨论的括号。 x86-64 汇编中有一个非常有用的乘法指令，它可以完成所需的工作：采用两个 64 位操作数并将结果放入两个 64 位寄存器中，因此高半部分已准备好添加到操作结果中括号。
这就是 128 位整数乘法的实现方式：三个 64 位乘法和两个 64 位加法。
现在，移位：使用与上面相同的符号，nh的两个最低有效位需要成为nl的两个最高有效位，在后者的内容是右移两位。使用 C++ 语法，它看起来像这样：
nl = nh << 62 | nl >> 2 //Doesn't change nh, only uses its bits.
除此之外，nh 也需要移动，使用类似
nh >>= 2;
这就是编译器实现 128 位移位的方式。对于第一部分，有一条 x86-64 指令具有该表达式的确切语义；它叫做 SHRD。使用它可能好也可能坏，正如我们将在下面看到的，两个编译器在这方面做出的选择略有不同。
处理器的作用
... 高度 processor-dependent。 （不……真的吗？！）
关于 Haswell 处理器发生的事情的详细信息可以在
- Intel® 64 and IA-32 Architectures Optimization Reference Manual
- Software Optimization Guide for AMD Family 15h Processors
- Agner Fog's microarchitecture manual and instruction tables.
我将参考以下架构：
- 英特尔 Sandy Bridge / Ivy Bridge - 缩写 "IntelSB" 前进；
- 英特尔 Haswell / Broadwell - "IntelH" 前进；
- 对于 SB 和 H 之间相同的东西，我将只使用 "Intel"。
- AMD Bulldozer / Piledriver / Steamroller - "AMD" 前进。
我有在 IntelSB 系统上获取的测量数据；我认为它足够精确，只要编译器不出错。不幸的是，当使用如此紧密的循环时，这很容易发生。在测试期间的各个点，我不得不使用各种愚蠢的技巧来避免 GCC 的特性，通常与寄存器使用有关。例如，在编译 比生成最佳汇编的其他情况更简单 代码时，它似乎有一种不必要地混洗寄存器的趋势。具有讽刺意味的是，在我的测试设置中，它倾向于为第二个样本生成最佳代码，使用移位，而为第一个样本生成更差的代码，使得移位的影响不那么明显。 Clang/LLVM 似乎有更少的坏习惯，但话又说回来，我看的使用它的例子更少，而且我没有测量它们中的任何一个，所以这并不意味着什么。为了同类比较，以下所有测量数据均指针对每种情况生成的最佳代码。
首先，让我们将上一节中的 128 位乘法表达式重新排列成一个（可怕的）图表：
nh * il
\
+ -> tmp
/ \
nl * ih + -> next nh
/
high 64 bits
/
nl * il --------
\
low 64 bits
\
-> next nl
（抱歉，我希望它能说明问题）
一些要点：
- 这两个加法只有在它们各自的输入准备好后才能执行；在其他一切准备就绪之前，最后的添加无法执行。
- 理论上，这三个乘法可以并行执行（没有输入取决于另一个乘法的输出）。
- 在上面的理想场景中，一次迭代完成整个计算的总循环次数是一次乘法和两次加法的循环次数之和。
next nl可以早点准备好。这一点，再加上下一个il和ih的计算成本非常低，意味着下一次迭代的nl * il和nl * ih计算可以提前开始，可能早于next nh已经计算出来。
乘法在这些处理器上无法真正完全并行执行，因为每个内核只有一个整数乘法单元，但它们可以通过流水线并发执行。一个乘法可以在 Intel 上的每个周期开始执行，在 AMD 上每 4 个周期开始执行一次，即使之前的乘法尚未完成执行。
以上所有意味着，如果循环体不包含任何其他阻碍，处理器可以重新排序这些乘法以实现尽可能接近上述理想情况的结果。这适用于第一个代码片段。在 IntelH 上，根据 harold 的测量，这正是理想情况：每次迭代 5 个周期由 3 个周期用于一次乘法和一个周期用于两次加法（令人印象深刻，老实说）。在 IntelSB 上，我测量了每次迭代 6 个周期（实际上接近 5.5）。
问题是在第二个代码片段中确实有问题：
nh * il
\ normal shift -> next nh
+ -> tmp /
/ \ /
nl * ih + ----> temp nh
/ \
high 64 bits \
/ "composite" shift -> next nl
nl * il -------- /
\ /
low 64 bits /
\ /
-> temp nl ---------
next nl 不再提前准备好。 temp nl 必须等待 temp nh 准备好，这样才能将两者都送入 composite shift，然后我们才能得到 next nl。即使两个班次都非常快并且并行执行，它们也不只是将一个班次的执行成本添加到迭代中；它们还改变了循环的动态 "pipeline"，就像一种同步屏障。
如果两个班次同时完成，那么下一次迭代的所有三个乘法将同时准备执行，并且它们不能全部并行开始，如上所述；他们将不得不互相等待，浪费周期。在 IntelSB 上就是这种情况，两个班次同样快（见下文）；对于这种情况，我每次迭代测量了 8 个周期。
如果两个班次不同时完成，通常首先完成的是正常班次（复合班次在大多数架构上较慢）。这意味着 next nh 将提前准备好，因此顶层乘法可以为下一次迭代提前开始。但是，其他两个乘法仍然需要等待更多（浪费的）周期才能完成复合移位，然后它们将同时准备就绪，一个将不得不等待另一个开始，浪费更多时间。这是 IntelH 上的情况，由 harold 在每次迭代 9 个周期时测量。
我希望 AMD 也属于最后一类。虽然此平台上的复合移位和正常移位之间的性能差异更大，但 AMD 上的整数乘法也比 Intel 慢（慢两倍以上），使得第一个样本开始时更慢。作为一个非常粗略的估计，我认为第一个版本在 AMD 上可能需要大约 12 个周期，第二个版本大约需要 16 个。不过，如果有一些具体的测量结果会很好。
关于麻烦的复合移位的更多数据，SHRD:
- 在 IntelSB 上，它和简单的转变一样便宜（太棒了！）；简单的班次几乎和它们来的一样便宜：它们在一个周期内执行，两个班次可以在每个周期开始执行。
- 在 IntelH 上，
SHRD需要 3 个周期来执行（是的，在新一代中它变得更糟），并且任何类型的两个班次（简单或复合）可以开始执行每个周期； - 在 AMD 上，情况更糟。如果我正确读取数据，执行
SHRD会使两个轮班执行单元保持忙碌，直到执行完成——没有并行性，也没有可能的流水线；它需要 3 个周期，在此期间没有其他班次可以开始执行。
你能做些什么
我能想到三个可能的改进：
- 在有意义的平台上用更快的东西替换
SHRD； - 优化乘法以利用此处涉及的数据类型；
- 重构循环。
1. SHRD 可以用两次移位和按位或替换，如编译器部分所述。向右移动两位的 128 位移位的 C++ 实现可能如下所示：
__int128_t shr2(__int128_t n)
{
using std::int64_t;
using std::uint64_t;
//Unpack the two halves.
int64_t nh = n >> 64;
uint64_t nl = static_cast<uint64_t>(n);
//Do the actual work.
uint64_t rl = nl >> 2 | nh << 62;
int64_t rh = nh >> 2;
//Pack the result.
return static_cast<__int128_t>(rh) << 64 | rl;
}
虽然看起来很多代码，但只有中间部分执行实际工作会生成班次和 OR。其他部分仅向编译器指示我们要使用哪些 64 位部分；由于 64 位部分已经在单独的寄存器中，因此在生成的汇编代码中它们实际上是 no-ops。
但是，请记住，这相当于 "trying to write assembly using C++ syntax"，这通常不是一个好主意。我之所以使用它，是因为我已验证它适用于 GCC，并且我试图将此答案中的汇编代码量保持在最低限度。即便如此，还是有一个惊喜：LLVM 优化器检测到我们试图用这两个班次和一个 OR 和...在某些情况下用 SHRD 替换它们（下面有更多相关信息）。
相同形式的函数可用于移位其他位数，小于 64。从 64 到 127，它变得更容易，但形式发生了变化。要记住的一件事是，将要移位的位数作为 运行time 参数传递给 shr 函数是错误的。在大多数体系结构上，可变位数的移位指令比使用常量的指令慢。您可以使用 non-type 模板参数在编译时生成不同的函数 - 毕竟这是 C++...
我认为使用这样的函数在除 IntelSB 之外的所有架构上都有意义，其中 SHRD 已经达到了它所能达到的最快速度。在 AMD 上，它肯定会有所改进。 IntelH 就不太一样了：对于我们的案例，我不认为它会产生什么影响，但通常它可以在一些计算循环结束后削减；理论上可能存在它会使事情变得更糟的情况，但我认为这些情况非常罕见（像往常一样，没有什么可以替代测量）。我认为这不会对我们的循环产生影响，因为它会将事情从 [nh 在一次循环后准备就绪和 nl 在三个循环后准备好] 更改为 [都在两次后准备就绪]；这意味着下一次迭代的所有三个乘法将同时准备就绪，它们将不得不相互等待，基本上浪费了通过轮班获得的周期。
GCC 似乎在所有体系结构上都使用 SHRD，上面的 "assembly in C++" 代码可以用作有意义的优化。 LLVM 优化器使用更细微的方法：它自动为 AMD 优化（替换 SHRD），但不为 Intel 优化，它甚至会反转它，如上所述。正如实现此优化的 the patch for LLVM 上的讨论所示，这可能会在未来的版本中发生变化。现在，如果你想在 Intel 上使用 LLVM 的替代方案，你将不得不求助于汇编代码。
2.乘法优化：测试代码对i使用128位整数，但本例不需要，因为它的值很容易拟合64 位（实际上是 32 位，但这对我们没有帮助）。这意味着 ih 将始终为零；这将 128 位乘法图简化为以下内容：
nh * il
\
\
\
+ -> next nh
/
high 64 bits
/
nl * il
\
low 64 bits
\
-> next nl
通常，我会说 "declare i as long long and let the compiler optimize things" 但不幸的是，这在这里不起作用；两个编译器都采用标准行为，在计算之前将两个操作数转换为它们的通用类型，因此 i 以 128 位结束，即使它从 64 位开始。我们将不得不以艰难的方式做事：
__int128_t mul(__int128_t n, long long i)
{
using std::int64_t;
using std::uint64_t;
//Unpack the two halves.
int64_t nh = n >> 64;
uint64_t nl = static_cast<uint64_t>(n);
//Do the actual work.
__asm__(R"(
movq %0, %%r10
imulq %2, %%r10
mulq %2
addq %%r10, %0
)" : "+d"(nh), "+a"(nl) : "r"(i) : "%r10");
//Pack the result.
return static_cast<__int128_t>(nh) << 64 | nl;
}
我说过我试图在这个答案中避免汇编代码，但这并不总是可能的。我设法哄骗 GCC 为上面的函数生成带有 "assembly in C++" 的正确代码，但是一旦函数被内联，一切都会分崩离析——优化器会看到整个循环体中发生了什么，并将所有内容转换为 128 位。 LLVM 似乎在这种情况下表现良好，但是，由于我在 GCC 上进行测试，所以我必须使用可靠的方法来获取正确的代码。
将 i 声明为 long long 并使用此函数代替普通乘法运算符，我在 IntelSB 上测量了第一个样本每次迭代 5 个周期，第二个样本每次迭代 7 个周期，一个增益在每种情况下一个周期。我希望它也能为 IntelH 上的两个示例减少一个迭代周期。
3. 循环有时可以重组以鼓励流水线执行，当（至少一些）迭代并不真正依赖于以前的结果时，即使它看起来像他们是这样。例如，我们可以将第二个示例的 for 循环替换为如下内容：
__int128_t n2 = 1;
long long j = 1000000000 / 2;
for(long long i = 1; i < 1000000000 / 2; ++i, ++j)
{
n *= i;
n2 *= j;
n >>= 2;
n2 >>= 2;
}
n *= (n2 * j) >> 2;
这利用了一些部分结果可以独立计算并且只在最后汇总的事实。我们还向编译器暗示我们希望对乘法和移位进行流水线处理（并非总是必要，但对于这段代码的 GCC 来说确实有一点不同）。
上面的代码只不过是一个简单的概念验证。真正的代码需要以更可靠的方式处理迭代总数。更大的问题是此代码不会生成与原始代码相同的结果，因为存在溢出和舍入时的行为不同。即使我们在第 51 次迭代时停止循环，以避免溢出，结果仍然会有大约 10% 的差异，因为右移时舍入的方式不同。在实际代码中，这很可能是个问题；但话又说回来，你不会有这样的真实代码，对吗？
假设这种技术适用于不会出现上述问题的情况，我再次在 IntelSB 上测量了这种代码在一些情况下的性能。结果在 "cycles per iteration" 中给出，和之前一样，其中 "iteration" 表示来自原始代码的结果（我将执行整个循环的循环总数除以原始执行的迭代总数代码，而不是重组后的代码，以进行有意义的比较）：
- 上面的代码每次迭代执行 7 个周期，比原来的增加了一个周期。
- 上面的代码用我们的
mul()函数替换了乘法运算符，每次迭代需要 6 个周期。
重组后的代码确实遭受了更多的寄存器改组，不幸的是这是无法避免的（更多变量）。 IntelH 等较新的处理器进行了架构改进，在许多情况下基本上可以免费移动寄存器；这可以使代码产生更大的收益。为 IntelH 使用 MULX 等新指令可以完全避免一些寄存器移动； GCC 在用 -march=haswell.
未回答的问题
None 我们迄今为止的测量结果解释了 OP 报告的以及我在不同系统上观察到的巨大性能差异。
我的初始计时是在远程系统（Westmere 系列处理器）上进行的，当然，很多事情都可能发生；然而，结果出奇地稳定。
在那个系统上，我还尝试用右移和左移执行第二个示例；使用右移的代码始终比其他变体慢 50%。我无法在 IntelSB 上的受控测试系统上复制它，而且我也没有对这些结果的解释。
我们可以将以上所有内容视为编译器/处理器/整体系统行为的不可预测的副作用，但我无法摆脱这里并未解释所有内容的感觉。
确实，如果没有受控系统、精确的工具（计算周期）和查看为每种情况生成的汇编代码，那么对如此紧密的循环进行基准测试并没有多大意义。编译器的特性很容易导致代码人为地引入 50% 或更多的性能差异。
另一个可以解释巨大差异的因素是英特尔 Hyper-Threading 的存在。启用此功能时，内核的不同部分表现不同，并且处理器系列之间的行为也发生了变化。这可能会对紧密循环产生奇怪的影响。
最重要的是，这里有一个疯狂的假设：翻转位比保持不变消耗更多的能量。在我们的例子中，第一个样本大部分时间都使用零值，翻转的位数将比第二个样本少得多，因此后者会消耗更多的功率。许多现代处理器具有根据电气和热限制动态调整核心频率的功能（Intel Turbo Boost / AMD Turbo Core）。这意味着，理论上，在正确（或错误？）条件下，第二个样本可以触发核心频率的降低，从而使相同数量的周期花费更长的时间，并使性能 data-dependent.
在我的 4770K 上对两者进行基准测试（使用 GCC 4.7.3 在 -O2 上生成的程序集）后，我发现第一个每次迭代需要 5 个周期，第二个每次迭代需要 9 个周期。为什么差别这么大？
事实证明这是吞吐量和延迟之间的相互作用。主要杀手是shrd，需要3个周期，在关键路径上。这是它的图片（我忽略了 i 的链，因为它更快并且有足够的空闲吞吐量供它向前 运行，它不会干扰）：
这里的边是依赖关系，不是数据流。
仅基于此链中的延迟，预期时间为每次迭代 8 个周期。但事实并非如此。这里的问题是要发生 8 个周期，mul2 和 imul3 必须并行执行，整数乘法只有 1 个/周期的吞吐量。所以它（其中一个）必须等待一个周期，并通过一个周期来支撑链条。我通过将 imul 更改为 add 来验证这一点，这将每次迭代的时间减少到 8 个周期。将另一个 imul 更改为 add 没有效果，正如基于此解释所预测的那样（它不依赖于 shrd 因此可以提前安排，而不会干扰其他乘法).
这些确切的细节仅适用于 Haswell。
我使用的代码是这样的：
section .text
global cmp1
proc_frame cmp1
[endprolog]
mov r8, rsi
mov r9, rdi
mov esi, 1
xor edi, edi
mov eax, 128
xor edx, edx
.L2:
mov rcx, rdx
mov rdx, rdi
imul rdx, rax
imul rcx, rsi
add rcx, rdx
mul rsi
add rdx, rcx
add rsi, 1
mov rcx, rsi
adc rdi, 0
xor rcx, 10000000
or rcx, rdi
jne .L2
mov rdi, r9
mov rsi, r8
ret
endproc_frame
global cmp2
proc_frame cmp2
[endprolog]
mov r8, rsi
mov r9, rdi
mov esi, 1
xor edi, edi
mov eax, 128
xor edx, edx
.L3:
mov rcx, rdi
imul rcx, rax
imul rdx, rsi
add rcx, rdx
mul rsi
add rdx, rcx
shrd rax, rdx, 2
sar rdx, 2
add rsi, 1
mov rcx, rsi
adc rdi, 0
xor rcx, 10000000
or rcx, rdi
jne .L3
mov rdi, r9
mov rsi, r8
ret
endproc_frame