if else比if+default更快吗?

12

我进行了一个简单的实验,比较了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

看起来唯一的区别在于 mov 是否在 je 之前或之后执行。

现在(抱歉,我的汇编有点粗糙),难道不是总是更好地在跳跃后使用 mov,以节省流水线刷新吗?如果是这样,为什么优化器(gcc6.2 -O3)不使用更好的方法呢?


2
如果你想知道X是否比Y更快,你应该进行性能分析,_性能分析_和__性能分析__。只有准确的时间测量才能揭示问题的真相。 - ForceBru
4
可能的原因是这两个指针可能指向同一个对象。例如,如果它是一个内存映射输出寄存器,那么这两段代码的结果将截然不同。 - StoryTeller - Unslander Monica
1
@StoryTeller:它们不是“volatile”,因此编译器可以假定如果“c==99”,它不必执行“*x = 0”存储。代码差异是由于编译器按照字面意思实现代码,因为缺乏其他提示。通过基于配置文件的优化,它将了解if()条件被采取/未采取的可能性,并相应地布置代码,以便最常见的情况是快速路径。 (或使用GNU C __builtin_expect()likely/unlikely - Peter Cordes
无论如何,如果默认值不难的话,我认为默认值+if比if/else更好。 - freestyle
1
@StoryTeller:是的,潜在的别名意味着编译器需要按程序顺序执行最后一组存储。但两个分支都通过两个指针进行存储,因此它并没有真正减少优化的可能性。如果有两个间接级别,第一个存储可以更改第二个存储的目标,那就是另一回事了。但由于*x不能与y别名,只能与*y别名,我同意添加restrict在实践或理论上都不重要。 - Peter Cordes
显示剩余6条评论
1个回答

14
对于上述函数,我使用了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 使用条件分支跳过赋值给 *x 的 15。

这个有趣之处在于它几乎完全是你所预期的相反。天真地说,人们可能希望 test0 是你握住优化器手并让其生成无分支代码的方式。至少,这是我想到的第一个想法。但事实上,情况并非如此!优化器能够识别 if/else 惯用语并进行相应的优化!它不能在 test0 的情况下进行相同的优化,你试图超越它。

然而,当添加一个额外的变量时......汇编突然变得不同了。

没什么意外。代码的微小变化通常会对生成的代码产生显著影响。优化器并不是魔法,它们只是非常复杂的模式匹配器。你改变了模式!

当然,一个优化编译器可以使用两个条件移动来生成无分支代码。实际上,这正是 Clang 3.9 为 test3 做的(但对于 test2 不是这样的,这与我们上面的分析一致,即优化器可能更能够识别标准模式而不是不同寻常的模式)。但 GCC 不会这样做。同样,不能保证执行特定的优化。

看起来唯一的区别在于顶部的 "mov" 是在 "je" 之前还是之后执行。

现在(抱歉我的汇编有点粗糙),难道把 mov 放在跳转后面总是更好的选择,以避免流水线刷新吗?

不,不完全是。在这种情况下,这并不会改善代码。如果分支预测错误,无论如何都会有一个流水线刷新。不管是一个 ret 指令还是一个 mov 指令,预测错误的代码都没有太大关系。

唯一需要关注条件分支紧接着的ret指令的原因是,如果您手动编写汇编代码并不知道使用rep ret指令,则需要使用这种针对某些AMD处理器的技巧,避免分支预测惩罚。除非您是一个汇编大师,否则您可能不知道这个技巧。但编译器知道,并且当您专门针对英特尔处理器或不具有此怪癖的不同代AMD处理器时,它也知道不必要。

然而,你可能是对的,将mov放在分支之后可能更好,但原因不是你提出的那个。现代处理器(我相信这是 Nehalem 及其后续版本,但如果需要验证,我会查看Agner Fog 的优化指南)在某些情况下能够进行宏操作融合。基本上,宏操作融合意味着 CPU 的解码器将两个符合条件的指令组合成一个微操作,在流水线的所有阶段节省带宽。在 test3 中所看到的 cmptest 指令后跟条件分支指令就符合宏操作融合的条件(实际上,还有其他必须满足的条件,但此代码符合这些要求)。在 test2 中在 cmpje 之间安排其他指令会使宏操作融合变得不可能,潜在地使代码执行速度更慢。

可以说,这是编译器中的一处优化缺陷。它本应该重新排列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的代码比test2多4个字节。虽然这种差异不太可能有影响,特别是如果此代码未在保证热缓存中运行的紧密循环内执行。那么,这是否意味着您应该始终像test2中所做的那样编写代码呢?好吧,不是的,原因有几个:
  1. As we have seen, it might be a pessimization, since the optimizer may not recognize the pattern.
  2. You should write code for readability and semantic correctness first, only going back to optimize it when your profiler indicates that it is actually a bottleneck. And then, you should only optimize after inspecting and verifying the object code emitted by your compiler, otherwise you could end up with a pessimization. (The standard "trust your compiler until proven otherwise" advice.)
  3. Even though it may be optimal in certain very simple cases, the "preset" idiom is not generalizable. If your initialization is time-consuming, it may be faster to skip over it when possible. (There is one example discussed here, in the context of VB 6, where string-manipulation is so slow that eliding it when possible actually results in faster execution time than fancy branchless code. More generally, the same rationale would apply if you were able to branch around a function call.)

    Even here, where it appears to result in very simple and possibly more optimal code, it may actually be slower because you are writing to memory twice in the case where c is equal to 99, and saving nothing in the case where c is not equal to 99.

    You might save this cost by rewriting the code such that it accumulates the final value in a temporary register, only storing it to memory at the end, e.g.:

    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
    

    but this clobbers two additional registers (eax and ecx) and may not actually be faster. You'd have to benchmark it. Or trust the compiler to emit this code when it is actually optimal, such as when it has inlined a function like test2 within a tight loop.

  4. Even if you could guarantee that writing the code in a certain way would cause the compiler to emit branchless code, this would not necessarily be faster! While branches are slow when they are mispredicted, mispredictions are actually quite rare. Modern processors have extremely good branch prediction engines, achieving prediction accuracies of greater than 99% in most cases.

    Conditional moves are great for avoiding branch mispredictions, but they have the important disadvantage of increasing the length of a dependency chain. By contrast, a correctly predicted branch breaks the dependency chain. (This is probably why GCC doesn't emit two CMOV instructions when you add the extra variable.) A conditional move is only a performance win if you expect branch prediction to fail. If you can count on a prediction success rate of ~75% or better, a conditional branch is probably faster, because it breaks the dependency chain and has a lower latency. And I would suspect that would be the case here, unless c alternates rapidly back and forth between 99 and not-99 each time the function is called. (See Agner Fog's "Optimizing subroutines in assembly language", pp 70–71.)


哇,感谢您提供Agner Fog的伟大链接,再次感谢。 - Elad Weiss
很好的答案,涵盖了编译器对这种代码的实际处理。我认为在一般情况下,我建议编写只向变量写入一次的代码,而不是至少一次或者有时两次。似乎编译器有时会在第二次存储发生时优化掉第一次存储的问题。这也不太可能引起优化器的别名问题。(当然,硬件通常非常擅长通过存储缓冲区和L1高速缓存吞吐量来吸收这些。向相同位置进行第二次存储非常便宜。) - Peter Cordes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接