与GCC 5.4.0的一次昂贵的跳跃

Question

我有一个看起来像这样的功能(只显示重要部分):

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++;
     }
     ...
  }
...
}

写得这样,我的机器上的功能耗时约34ms.将条件更改为bool乘法后(使代码看起来像这样):

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,在使用godbolt.org检查生成的asm代码后,我发现第一个示例生成跳转,而第二个示例没有生成跳转.我决定尝试GCC 6.2.0,它在使用第一个例子时也生成一个跳转指令,但GCC 7似乎不再生成一个.

找到这种加速代码的方式是相当可怕的,花了很长时间.为什么编译器会以这种方式运行？这是程序员应该注意的吗？还有更类似的东西吗？

编辑:链接到godbolt https://godbolt.org/g/5lKPF3

Answer 1

逻辑AND运算符(&&)使用短路评估,这意味着仅在第一次比较评估为真时才进行第二次测试.这通常是您需要的语义.例如,请考虑以下代码:

if ((p != nullptr) && (p->first > 0))

在取消引用之前,必须确保指针为非null.如果这不是短路评估,那么您将有未定义的行为,因为您将取消引用空指针.

在条件评估是昂贵的过程的情况下,短路评估也可能产生性能增益.例如:

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

如果DoLengthyCheck1失败,就没有必要打电话DoLengthyCheck2.

但是,在生成的二进制文件中,短路操作通常会产生两个分支,因为这是编译器保留这些语义的最简单方法.(这就是为什么,硬币的另一方面,短路评估有时会抑制优化潜力.)您可以通过查看ifGCC 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指令),每个比较后面跟一个单独的条件跳转/分支(ja如果在上面,则跳转).

一般的经验法则是分支很慢,因此要在紧密的循环中避免.几乎所有x86处理器都是如此,从简陋的8088(其缓慢的获取时间和极小的预取队列[与指令缓存相当],加上完全缺乏分支预测,意味着所采用的分支需要缓存被转储)对于现代实施(其长管道使错误预测的分支同样昂贵).请注意我在那里滑倒的小警告.Pentium Pro以来的现代处理器拥有先进的分支预测引擎,旨在最大限度地降低分支机构的成本.如果可以正确预测分支的方向,则成本最小.大多数情况下,这种方法效果很好,但如果您遇到分支预测器不在您身边的病态情况,您的代码可能会变得非常慢.这可能是你在这里的地方,因为你说你的数组是未分类的.

你说基准测试证实&&用a 替换*使得代码明显更快.当我们比较目标代码的相关部分时,原因很明显:

    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.如果比较低于或等于(由于寄存器预先归零,否则它将为0),它将其目标寄存器设置为1,而ja如果比较高于分支则分支.一旦在r15b和r14b寄存器中获得了这两个值,就会将它们相乘imul.乘法传统上是一个相对较慢的操作,但它在现代处理器上速度很快,而且速度特别快,因为它只乘以两个字节大小的值.

您可以很容易地使用按位AND运算符(&)替换乘法,这不会进行短路评估.这使得代码更加清晰,并且是编译器通常认可的模式.但是,当您使用代码执行此操作并使用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操作的标志,而是使用r14d1或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变得更加智能.它现在为上述技巧生成几乎相同的代码(除了一些轻微的重新排列指令)作为原始代码.那么,你的问题的答案是"为什么编译器会以这种方式运行？" ,可能是因为它们并不完美!他们尝试使用启发式算法来生成最佳代码,但他们并不总能做出最佳决策.但至少他们可以随着时间的推移变得更聪明!

查看这种情况的一种方法是分支代码具有更好的最佳性能.如果分支预测成功,则跳过不必要的操作将导致稍快的运行时间.但是,无分支代码具有更好的最坏情况性能.如果分支预测失败,执行必要的,以避免一个分支一些额外的说明将肯定比一个分支预测失败得更快.即使是最聪明,最聪明的编译器也很难做出这样的选择.

关于这是程序员需要注意的问题,答案几乎肯定是否定的,除了某些热循环,你试图通过微优化加速.然后,您坐下来进行反汇编并找到调整它的方法.而且,正如我之前所说的那样,当你更新到更新版本的编译器时,准备重新审视这些决定,因为它可能会对你的棘手代码做一些愚蠢的事情,或者它可能已经改变了它的优化启发式,你可以回去使用您的原始代码.评论彻底!

Answer 2

需要注意的一件重要事情是

(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) {
    // ...

Answer 3

该&&运营商实现了短路的评价.这意味着仅在第一个操作数求值时才计算第二个操作数true.这肯定会导致这种情况的跳跃.

您可以创建一个小示例来显示:

#include <iostream>

bool f(int);
bool g(int);

void test(int x, int y)
{
  if ( f(x) && g(x)  )
  {
    std::cout << "ok";
  }
}

汇编器输出可以在这里找到.

您可以看到生成的代码首先调用f(x),然后检查输出并跳转到评估g(x)时间true.否则它将离开该功能.

使用"布尔"乘法代替每次都强制评估两个操作数,因此不需要跳转.

根据数据的不同,跳转可能会导致速度变慢,因为它会干扰CPU的管道以及推测执行等其他事情.通常,分支预测会有所帮助,但如果您的数据是随机的,那么可以预测的数据并不多.