是否比if + default更快？

Question

我进行了一个简单的实验,比较if-else到只有if(预设默认值).例:

void test0(char c, int *x) {
    *x = 0;
    if (c == 99) {
        *x = 15;
    }
}

void test1(char c, int *x) {
    if (c == 99) {
        *x = 15;
    } else {
        *x = 0;
    }
}

对于上面的函数,我得到了完全相同的汇编代码(使用cmovne).

但是在添加额外变量时:

void test2(char c, int *x, int *y) {
    *x = 0;
    *y = 0;
    if (c == 99) {
        *x = 15;
        *y = 21;
    }
}

void test3(char c, int *x, int *y) {
    if (c == 99) {
        *x = 15;
        *y = 21;
    } else {
        *x = 0;
        *y = 0;
    }
}

组装突然变得不同:

test2(char, int*, int*):
        cmp     dil, 99
        mov     DWORD PTR [rsi], 0
        mov     DWORD PTR [rdx], 0
        je      .L10
        rep ret
.L10:
        mov     DWORD PTR [rsi], 15
        mov     DWORD PTR [rdx], 21
        ret
test3(char, int*, int*):
        cmp     dil, 99
        je      .L14
        mov     DWORD PTR [rsi], 0
        mov     DWORD PTR [rdx], 0
        ret
.L14:
        mov     DWORD PTR [rsi], 15
        mov     DWORD PTR [rdx], 21
        ret

似乎唯一的区别是顶部movs是在之前还是之后完成的je.

现在(对不起,我的装配有点粗糙),mov跳过后有没有更好的s,为了节省管道冲洗？如果是这样,为什么优化器(gcc6.2 -O3)不会使用更好的方法？

Answer 1

对于上面的函数,我得到了完全相同的汇编代码(使用cmovne).

当然,一些编译器可能会进行优化,但不能保证.您很可能会为这两种函数编写方法获得不同的目标代码.

实际上,没有保证优化(尽管现代优化编译器在大多数情况下都能完成令人印象深刻的工作),因此您应该编写代码来捕获您打算使用的语义,或者您应该验证生成的目标代码和编写代码以确保获得预期的输出.

以下是针对x86-32时MSVC的旧版本将生成的内容(主要是因为他们不知道使用CMOV指令):

test0 PROC
    cmp      BYTE PTR [c], 99
    mov      eax, DWORD PTR [x]
    mov      DWORD PTR [eax], 0
    jne      SHORT LN2
    mov      DWORD PTR [eax], 15
LN2:
    ret      0
test0 ENDP

test1 PROC
    mov      eax, DWORD PTR [x]
    xor      ecx, ecx
    cmp      BYTE PTR [c], 99
    setne    cl
    dec      ecx
    and      ecx, 15
    mov      DWORD PTR [eax], ecx
    ret      0
test1 ENDP

请注意,test1为您提供无分支代码,该代码利用SETNE指令(条件集,根据条件代码将其操作数设置为0或1 NE),并结合一些位操作来生成正确的值.test0使用条件分支跳过15到的赋值*x.

这很有趣的原因是因为它几乎与你所期望的完全相反.天真地,人们可能会认为这test0将是你持有优化器并让它生成无分支代码的方式.至少,这是我头脑中的第一个想法.但事实上,事实并非如此!优化器能够识别if/ else成语并相应地进行优化!test0在你试图超越它的情况下,它无法进行相同的优化.

但是当添加额外的变量时......组件突然变得不同了

好吧,那里也不奇怪.代码中的微小变化通常会对发出的代码产生重大影响.优化者不是魔术; 它们只是非常复杂的模式匹配器.你改变了模式!

当然,优化编译器可以在这里使用两个条件移动来生成无分支代码.实际上,这正是Clang 3.9所做的test3(但并非如此test2,与我们上面的分析一致,表明优化器可能更能识别标准模式而非异常模式).但海湾合作委员会不这样做.同样,不能保证执行特定的优化.

似乎唯一的区别是顶部的"mov"是在"je"之前还是之后完成的.

现在(对不起,我的组装有点粗糙),跳转后有没有总是更好的,以节省管道冲洗？

不,不是真的.在这种情况下,这不会改进代码.如果分支机构被错误预测,那么无论如何都会有管道冲洗.推测错误预测的代码是ret指令还是指令是没关系的mov.

唯一的原因ret是,如果您手动编写汇编代码并且不知道使用rep ret指令,那么紧跟在条件分支之后的指令就很重要.这是某些AMD处理器必需的技巧,可以避免分支预测的损失.除非你是集会大师,否则你可能不会知道这个伎俩.但编译器确实如此,而且当你专门针对英特尔处理器或不具备这种怪癖的不同代AMD处理器时,它也知道没有必要.

