c++ - < 比 <= 快吗？

Question

if (a < 901)比快吗if (a <= 900)？

与这个简单的示例不完全一样，但循环复杂代码的性能略有变化。我想这必须与生成的机器代码有关，以防万一。

score 1792 · Accepted Answer

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

一个test或cmp指令，它设置EFLAGS
还有一个Jcc（跳转）指令，具体取决于比较类型（和代码布局）：
jne- 如果不相等则跳转 -->ZF = 0
jz- 如果为零（等于）则跳转-->ZF = 1
jg- 大于则跳转 -->ZF = 0 and SF = OF
（ETC...）

示例（为简洁而编辑）编译为$ gcc -m32 -S -masm=intel test.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:

和

    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指令。两者将花费相同的时间。

我想解决没有任何迹象表明不同的跳转指令需要相同的时间的评论。这个回答有点棘手，但这是我可以给出的：在Intel Instruction Set Reference中，它们都被组合在一个通用指令下Jcc（如果满足条件则跳转）。在优化参考手册的附录 C. 延迟和吞吐量中进行了相同的分组。

延迟— 执行内核完成构成指令的所有 μop 的执行所需的时钟周期数。

吞吐量——在发布端口可以再次自由地接受相同指令之前需要等待的时钟周期数。对于许多指令，一条指令的吞吐量可能远低于其延迟

的值为Jcc：

      Latency   Throughput
Jcc     N/A        0.5

附上以下脚注Jcc：

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

因此，英特尔文档中的任何内容都不会将一条Jcc指令与其他指令区别对待。

如果考虑用于实现指令的实际电路，可以假设在中的不同位上会有简单的 AND/OR 门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

score 613 · Accepted Answer

从历史上看（我们谈论的是 1980 年代和 1990 年代初期），有一些架构确实如此。根本问题是整数比较本质上是通过整数减法实现的。这导致了以下情况。

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

因此，实现分支 forA < 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 与内存速度比的时代是相关的，但在今天几乎完全无关紧要。

score 97 · Accepted Answer

假设我们谈论的是内部整数类型，那么一种方法不可能比另一种更快。它们显然在语义上是相同的。他们都要求编译器做同样的事情。只有严重损坏的编译器会为其中之一生成劣质代码。

如果有一些平台<比<=简单整数类型更快，编译器应该总是转换<=为<常量。任何没有的编译器都只是一个糟糕的编译器（对于那个平台）。

score 69 · Accepted Answer

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

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

score 54 · Accepted Answer

对于浮点代码，即使在现代架构上， <= 比较也可能确实更慢（通过一条指令）。这是第一个功能：

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- 条件寄存器按位或）将这两位合并为一个。所以compare_loose需要五个指令，而compare_strict需要四个。

你可能认为编译器可以像这样优化第二个函数：

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

但是，这将错误地处理 NaN。NaN1 <= NaN2并且NaN1 > NaN2需要两者都评估为假。

score 34 · Accepted Answer

也许那本无名书的作者读过的书比它a > 0运行得更快，a >= 1并且认为这是普遍正确的。

但这是因为0涉及 a （因为CMP可以，取决于架构，例如替换为OR）而不是因为<.

score 30 · Accepted Answer

至少，如果这是真的，编译器可以简单地将 a <= b 优化为 !(a > b)，因此即使比较本身实际上更慢，除了最天真的编译器之外，您不会注意到任何差异.

score 17 · Accepted Answer

TL;DR答案

对于架构、编译器和语言的大多数组合，<不会比<=.

完整答案

其他答案集中在x86架构上，我不知道ARM架构（您的示例汇编程序似乎是）足以专门评论生成的代码，但这是一个非常架构的微优化示例具体的，并且很可能是一种反优化，因为它是一种优化。

因此，我建议这种微优化是货物崇拜编程的一个例子，而不是最佳软件工程实践。

反例

可能有一些架构是一种优化，但我知道至少有一种架构可能相反。古老的Transputer架构只有等于和大于或等于的机器代码指令，因此所有比较都必须从这些原语构建。

即便如此，在几乎所有情况下，编译器都可以以这样一种方式对评估指令进行排序，即在实践中，没有任何比较比其他任何比较有任何优势。但最坏的情况是，它可能需要添加反向指令 (REV) 来交换操作数堆栈上的顶部两项。这是一个单字节指令，需要一个周期才能运行，因此开销可能最小。

