if(a<901)是否比if(a<=900)快?

与这个简单示例中的情况不同,但循环复杂代码的性能略有变化。我想这需要对生成的机器代码进行一些处理,以防它是真的。


当前回答

假设我们讨论的是内部整数类型,不可能一个比另一个更快。它们显然在语义上是相同的。它们都要求编译器做完全相同的事情。只有一个严重损坏的编译器才能为其中一个生成劣质代码。

如果在某些平台上,对于简单整数类型,<比<=快,编译器应始终将常量的<=转换为<。任何没有这样做的编译器都将是一个糟糕的编译器(对于该平台)。

其他回答

当我写这个答案的第一个版本时,我只看了关于<vs.<=的标题问题,而不是常数a<901vs.a<=900的具体例子。许多编译器总是通过在<和<=之间进行转换来缩小常数的大小,例如,因为x86立即数操作数的-128..127的1字节编码更短。

对于ARM来说,能够作为立即数进行编码取决于能够将窄字段旋转到单词中的任何位置。因此,cmp r0,#0x00f000将是可编码的,而cmp r1,#0x08efff将不可编码。因此,与编译时间常数进行比较的“使其更小”规则并不总是适用于ARM。与32位ARM和Thumb模式不同,对于cmp和cmn等指令,AArch64要么按12移位,要么不按12移位。


<vs.<=一般情况下,包括运行时变量条件

在大多数机器上的汇编语言中,<=的比较与<的比较成本相同。无论您是对其进行分支、对其进行布尔化以创建0/1整数,还是将其用作无分支选择操作的谓词(如x86 CMOV),这都适用。其他答案只解决了问题的这一部分。

但这个问题是关于C++运算符,即优化器的输入。通常情况下,它们的效率都是一样的;书中的建议听起来完全是假的,因为编译器总是可以转换他们在asm中实现的比较。但至少有一个例外,即使用<=会意外创建编译器无法优化的内容。

作为循环条件,在某些情况下,<=与<在质量上不同,因为它阻止编译器证明循环不是无限的。这会产生很大的不同,禁用自动矢量化。

与有符号溢出(UB)不同,无符号溢出定义为base-2环绕。有符号循环计数器通常是安全的,因为编译器会根据有符号溢出UB进行优化,但不会发生:++i<=size最终总是会变为false。(每个C程序员都应该知道未定义的行为)

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

编译器只能对所有可能的输入值(导致未定义行为的值除外)保持C++源代码的(定义的和合法可观察的)行为。

(简单的i<=size也会产生问题,但我认为计算上限是一个更现实的例子,它意外地为编译器必须考虑的输入引入了无限循环的可能性。)

在这种情况下,size=0导致upper_bound=UINT_MAX,而i<=UINT-MAX始终为真。因此,对于size=0,这个循环是无限的,编译器必须尊重这一点,即使您作为程序员可能从未打算传递size=0。如果编译器可以将此函数内联到调用者中,在那里它可以证明size=0是不可能的,那么很好,它可以像i<size那样进行优化。

Asm like if(!size)跳过循环;do{…}while(--size);如果循环中不需要i的实际值(为什么循环总是编译成“do…while”样式(尾部跳转)。

但这不可能是无限的:如果输入size==0,我们将得到2^n次迭代。(在for循环C中对所有无符号整数进行迭代,可以在包括零在内的所有无符号整型上表达循环,但在asm中没有进位标志是不容易的。)

由于循环计数器的环绕是一种可能,现代编译器通常只是“放弃”,而没有进行更积极的优化。

示例:从1到n的整数之和

使用无符号i<=n会破坏clang的习惯用法识别,该识别基于高斯的n*(n+1)/2公式,以封闭形式优化和(1..n)循环。

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

Godbolt编译器资源管理器上clang7.0和gcc8.2的x86-64 asm

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

但对于天真的版本,我们只是从叮当声中得到了一个愚蠢的循环。

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}
# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

GCC也不使用封闭形式,因此循环条件的选择不会对其造成真正的伤害;它通过SIMD整数加法自动矢量化,在XMM寄存器的元素中并行运行4个i值。

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.
     

