assembly - 条件数据传输 VS n 条件控制传输(使用条件 mov)在 Assembly
问题描述
嗨,我正在阅读一本比较汇编中的条件数据传输和条件控制传输的教科书:
以上是gotodiff(条件跳转)
我不知道为什么
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 更有效呢?
解决方案
你大大低估了一个分支错过的成本。检测到分支未命中后需要多个周期才能恢复(分支提取/解码后的许多流水线阶段)。 当 Skylake CPU 错误预测分支时,究竟会发生什么?.
并且由于某种原因,您假设错误推测不会继续到以后的说明中(此处未显示)。
此外,将指令计数相加对于估计吞吐量或延迟成本来说远非准确。有些指令有或多或少的延迟;例如,许多最近的 x86 CPU 具有零延迟mov
。(x86 的 MOV 真的可以“免费”吗?为什么我根本无法重现这个?)。但是,对于吞吐量,mov
仍然需要前端带宽。
请参阅在预测现代超标量处理器上的操作延迟时需要考虑哪些注意事项以及如何手动计算它们?了解如何实际进行静态分析以确定某些代码在现代 x86 上运行的速度(在正确预测的情况下)。剧透:它很复杂,有时对吞吐量最佳的东西对延迟不是最佳的,因此选择取决于周围的代码。(对独立数据进行处理,而不是一个长链,其中一个的输出是下一个的输入。)
cmov
在 Broadwell 之前在 Intel 上是 2 uops,并且控制依赖关系脱离了关键路径(由于推测性执行)。因此,通过正确的预测,与在计算两者( http://yarchive.net/comp/linux/cmov.html )后具有数据依赖性来选择正确结果相比,分支代码可能会更好。这cmov
是一个悲观的情况:gcc优化标志 -O3 使代码比 -O2 慢。
如果分支预测在 50% 的情况下失败(即不比机会好!),包含cmov
版本的循环可能会快 10 倍。
@Mysticial 的分支与无分支的实际基准测试显示,在这种情况下,无分支在随机(未排序)数组上的加速因子为 5:
if (data[c] >= 128)
sum += data[c];
为什么处理排序数组比处理未排序数组更快?. (对于已排序的数据,在这种情况下,branchy 只会稍微快一点。显然,其他一些瓶颈阻止了 branchy 在 Mysticial 的 Nehalem 上的速度更快。)
50% 的分支错误预测率绝对是可怕的,几乎是最坏的情况。即使是 20% 也很糟糕;如果分支历史中有任何类型的模式,现代分支预测器非常好。例如,如果作为微基准测试的一部分,每次都使用相同的输入数据重复执行,Skylake 可以完全预测 BubbleSort 中超过 12 个元素的分支。
但是循环随机数据可能是高度不可预测的。
您的源代码全是图像,因此我无法将其复制/粘贴到 Godbolt 编译器资源管理器 ( https://godbolt.org/ ) 并查看现代 gcc 和 clang 在您使用-O3
. 我怀疑它会比您展示的代码示例更有效:看起来很多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 或 Ryzen 上:
- 两条
sub
指令都可以在同一个周期上运行(因为mov
是零延迟,假设成功的 mov 消除)。 cmovg
其输入准备好之后的循环,并在另一个 1 循环中产生结果。
所以我们有 4 个 uops,x 和 y 都准备好了 2 个周期延迟。Haswell 和更早版本是具有额外延迟周期的额外微指令,因为cmov
具有 3 个输入,而早期的英特尔 CPU 无法将 3 输入指令解码为单个微指令。
您显示的编译器输出很差;方式太多mov
并使用单独的cmp
. cmp
只是 asub
只写标志,而不是整数寄存器操作数,我们已经需要sub
结果了。
如果你有一个编译器在启用完全优化的情况下发出类似的东西,而不是我上面显示的,报告一个错过优化的错误。
正如@Ped7g 所说if()
,如果他们决定,编译器可以使用无分支 for 或分支用于三元组。如果您正在处理数组元素而不是局部变量,那么三元往往会有所帮助,因为无条件地编写变量可以让编译器进行优化,而不必担心踩到另一个线程正在执行的操作。(即编译器不能发明对潜在共享变量的写入,但三元运算符总是写入。)
推荐阅读
- android - React Native Image Cache Android
- php - Cloudinary 的 PHP 上传 API 中的 cURL 错误 - “无法连接到端口 443:连接被拒绝”
- excel - Excel VBA 日历 - 选择日期命令问题
- mozilla - 如何在使用 make 构建时修复 DXR 中的服务不可用 503 错误
- javascript - Javascript - 如何将文本区域的值发送到我的文本框
- laravel - 已解决:语法错误-使用 Route::group(['middleware'=>['auth'], function(){ }]); 所有其他路线都停止工作
- php - sql将两列相加并将两者相加
- postgresql - 一批从 PostgreSQL 传输到 Redis 的数据有多少被认为是可靠的?
- google-sheets - Google 是否更改了函数 VALUE()?
- android - 谷歌播放控制台说“你不能编辑这个应用程序,直到你创建一个声明敏感权限的新应用程序版本”如何解决?