概括

像这样的微优化是优化还是反优化取决于您使用的特定架构，因此养成使用特定架构微优化的习惯通常是个坏主意，否则您可能会本能地在不合适的时候使用一个，看起来这正是你正在阅读的书所提倡的。

score 15 · Accepted Answer

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

score 14 · Accepted Answer

这将高度依赖于 C 编译到的底层架构。一些处理器和体系结构可能具有明确的等于、小于和等于指令，它们以不同的周期数执行。

不过，这将是非常不寻常的，因为编译器可以解决它，使其无关紧要。

score 6 · Accepted Answer

即使有任何差异，您也不应该注意到差异。此外，在实践中，除非您要使用一些魔术常数，否则您必须做额外的事情a + 1或使条件成立，这无论如何都是非常糟糕的做法。a - 1

score 5 · Accepted Answer

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

对于 ARM，能够编码为立即数取决于能够将窄域旋转到单词中的任何位置。所以cmp r0, #0x00f000将是可编码的，而cmp r0, #0x00efff不会。因此，用于比较与编译时常量的缩小规则并不总是适用于 ARM。与 32 位 ARM 和 Thumb 模式不同，对于cmp和之类的指令，AArch64 要么移位 12 位，要么不移位，而不是任意旋转。cmn

< 与 <= 通常，包括运行时变量条件

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

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

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

与有符号溢出 (UB) 不同，无符号溢出被明确定义为 base-2 环绕。带符号的循环计数器通常可以避免这种情况，因为编译器不会基于有符号溢出 UB 进行优化：++i <= size最终总是会变为假。（每个 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 likeif(!size) skip the loop; do{...}while(--size);是优化循环的一种通常有效的方法，如果循环内部不需要for( i<size )实际值（为什么循环总是编译成“do...while”样式（尾跳转）？）。i

但这不会是无限的：如果使用输入size==0，我们将获得 2^n 次迭代。（在 for 循环 C 中对所有无符号整数进行迭代使得可以在包括零在内的所有无符号整数上表达一个循环，但是没有进位标志就像在 asm 中那样不容易。）

由于循环计数器的环绕是可能的，现代编译器通常只是“放弃”，并且几乎没有积极地优化。

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

使用 unsignedi <= n会破坏 clang 的惯用语识别，该惯用语识别sum(1 .. n)基于高斯n * (n+1) / 2公式以封闭形式优化循环。

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

但是对于幼稚的版本，我们只是从 clang 中得到一个愚蠢的循环。

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 整数加法自动矢量化，i在 XMM 寄存器的元素中并行运行 4 个值。

# "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 上的一个微指令）。 sub eax,1/jnz而不是add eax,1/cmp/jcc 会更有效。1 uop 而不是 2（在 sub/jcc 或 cmp/jcc 的宏融合之后）。两个循环之后的代码无条件地写入 EAX，因此它没有使用循环计数器的最终值。

score 4 · Accepted Answer

您可以说该行在大多数脚本语言中是正确的，因为多余的字符会导致代码处理速度稍慢。但是，正如最重要的答案所指出的那样，它在 C++ 中应该没有效果，并且使用脚本语言所做的任何事情都可能并不关心优化。

score 3 · Accepted Answer

仅当创建计算机的人不擅长布尔逻辑时。他们不应该这样。

每个比较 ( >= <= > <) 都可以以相同的速度完成。

每一个比较是什么，只是一个减法（差异），看看它是正面的还是负面的。
（如果msb设置了，则为负数）

如何检查a >= b？子a-b >= 0检查是否a-b为正。
如何检查a <= b？子0 <= b-a检查是否b-a为正。
如何检查a < b？子a-b < 0检查是否a-b为负。
如何检查a > b？子0 > b-a检查是否b-a为负。

简而言之，计算机可以在给定操作的底层执行此操作：

a >= b== msb(a-b)==0
a <= b== msb(b-a)==0
a > b== msb(b-a)==1
a < b==msb(a-b)==1

==0当然，计算机实际上并不需要这样做==1。
因为它可能只是从电路中==0反转。msb

无论如何，他们肯定不会a >= b被计算为a>b || a==b大声笑

c++ - < 比 <= 快吗？

14 回答 14

TL;DR答案

完整答案

反例

概括

< 与 <= 通常，包括运行时变量条件

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

Related

Reference