GCC 5.4.0 的昂贵跳跃
An expensive jump with GCC 5.4.0
我有一个看起来像这样的函数(只显示重要部分):
double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY) {
...
for(std::size_t i=std::max(0,-shift);i<max;i++) {
if ((curr[i] < 479) && (l[i + shift] < 479)) {
nontopOverlap++;
}
...
}
...
}
这样写的,这个函数在我的机器上花了大约 34 毫秒。将条件更改为布尔乘法后(使代码看起来像这样):
double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY) {
...
for(std::size_t i=std::max(0,-shift);i<max;i++) {
if ((curr[i] < 479) * (l[i + shift] < 479)) {
nontopOverlap++;
}
...
}
...
}
执行时间减少到 ~19ms。
使用的编译器是带有 -O3
的 GCC 5.4.0,在检查 the generated asm code using godbolt.org 之后,我发现第一个示例会生成跳转,而第二个则不会。我决定尝试 GCC 6.2.0,它在使用第一个示例时也会生成跳转指令,但 GCC 7 似乎不再生成跳转指令。
找出这种加速代码的方法是相当可怕的,需要相当长的时间。为什么编译器会这样?它是有意的吗?程序员应该注意吗?还有类似的吗?
这可能是因为当您使用逻辑运算符 &&
时,编译器必须检查两个条件才能使 if 语句成功。但是在第二种情况下,由于您将 int 值隐式转换为 bool,因此编译器会根据传入的类型和值以及(可能)单个跳转条件做出一些假设。也有可能编译器通过移位完全优化了 jmps。
&&
运算符执行短路评估。这意味着只有当第一个操作数的计算结果为 true
时,才会计算第二个操作数。在这种情况下,这肯定会导致跳跃。
您可以创建一个小示例来说明这一点:
#include <iostream>
bool f(int);
bool g(int);
void test(int x, int y)
{
if ( f(x) && g(x) )
{
std::cout << "ok";
}
}
The assembler output can be found here.
您可以看到生成的代码首先调用 f(x)
,然后检查输出并跳转到 g(x)
的计算,当时这是 true
。否则它离开函数。
改为使用 "boolean" 乘法,每次都强制计算两个操作数,因此不需要跳转。
根据数据的不同,跳转可能会导致速度变慢,因为它会干扰 CPU 的管道和推测执行等其他事情。通常分支预测会有所帮助,但如果你的数据是随机的,那么就没有多少可以预测的了。
逻辑与运算符 (&&
) 使用短路评估,这意味着只有在第一次比较的评估结果为真时才进行第二次测试。这通常正是您需要的语义。例如,考虑以下代码:
if ((p != nullptr) && (p->first > 0))
在取消引用之前,您必须确保指针不为空。如果此 不是 短路评估,您将有未定义的行为,因为您将取消引用空指针。
在条件评估是一个昂贵的过程的情况下,短路评估也可能会产生性能增益。例如:
if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))
如果 DoLengthyCheck1
失败,调用 DoLengthyCheck2
就没有意义了。
但是,在生成的二进制文件中,短路操作通常会导致两个分支,因为这是编译器保留这些语义的最简单方法。 (这就是为什么在硬币的另一面,短路评估有时会 抑制 优化潜力的原因。)您可以通过查看为您生成的目标代码的相关部分来了解这一点if
GCC 5.4 声明:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13w, 478 ; (curr[i] < 479)
ja .L5
cmp ax, 478 ; (l[i + shift] < 479)
ja .L5
add r8d, 1 ; nontopOverlap++
你在这里看到两个比较(cmp
指令),每个比较后跟一个单独的条件 jump/branch(ja
,如果在上面则跳转)。
根据经验,分支很慢,因此应避免在紧密循环中使用。这在几乎所有 x86 处理器上都是如此,从不起眼的 8088(其缓慢的获取时间和极小的预取队列 [与指令缓存相比],加上完全缺乏分支预测,意味着采取的分支需要转储缓存) 到现代实现(其长管道使错误预测的分支同样昂贵)。请注意我在那里滑入的小警告。自 Pentium Pro 以来的现代处理器具有先进的分支预测引擎,旨在最大限度地降低分支成本。如果可以正确预测分支的方向,则成本是最小的。大多数时候,这很有效,但如果你遇到分支预测器不在你身边的病态情况,your code can get extremely slow。这大概是你在这里的地方,因为你说你的数组是未排序的。
你说基准测试证实用 *
替换 &&
可以使代码明显更快。当我们比较目标代码的相关部分时,原因很明显:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
xor r15d, r15d ; (curr[i] < 479)
cmp r13w, 478
setbe r15b
xor r14d, r14d ; (l[i + shift] < 479)
cmp ax, 478
setbe r14b
imul r14d, r15d ; meld results of the two comparisons
cmp r14d, 1 ; nontopOverlap++
sbb r8d, -1
这可能会更快,这有点违反直觉,因为这里有 更多 条指令,但这有时就是优化的工作原理。您会看到此处进行了相同的比较 (cmp
),但现在每个比较前面都有一个 xor
,后面跟着一个 setbe
。 XOR 只是清除寄存器的标准技巧。 setbe
是一条 x86 指令,它根据标志的值设置一个位,通常用于实现无分支代码。这里,setbe
是 ja
的倒数。如果比较低于或等于,它将其目标寄存器设置为 1(因为寄存器已预置零,否则它将为 0),而 ja
如果比较高于则分支。在 r15b
和 r14b
寄存器中获得这两个值后,使用 imul
将它们相乘。乘法传统上是一个相对较慢的操作,但在现代处理器上它非常快,而且这将特别快,因为它只乘以两个字节大小的值。
您可以轻松地将乘法替换为按位与运算符 (&
),它不进行短路计算。这使代码更加清晰,并且是编译器普遍认可的模式。但是当你对你的代码执行此操作并使用 GCC 5.4 编译它时,它会继续发出第一个分支:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13w, 478 ; (curr[i] < 479)
ja .L4
cmp ax, 478 ; (l[i + shift] < 479)
setbe r14b
cmp r14d, 1 ; nontopOverlap++
sbb r8d, -1
没有技术原因它必须以这种方式发出代码,但出于某种原因,它的内部启发式告诉它这样更快。如果分支预测器在你这边,它 会 可能会更快,但如果分支预测失败的次数多于成功的次数,它可能会更慢。
新一代的编译器(和其他编译器,如 Clang)知道这条规则,并且有时会使用它来生成您通过手动优化寻求的相同代码。我经常看到 Clang 将 &&
表达式翻译成与我使用 &
时相同的代码。以下是 GCC 6.2 的相关输出以及您使用普通 &&
运算符的代码:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13d, 478 ; (curr[i] < 479)
jg .L7
xor r14d, r14d ; (l[i + shift] < 479)
cmp eax, 478
setle r14b
add esi, r14d ; nontopOverlap++
注意这个是多么聪明!它使用有符号条件(jg
和 setle
)而不是无符号条件(ja
和 setbe
),但这并不重要。你可以看到它仍然像旧版本一样为第一个条件执行比较和分支,并使用相同的 setCC
指令为第二个条件生成无分支代码,但它在它是如何增加的。它没有进行第二次冗余比较来设置 sbb
操作的标志,而是使用 r14d
将是 1 或 0 的知识来简单地无条件地将此值添加到 nontopOverlap
。如果 r14d
为 0,则加法为空操作;否则,它会加 1,就像它应该做的那样。
GCC 6.2 实际上在使用短路 &&
运算符时比按位 &
运算符生成 更多 高效代码:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13d, 478 ; (curr[i] < 479)
jg .L6
cmp eax, 478 ; (l[i + shift] < 479)
setle r14b
cmp r14b, 1 ; nontopOverlap++
sbb esi, -1
分支和条件集仍然存在,但现在又回到了不太聪明的递增方式nontopOverlap
。这是一个重要的教训,告诉你为什么在试图超越你的编译器时应该小心!
但是,如果您可以 证明 基准测试表明分支代码实际上更慢,那么尝试让您的编译器更聪明可能是值得的。您只需仔细检查反汇编,并准备好在升级到更高版本的编译器时重新评估您的决定。例如,您的代码可以重写为:
nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));
这里根本没有 if
语句,绝大多数编译器永远不会考虑为此发出分支代码。海湾合作委员会也不例外;所有版本都会生成类似于以下内容的内容:
movzx r14d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r14d, 478 ; (curr[i] < 479)
setle r15b
xor r13d, r13d ; (l[i + shift] < 479)
cmp eax, 478
setle r13b
and r13d, r15d ; meld results of the two comparisons
add esi, r13d ; nontopOverlap++
如果您一直在关注前面的示例,那么您应该会很熟悉。两种比较都以无分支的方式完成,中间结果被 and
编辑在一起,然后这个结果(将是 0 或 1)被 add
编辑为 nontopOverlap
。如果您想要无分支代码,这几乎可以确保您获得它。
GCC 7 变得更加智能。它现在为上述技巧生成与原始代码几乎相同的代码(除了指令的一些轻微重新排列)。所以,您的问题 "Why does the compiler behave this way?" 的答案可能是因为它们并不完美!他们尝试使用启发式方法生成尽可能最佳的代码,但他们并不总是做出最佳决策。但至少他们可以随着时间的推移变得更聪明!
查看这种情况的一种方式是分支代码具有更好的最佳情况性能。如果分支预测成功,跳过不必要的操作将导致 运行 时间稍快。但是,无分支代码具有更好的 worst-case 性能。如果分支预测失败,执行一些必要的附加指令以避免分支将 绝对 比错误预测的分支更快。即使是最聪明最聪明的编译器也很难做出这个选择。
关于您是否认为这是程序员需要注意的问题,答案几乎肯定是否定的,除了在您试图通过微优化加速的某些热循环中。然后,您坐下来进行反汇编并找到调整它的方法。而且,正如我之前所说,当您更新到较新版本的编译器时,请准备好重新审视这些决定,因为它可能会对您的棘手代码做一些愚蠢的事情,或者它可能已经改变了它的优化启发式方法,以至于您可以返回使用您的原始代码。评论彻底!
需要注意的一件重要事情是
(curr[i] < 479) && (l[i + shift] < 479)
和
(curr[i] < 479) * (l[i + shift] < 479)
在语义上不等同!特别是,如果您遇到以下情况:
0 <= i
和 i < curr.size()
都为真
curr[i] < 479
为假
i + shift < 0
或 i + shift >= l.size()
为真
那么表达式 (curr[i] < 479) && (l[i + shift] < 479)
保证是一个明确定义的布尔值。例如,它不会导致段错误。
但是,在这种情况下,表达式 (curr[i] < 479) * (l[i + shift] < 479)
是 未定义的行为;它是允许导致分段错误。
这意味着对于原始代码片段,例如,编译器不能只编写一个执行两个比较并执行 and
操作的循环,除非编译器也可以证明 l[i + shift]
在不需要的情况下永远不会导致段错误。
简而言之,原始代码提供的优化机会少于后者。 (当然,编译器是否识别机会是一个完全不同的问题)
您可以通过以下方式修复原始版本
bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
// ...
我有一个看起来像这样的函数(只显示重要部分):
double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY) {
...
for(std::size_t i=std::max(0,-shift);i<max;i++) {
if ((curr[i] < 479) && (l[i + shift] < 479)) {
nontopOverlap++;
}
...
}
...
}
这样写的,这个函数在我的机器上花了大约 34 毫秒。将条件更改为布尔乘法后(使代码看起来像这样):
double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY) {
...
for(std::size_t i=std::max(0,-shift);i<max;i++) {
if ((curr[i] < 479) * (l[i + shift] < 479)) {
nontopOverlap++;
}
...
}
...
}
执行时间减少到 ~19ms。
使用的编译器是带有 -O3
的 GCC 5.4.0,在检查 the generated asm code using godbolt.org 之后,我发现第一个示例会生成跳转,而第二个则不会。我决定尝试 GCC 6.2.0,它在使用第一个示例时也会生成跳转指令,但 GCC 7 似乎不再生成跳转指令。
找出这种加速代码的方法是相当可怕的,需要相当长的时间。为什么编译器会这样?它是有意的吗?程序员应该注意吗?还有类似的吗?
这可能是因为当您使用逻辑运算符 &&
时,编译器必须检查两个条件才能使 if 语句成功。但是在第二种情况下,由于您将 int 值隐式转换为 bool,因此编译器会根据传入的类型和值以及(可能)单个跳转条件做出一些假设。也有可能编译器通过移位完全优化了 jmps。
&&
运算符执行短路评估。这意味着只有当第一个操作数的计算结果为 true
时,才会计算第二个操作数。在这种情况下,这肯定会导致跳跃。
您可以创建一个小示例来说明这一点:
#include <iostream>
bool f(int);
bool g(int);
void test(int x, int y)
{
if ( f(x) && g(x) )
{
std::cout << "ok";
}
}
The assembler output can be found here.
您可以看到生成的代码首先调用 f(x)
,然后检查输出并跳转到 g(x)
的计算,当时这是 true
。否则它离开函数。
改为使用 "boolean" 乘法,每次都强制计算两个操作数,因此不需要跳转。
根据数据的不同,跳转可能会导致速度变慢,因为它会干扰 CPU 的管道和推测执行等其他事情。通常分支预测会有所帮助,但如果你的数据是随机的,那么就没有多少可以预测的了。
逻辑与运算符 (&&
) 使用短路评估,这意味着只有在第一次比较的评估结果为真时才进行第二次测试。这通常正是您需要的语义。例如,考虑以下代码:
if ((p != nullptr) && (p->first > 0))
在取消引用之前,您必须确保指针不为空。如果此 不是 短路评估,您将有未定义的行为,因为您将取消引用空指针。
在条件评估是一个昂贵的过程的情况下,短路评估也可能会产生性能增益。例如:
if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))
如果 DoLengthyCheck1
失败,调用 DoLengthyCheck2
就没有意义了。
但是,在生成的二进制文件中,短路操作通常会导致两个分支,因为这是编译器保留这些语义的最简单方法。 (这就是为什么在硬币的另一面,短路评估有时会 抑制 优化潜力的原因。)您可以通过查看为您生成的目标代码的相关部分来了解这一点if
GCC 5.4 声明:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13w, 478 ; (curr[i] < 479)
ja .L5
cmp ax, 478 ; (l[i + shift] < 479)
ja .L5
add r8d, 1 ; nontopOverlap++
你在这里看到两个比较(cmp
指令),每个比较后跟一个单独的条件 jump/branch(ja
,如果在上面则跳转)。
根据经验,分支很慢,因此应避免在紧密循环中使用。这在几乎所有 x86 处理器上都是如此,从不起眼的 8088(其缓慢的获取时间和极小的预取队列 [与指令缓存相比],加上完全缺乏分支预测,意味着采取的分支需要转储缓存) 到现代实现(其长管道使错误预测的分支同样昂贵)。请注意我在那里滑入的小警告。自 Pentium Pro 以来的现代处理器具有先进的分支预测引擎,旨在最大限度地降低分支成本。如果可以正确预测分支的方向,则成本是最小的。大多数时候,这很有效,但如果你遇到分支预测器不在你身边的病态情况,your code can get extremely slow。这大概是你在这里的地方,因为你说你的数组是未排序的。
你说基准测试证实用 *
替换 &&
可以使代码明显更快。当我们比较目标代码的相关部分时,原因很明显:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
xor r15d, r15d ; (curr[i] < 479)
cmp r13w, 478
setbe r15b
xor r14d, r14d ; (l[i + shift] < 479)
cmp ax, 478
setbe r14b
imul r14d, r15d ; meld results of the two comparisons
cmp r14d, 1 ; nontopOverlap++
sbb r8d, -1
这可能会更快,这有点违反直觉,因为这里有 更多 条指令,但这有时就是优化的工作原理。您会看到此处进行了相同的比较 (cmp
),但现在每个比较前面都有一个 xor
,后面跟着一个 setbe
。 XOR 只是清除寄存器的标准技巧。 setbe
是一条 x86 指令,它根据标志的值设置一个位,通常用于实现无分支代码。这里,setbe
是 ja
的倒数。如果比较低于或等于,它将其目标寄存器设置为 1(因为寄存器已预置零,否则它将为 0),而 ja
如果比较高于则分支。在 r15b
和 r14b
寄存器中获得这两个值后,使用 imul
将它们相乘。乘法传统上是一个相对较慢的操作,但在现代处理器上它非常快,而且这将特别快,因为它只乘以两个字节大小的值。
您可以轻松地将乘法替换为按位与运算符 (&
),它不进行短路计算。这使代码更加清晰,并且是编译器普遍认可的模式。但是当你对你的代码执行此操作并使用 GCC 5.4 编译它时,它会继续发出第一个分支:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13w, 478 ; (curr[i] < 479)
ja .L4
cmp ax, 478 ; (l[i + shift] < 479)
setbe r14b
cmp r14d, 1 ; nontopOverlap++
sbb r8d, -1
没有技术原因它必须以这种方式发出代码,但出于某种原因,它的内部启发式告诉它这样更快。如果分支预测器在你这边,它 会 可能会更快,但如果分支预测失败的次数多于成功的次数,它可能会更慢。
新一代的编译器(和其他编译器,如 Clang)知道这条规则,并且有时会使用它来生成您通过手动优化寻求的相同代码。我经常看到 Clang 将 &&
表达式翻译成与我使用 &
时相同的代码。以下是 GCC 6.2 的相关输出以及您使用普通 &&
运算符的代码:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13d, 478 ; (curr[i] < 479)
jg .L7
xor r14d, r14d ; (l[i + shift] < 479)
cmp eax, 478
setle r14b
add esi, r14d ; nontopOverlap++
注意这个是多么聪明!它使用有符号条件(jg
和 setle
)而不是无符号条件(ja
和 setbe
),但这并不重要。你可以看到它仍然像旧版本一样为第一个条件执行比较和分支,并使用相同的 setCC
指令为第二个条件生成无分支代码,但它在它是如何增加的。它没有进行第二次冗余比较来设置 sbb
操作的标志,而是使用 r14d
将是 1 或 0 的知识来简单地无条件地将此值添加到 nontopOverlap
。如果 r14d
为 0,则加法为空操作;否则,它会加 1,就像它应该做的那样。
GCC 6.2 实际上在使用短路 &&
运算符时比按位 &
运算符生成 更多 高效代码:
movzx r13d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r13d, 478 ; (curr[i] < 479)
jg .L6
cmp eax, 478 ; (l[i + shift] < 479)
setle r14b
cmp r14b, 1 ; nontopOverlap++
sbb esi, -1
分支和条件集仍然存在,但现在又回到了不太聪明的递增方式nontopOverlap
。这是一个重要的教训,告诉你为什么在试图超越你的编译器时应该小心!
但是,如果您可以 证明 基准测试表明分支代码实际上更慢,那么尝试让您的编译器更聪明可能是值得的。您只需仔细检查反汇编,并准备好在升级到更高版本的编译器时重新评估您的决定。例如,您的代码可以重写为:
nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));
这里根本没有 if
语句,绝大多数编译器永远不会考虑为此发出分支代码。海湾合作委员会也不例外;所有版本都会生成类似于以下内容的内容:
movzx r14d, WORD PTR [rbp+rcx*2]
movzx eax, WORD PTR [rbx+rcx*2]
cmp r14d, 478 ; (curr[i] < 479)
setle r15b
xor r13d, r13d ; (l[i + shift] < 479)
cmp eax, 478
setle r13b
and r13d, r15d ; meld results of the two comparisons
add esi, r13d ; nontopOverlap++
如果您一直在关注前面的示例,那么您应该会很熟悉。两种比较都以无分支的方式完成,中间结果被 and
编辑在一起,然后这个结果(将是 0 或 1)被 add
编辑为 nontopOverlap
。如果您想要无分支代码,这几乎可以确保您获得它。
GCC 7 变得更加智能。它现在为上述技巧生成与原始代码几乎相同的代码(除了指令的一些轻微重新排列)。所以,您的问题 "Why does the compiler behave this way?" 的答案可能是因为它们并不完美!他们尝试使用启发式方法生成尽可能最佳的代码,但他们并不总是做出最佳决策。但至少他们可以随着时间的推移变得更聪明!
查看这种情况的一种方式是分支代码具有更好的最佳情况性能。如果分支预测成功,跳过不必要的操作将导致 运行 时间稍快。但是,无分支代码具有更好的 worst-case 性能。如果分支预测失败,执行一些必要的附加指令以避免分支将 绝对 比错误预测的分支更快。即使是最聪明最聪明的编译器也很难做出这个选择。
关于您是否认为这是程序员需要注意的问题,答案几乎肯定是否定的,除了在您试图通过微优化加速的某些热循环中。然后,您坐下来进行反汇编并找到调整它的方法。而且,正如我之前所说,当您更新到较新版本的编译器时,请准备好重新审视这些决定,因为它可能会对您的棘手代码做一些愚蠢的事情,或者它可能已经改变了它的优化启发式方法,以至于您可以返回使用您的原始代码。评论彻底!
需要注意的一件重要事情是
(curr[i] < 479) && (l[i + shift] < 479)
和
(curr[i] < 479) * (l[i + shift] < 479)
在语义上不等同!特别是,如果您遇到以下情况:
0 <= i
和i < curr.size()
都为真curr[i] < 479
为假i + shift < 0
或i + shift >= l.size()
为真
那么表达式 (curr[i] < 479) && (l[i + shift] < 479)
保证是一个明确定义的布尔值。例如,它不会导致段错误。
但是,在这种情况下,表达式 (curr[i] < 479) * (l[i + shift] < 479)
是 未定义的行为;它是允许导致分段错误。
这意味着对于原始代码片段,例如,编译器不能只编写一个执行两个比较并执行 and
操作的循环,除非编译器也可以证明 l[i + shift]
在不需要的情况下永远不会导致段错误。
简而言之,原始代码提供的优化机会少于后者。 (当然,编译器是否识别机会是一个完全不同的问题)
您可以通过以下方式修复原始版本
bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
// ...