< 快于 <= 吗?

我正在读一本书,作者说if( a < 901 )if( a <= 900 )快。

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

答案

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

  • testcmp指令,用于设置EFLAGS
  • 还有一条Jcc (跳转)指令 ,具体取决于比较类型(和代码布局):
    • jne如果不相等则跳转 -> ZF = 0
    • jz如果为零(等于)则跳转 -> ZF = 1
    • jg更大时跳转 -> ZF = 0 and SF = OF
    • (等等...)

示例 (为简洁起见,已编辑)与$ 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:

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


我想指出的是,没有任何内容表明不同的跳转指令花费相同的时间。回答这个问题有些棘手,但是我可以提供以下信息:在《 英特尔指令集参考》中 ,它们都按照一条通用指令Jcc组合在一起(如果满足条件则跳转)。在 “ 优化参考手册 ” 的附录 C. 延迟和吞吐量中将相同的分组在一起。

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

吞吐量(T 吞吐率) —在发布端口可以自由再次接受同一指令之前需要等待的时钟周期数。对于许多指令,一条指令的吞吐量可以大大小于其延迟

Jcc的值是:

Latency   Throughput
Jcc     N/A        0.5

以下关于Jcc脚注:

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

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

如果考虑用于实现指令的实际电路,则可以假定EFLAGS不同位上将存在简单的 AND / OR 门,以确定是否满足条件。这样,没有理由测试一个两位的指令所花费的时间要比一个测试一个位所花费的时间更多或更少(忽略门传播延迟,这比时钟周期要短得多)。


编辑:浮点数

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

从历史上看(我们所说的是 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

因此,可以在一条指令中实现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 与内存速度比的时代,这是相关的,但是今天几乎完全不相关。

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

如果在某些平台上,对于简单整数类型, <快于<= ,则编译器应始终将常量的<=转换为< 。任何不适合该平台的编译器都将是一个糟糕的编译器。

我看到两者都不快。编译器会在每种情况下以不同的值生成相同的机器代码。

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

对于浮点代码,即使在现代体系结构上,<= 比较的确可能会更慢(通过一条指令)。这是第一个功能:

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 <= NaN2NaN1 > NaN2需要评估为 false。

也许那本未命名的书的作者已经读到a > 0运行速度比a >= 1运行速度快,并且普遍认为这是正确的。

但这是因为涉及到0 (因为CMP可以取决于体系结构,例如用OR代替),而不是因为<

至少,如果这是真的,则编译器可以轻松地将 <= b 优化为!(a> b),因此,即使比较本身实际上速度较慢,对于除最幼稚的编译器之外的所有编译器,您都不会注意到差异。

它们具有相同的速度。也许在某些特殊的体系结构中,他 / 她说的是正确的,但是至少在 x86 系列中,我知道它们是相同的。因为这样做,CPU 将进行减法(a-b),然后检查标志寄存器的标志。该寄存器的两位分别称为 ZF(零标志)和 SF(符号标志),并且在一个周期内完成,因为它将用一个掩码操作来完成。

这将高度依赖于 C 编译到的基础体系结构。一些处理器和体系结构可能具有显式的指令,用于等于或小于和等于的指令,它们以不同数量的周期执行。

但是,这将是非常不寻常的,因为编译器可以解决该问题,因此不相关。

TL; DR答案

对于体系结构,编译器和语言的大多数组合,它不会更快。

完整答案

其他答案集中在x86架构上,我不知道ARM架构(您的示例汇编程序似乎是这样)足以对生成的代码进行特别注释,但这只是一个微优化的示例,它非常架构的具体而言,并且有可能是反优化,也有可能是优化

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

某些架构中,这可能是一种优化,但我知道至少有一种架构可能是相反的。古老的Transputer体系结构只有等于大于或等于的机器代码指令,因此所有比较都必须根据这些原语进行。

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

像这样的微优化是优化还是反优化取决于您使用的特定体系结构,因此养成使用特定于体系结构的微优化的习惯通常是一个坏主意,否则您可能会本能地在不适当的时候使用它,而这恰恰是您所读的书所倡导的。