但是,你可能是正确mov的,在分支后有s 更好,但不是你建议的原因.现代处理器(我相信这是Nehalem以及后来,但如果我需要验证,我会在Agner Fog的优秀优化指南中查找)在某些情况下能够进行宏观融合.基本上,宏操作融合意味着CPU的解码器将两个合格的指令组合成一个微操作,从而节省了管道所有阶段的带宽.一个cmp或test跟随指令通过条件转移指令,正如你看到的test3,是符合宏指令融合(实际上,也有必须满足其他条件,但是这个代码不符合这些要求).正如您所见,在cmp和之间调度其他指令使得宏操作融合变得不可能,从而可能使代码执行得更慢.jetest2

但可以说,这是编译器中的优化缺陷.它可以重新排序mov指令,je立即放置cmp,保留宏操作融合的能力:

test2a(char, int*, int*):
    mov     DWORD PTR [rsi], 0    ; do the default initialization *first*
    mov     DWORD PTR [rdx], 0
    cmp     dil, 99               ; this is now followed immediately by the conditional
    je      .L10                  ;  branch, making macro-op fusion possible
    rep ret
.L10:
    mov     DWORD PTR [rsi], 15
    mov     DWORD PTR [rdx], 21
    ret

目标代码test2和test3代码大小之间的另一个区别.由于优化器发出的填充以对齐分支目标,因此代码test3大于4个字节test2.但是,这不太可能是重要的差异,特别是如果这个代码没有在一个紧密的循环中执行,而它在高速缓存中保证是热的.

那么,这是否意味着你应该像你一样编写代码test2？
嗯,不,有几个原因:

1. 正如我们所看到的,它可能是一种悲观,因为优化器可能无法识别该模式.
2. 你应该写的可读性和语义的正确性代码首先,只有回去当你的探查表明,它实际上是一个瓶颈进行优化.然后,您应该只在检查和验证编译器发出的目标代码后进行优化,否则最终会导致悲观.(标准"信任你的编译器,直到证明不然"的建议.)

3. 尽管在某些非常简单的情况下它可能是最佳的,但"预设"惯用语是不可推广的.如果您的初始化非常耗时,则在可能的情况下跳过它可能会更快.(这里讨论了一个例子,在VB 6的上下文中,字符串操作非常慢,在可能的情况下将其删除实际上比花哨的无分支代码实现更快的执行时间.更一般地说,如果你能够使用相同的基本原理分支函数调用.)

   即使在这里,它似乎导致非常简单,可能更优化的代码,它实际上可能会比较慢,因为你正在写内存两次在该情况下c等于99,而在该情况下,储蓄没什么c是不是等于99 .

   您可以通过重写代码来节省此成本,使其在临时寄存器中累积最终值,仅在最后将其存储到内存中,例如:

   test2b(char, int*, int*):
       xor     eax, eax               ; pre-zero the EAX register
       xor     ecx, ecx               ; pre-zero the ECX register
       cmp     dil, 99
       je      Done
       mov     eax, 15                ; change the value in EAX if necessary
       mov     ecx, 21                ; change the value in ECX if necessary
   Done:
       mov     DWORD PTR [rsi], eax   ; store our final temp values to memory
       mov     DWORD PTR [rdx], ecx
       ret
   

   但这会破坏两个额外的寄存器(eax和ecx),实际上可能不会更快.你必须对它进行基准测试.或者信任编译器在实际最佳时发出此代码,例如test2在紧密循环中内联函数时.

4. 即使您可以保证以某种方式编写代码会导致编译器发出无分支代码,但这不一定会更快!虽然错误预测时分支机构很慢,但错误预测实际上很少见.现代处理器具有非常良好的分支预测引擎,在大多数情况下,实现大于99%的预测精度.

   条件移动对于避免分支错误预测很有用,但它们具有增加依赖链长度的重要缺点.相比之下,正确预测的分支会破坏依赖链.(这可能是GCC在添加额外变量时不发出两条CMOV指令的原因.)如果您希望分支预测失败,则条件移动只是性能获胜.如果你可以指望约75%或更好的预测成功率,条件分支可能更快,因为它打破了依赖链并具有较低的延迟.而且我怀疑这种情况就是这样,除非c每次调用函数时在99和99之间快速来回交替.(参见Agner Fog的"用汇编语言优化子程序",第70-71页.)