它还有一个普通的标量循环,我认为它用于非常小的n,和/或无限循环的情况。

顺便说一句,这两个循环都在循环开销上浪费了一条指令(以及Sandybridge系列CPU上的一个uop)。sub-eax,1/jnz而不是添加eax,1/cmp/jcc将更有效。1 uop而不是2(sub/jcc或cmp/jcc宏融合后)。两个循环后的代码无条件地写入EAX,因此它不使用循环计数器的最终值。

我认为两者都不快。编译器在每个条件下生成具有不同值的相同机器代码。

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

我的示例if来自Linux上x86_64平台上的GCC。

编译器编写者是非常聪明的人,他们认为这些事情以及我们大多数人认为理所当然的其他事情。

我注意到,如果它不是常数,那么在这两种情况下都会生成相同的机器代码。

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3

这将高度依赖于C编译到的底层架构。某些处理器和架构可能具有等于或小于等于的显式指令,这些指令以不同的周期执行。

但这很不寻常,因为编译器可以绕过它,使它变得无关紧要。

不,它在大多数架构上不会更快。您没有指定,但在x86上,所有的积分比较通常将在两个机器指令中实现:

测试或cmp指令,用于设置EFLAGS以及Jcc(跳转)指令,具体取决于比较类型(和代码布局):jne-如果不等于-->ZF=0,则跳转jz-如果零(等于)-->ZF=1则跳转jg-如果大于-->ZF=0且SF=OF,则跳转(等等)


示例(为简洁起见编辑)使用$gcc-m32-S-masm=inteltest.c编译

    if (a < b) {
        // Do something 1
    }

编译到:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

And

    if (a <= b) {
        // Do something 2
    }

编译到:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

因此,两者之间的唯一区别是jg与jge指令。这两者将花费相同的时间。


我想指出的是,没有任何东西表明不同的跳转指令需要相同的时间。这个问题回答起来有点棘手,但我可以给出以下答案:在“英特尔指令集参考”中,它们都被分组在一条公共指令Jcc(如果满足条件则跳转)下。根据附录C中的《优化参考手册》进行了相同的分组。延迟和吞吐量。

Latency—执行核心,以完成形成的所有μ操作的执行指令。

吞吐量—需要的时钟周期数等待发出端口可以接受相同的指令再一次对于许多指令,指令的吞吐量可以是显著低于其延迟

Jcc的值为:

      Latency   Throughput
Jcc     N/A        0.5

Jcc上有以下脚注:

条件跳转指令的选择应基于第3.4.1节“分支预测优化”的建议,以提高分支的可预测性。当成功预测分支时,jcc的延迟实际上为零。

因此,在英特尔文档中,对一条Jcc指令的处理方式与其他指令没有任何区别。

如果考虑用于实现指令的实际电路,可以假设EFLAGS中的不同位上有简单的“与/或”门,以确定是否满足条件。因此,没有理由让一条测试两个位的指令比只测试一个位花费更多或更少的时间(忽略比时钟周期短得多的门传播延迟)


编辑:浮点

x87浮点也是如此:(与上面的代码几乎相同,但使用double而不是int。)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret

从历史上看(我们所说的是20世纪80年代和90年代初),有些架构是这样的。根本问题是整数比较本质上是通过整数减法实现的。这导致了以下情况。

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

现在,当A<B时,减法必须借用高位才能正确进行减法,就像你用手进行加法和减法时一样。这个“借用”位通常被称为进位位,可以通过分支指令进行测试。如果减法等于零,则将设置第二位,称为零位,这意味着相等。

通常至少有两条条件分支指令,一条在进位位上分支,另一条在零位上分支。

现在,为了了解问题的核心,让我们扩展上一个表,以包括进位和零位结果。

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

因此,实现a<B的分支可以在一条指令中完成,因为进位位仅在这种情况下是清除的,即,

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

但是,如果我们想进行小于或等于的比较,我们需要对零标志进行额外的检查,以捕捉相等的情况。

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

因此,在某些机器上,使用“小于”比较可能会节省一条机器指令。这在亚兆赫处理器速度和1:1 CPU与内存速度比的时代是相关的,但在今天几乎完全不相关。