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,因此它不使用循环计数器的最终值。

其他回答

即使有差异,你也不应该注意到。此外,在实践中,除非你要使用一些神奇的常数,否则你必须做一个额外的a+1或a-1来使条件成立,这无论如何都是一个非常糟糕的实践。

它们的速度相同。也许在某些特殊的架构中,他/她所说的是对的,但在x86家族中,至少我知道他们是一样的。因为为此,CPU将执行一个减法(a-b),然后检查标志寄存器的标志。该寄存器的两位被称为ZF(零标志)和SF(符号标志),它在一个周期内完成,因为它将通过一个掩码操作完成。

在C和C++中,编译器的一个重要规则是“仿佛”规则:如果执行X的行为与执行Y的行为完全相同,那么编译器可以自由选择使用哪一个。

在您的情况下,“a<901”和“a<=900”总是具有相同的结果,因此编译器可以自由编译任一版本。无论出于什么原因,如果一个版本更快,那么任何高质量的编译器都会为更快的版本生成代码。因此,除非您的编译器生成异常糟糕的代码,否则两个版本的运行速度将相等。

现在,如果你有一种情况,两位代码总是会产生相同的结果,但编译器很难证明,和/或编译器很难证实哪个版本更快,那么你可能会得到不同的代码以不同的速度运行。

PS如果处理器支持单字节常量(更快)和多字节常量(更慢),则原始示例可能以不同的速度运行,因此与255(1字节)进行比较可能比与256(2字节)进行对比更快。我希望编译器做任何更快的事情。

对于浮点代码,甚至在现代体系结构上,<=比较可能确实会慢一些(一条指令)。这是第一个函数:

int compare_strict(double a, double b) { return a < b; }

在PowerPC上,首先执行浮点比较(更新条件寄存器cr),然后将条件寄存器移动到GPR,将“比较小于”位移位到位,然后返回。它需要四个指令。

现在考虑一下这个函数:

int compare_loose(double a, double b) { return a <= b; }

这需要与上面的compare_strict相同的工作,但现在有两个有趣的位:“小于”和“等于”。这需要一个额外的指令(cror-condition寄存器逐位OR)将这两个位组合为一。因此,compare_sloose需要五条指令,而compare_sstrict需要四条指令。

您可能认为编译器可以这样优化第二个函数:

int compare_loose(double a, double b) { return ! (a > b); }

然而,这将错误地处理NaN。NaN1<=NaN2和NaN1>NaN2都需要评估为假。

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

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