汇编中的条件数据传输和条件控制传输（使用条件 mov）

Question

您好，我正在阅读一本比较条件数据传输的教科书和汇编中的条件控制转移：

以上是gotodiff（条件跳转）

下面是cmovdiff（有条件的mov）

我不知道为什么

v = test-expr ? then-expr : else-expr;

效率高于：

if (!test-expr)
goto false;
v = true-expr;
goto done;
false:
v = else-expr;
done:

假设分支预测硬件会正确猜测大约 50% 的时间，所以如果我们运行每两次（第一次预测成功，第二次预测失败，gotodiff 将总共执行 6+8 = 14 条指令，而 cmovdiff 将有8+8 = 16 条指令，为什么 cmovdiff 比 gotodiff 更高效？

Answer 1

您大大低估了分支未命中的成本。检测到分支未命中后需要多个周期才能恢复（分支 fetch/decode 之后的许多流水线阶段）。 .

出于某种原因，您假设错误推测不会继续到后面的说明中（此处未显示）。

此外，相加指令计数对于估计吞吐量或延迟成本来说远非准确。有些指令有或多或少的延迟；例如，许多最近的 x86 CPU 具有零延迟 mov。 ()。但是，对于吞吐量，mov 仍然会消耗前端带宽。

请参阅 What considerations go into predicting latency for operations on modern superscalar processors and how can I calculate them by hand? 了解如何实际进行静态分析以确定某些代码在现代 x86 上运行的速度有多快（在正确的-预测的情况）。剧透：这很复杂，有时对吞吐量最佳的方法对延迟不是最佳的，因此选择取决于周围的代码。（在 independent 数据上做一些事情，而不是一个长链，其中一个的输出是下一个的输入。）

cmov 在 Broadwell 之前在 Intel 上是 2 微指令，并且控制依赖项不在关键路径上（由于推测执行）。因此，通过正确的预测，分支代码可以是优秀的，而不是在计算完两者（http://yarchive.net/comp/linux/cmov.html). Here's a case where cmov was a pessimization: .

之后具有对 select 正确结果的数据依赖性

如果分支预测有 50% 的时间失败（即不比偶然好！），包含 cmov 版本的循环可能会快 10 倍。

@Mysticial 的分支与无分支的现实生活基准显示，在这种情况下，对于随机（未排序）数组，无分支的加速因子为 5：

       if (data[c] >= 128)
            sum += data[c];

Why is it faster to process a sorted array than an unsorted array?。（对于已排序的数据，在这种情况下，branchy 只稍微快一点。显然其他一些瓶颈阻止了 branchy 在 Mysticial 的 Nehalem 上更快。）

50% 的分支预测错误率绝对是可怕的，几乎是最坏的情况。即使是 20% 也很糟糕；如果分支历史中存在任何类型的模式，那么现代分支预测器就非常好。例如如果每次都使用相同的输入数据作为微基准测试的一部分重复进行，Skylake 可以完全预测超过 12 个元素的 BubbleSort 中的分支。

但是遍历随机数据可能是高度不可预测的。

你的源代码全是图片，所以我不能 copy/paste 把它放到 Godbolt 编译器浏览器 (https://godbolt.org/) 上看看当你用 [=17 编译时现代 gcc 和 clang 做了什么=].我怀疑它会比您显示的代码示例更有效：看起来像很多 mov，并且 cmov 应该能够使用 sub 设置的标志。这是我对您的 absdiff 函数的期望（或至少希望）：

# loading args into registers not shown, only necessary with crappy stack-args calling conventions

# branchless absdiff.  Hand-written.
# Compilers should do something like this if they choose branchless at all.

# inputs in x=%edi, y=%esi
mov   %edi, %eax
sub   %esi, %eax     # EAX= x-y
sub   %edi, %esi     # ESI= y-x
cmovg %esi, %eax     # if(y>x) eax=y-x

# result in EAX

在 Broadwell/Skylake 或锐龙上：

两个 sub 指令都可以运行在同一个周期（因为 mov 是零延迟，假设移动消除成功）。
cmovg 在那之后的一个周期准备好输入，并在另一个 1 个周期产生结果。

所以我们有 4 微指令，x 和 y 都准备好了，有 2 个周期的延迟。 Haswell 和更早版本是一个额外的 uop，具有额外的延迟周期，因为 cmov 有 3 个输入，而更早的 Intel CPU 无法将 3 输入指令解码为单个 uop。

您显示的编译器输出很差；太多 mov 并使用单独的 cmp。 cmp 只是一个 sub，它只写标志，而不是整数寄存器操作数，我们已经需要 sub 结果。

如果您有一个编译器在启用完全优化的情况下发出类似的东西，而不是我上面显示的东西，请报告一个错过优化的错误。

正如@Ped7g 所说，编译器可以对 if() 使用无分支，或者对三元使用分支，如果他们决定的话。如果您正在处理数组元素而不是局部变量，三元往往会有所帮助，因为无条件地编写一个变量可以让编译器进行优化，而不必担心踩到另一个线程正在做的事情。（即编译器不能发明对潜在共享变量的写入，但三元运算符总是写入。）

汇编中的条件数据传输和条件控制传输（使用条件 mov）

conditional data transfers VS n conditional control transfers(using conditional mov) in Assembly

cpu

assembly

instruction-set