题 <快于<=?


我正在读一本作者所说的书 if( a < 901 ) 比...更快 if( a <= 900 )

与此简单示例不完全相同,但循环复杂代码略有性能变化。我想这必须对生成的机器代码做一些事情,如果它甚至是真的。


1372
2017-08-27 02:10


起源


鉴于其历史意义,答案的质量以及其他最重要的问题,我认为没有理由为什么应该关闭这个问题(特别是没有删除,因为投票目前正在显示)。 性能 保持开放。最多应锁定。而且,即使问题本身是错误的/天真的,它出现在书中的事实意味着原始的错误信息存在于某些地方的“可靠”来源中,因此这个问题具有建设性,因为它有助于清除它。 - Jason C
你从来没有告诉过我们 哪本书 你指的是。 - Jonathon Reinhart
打字 < 比打字快两倍 <=。 - Deqing
8086年确实如此。 - Joshua
upvotes的数量清楚地表明,有数百人严重过度优化。 - m93a


答案:


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

  • 一个 test 要么 cmp 指令,设定 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:

所以两者之间的唯一区别是a jg 与a jge 指令。这两个将花费相同的时间。


我想解释一下,没有任何迹象表明不同的跳转指令需要相同的时间。这个回答有点棘手,但这就是我能给出的:在 英特尔指令集参考,他们都在一个共同的指令下组合在一起, Jcc (如果满足条件,则跳转)。同样的分组是在 优化参考手册,附录C.延迟和吞吐量。

潜伏  - 所需的时钟周期数   执行核心来完成所有形成的μops的执行   一个指令。

吞吐量  - 所需的时钟周期数   在问题端口可以自由接受相同的指令之前等待   再次。对于许多指令,指令的吞吐量可以是   显着低于其延迟

的值 Jcc 是:

      Latency   Throughput
Jcc     N/A        0.5

以下脚注 Jcc

7)条件跳转指令的选择应基于第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

1571
2017-08-27 02:13



@Dyppl实际上 jg 和 jnle 是同一个指令, 7F :-) - Jonathon Reinhart
更不用说优化器可以修改代码,如果一个选项确实比另一个更快。 - Elazar Leibovich
仅仅因为某些事物导致相同数量的指令并不一定意味着执行所有这些指令的总时间将是相同的。实际上可以更快地执行更多指令。每个周期的指令不是固定的数字,它根据指令而有所不同。 - jontejj
@jontejj我非常清楚这一点。你有没有 读 我的答案?我没有说同样的事情 数 在说明中,我说它们编译成基本上完全相同 instrutcions,除了一个跳转指令正在查看一个标志,另一个跳转指令正在查看两个标志。我相信我已经提供了足够的证据来证明它们在语义上是相同的。 - Jonathon Reinhart
@jontejj你说得非常好。对于这个答案获得尽可能多的可见性,我应该给它一点点清理。感谢您的反馈。 - Jonathon Reinhart


历史上(我们说的是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到内存速度比的时代相关,但它现在几乎完全无关紧要。


554
2017-08-27 17:53



此外,像x86这样的架构实现了类似的指令 jge,它测试零和符号/进位标志。 - greyfade
+1 从历史的角度来看。 - sbi
这在8080上是正确的。它有指令跳零和跳减号,但没有可以同时测试两者。
+1这是解释为什么作者可能写下他所做的事情的唯一答案。 - Leo
即使在8080上 <= 测试可以实现 一 交换操作数和测试的指令 not < (相当于 >=)这是理想的 <= 使用交换操作数: cmp B,A; bcs addr。这就是英特尔省略了这项测试的原因,他们认为这是多余的,你不能在那些时候提供冗余指令:-) - Gunther Piez


假设我们正在谈论内部整数类型,那么没有可能比另一个更快。它们在语义上显然是相同的。他们都要求编译器做同样的事情。只有一个可怕的破坏编译器会为其中一个生成劣质代码。

如果有一些平台在哪里 < 比...更快 <= 对于简单的整数类型,编译器应该 总是 兑换 <= 至 < 对于常数。任何编译器都不是一个糟糕的编译器(对于那个平台)。


84
2017-08-27 02:31



+1我同意。也不 < 也不 <= 有速度,直到编译器决定他们将具有哪种速度。对于编译器来说,这是一个非常简单的优化,当你考虑它们通常已经执行死代码优化,尾调用优化,循环提升(和有时展开),各种循环的自动并行化等等... 为什么浪费时间思考过早的优化? 获取原型运行,对其进行分析以确定最重要的优化所在的位置,按重要性顺序执行这些优化,并在测量进度的过程中再次执行配置文件... - autistic
仍有一些边缘情况,其中具有一个常数值的比较在<=时可能较慢,例如,当转换时 (a < C) 至 (a <= C-1) (对于某些常数 C)原因 C 更难以在指令集中编码。例如,指令集可能能够在比较中以紧凑的形式表示从-127到128的有符号常量,但是该范围之外的常量必须使用更长,更慢的编码或完全的另一指令来加载。所以比较一下 (a < -127) 可能没有直接的转变。 - BeeOnRope
@BeeOnRope问题不在于执行因其中包含不同常数而不同的操作是否会影响性能, 表达 该 相同 使用不同常量的操作可能会影响性能。所以我们不是在比较 a > 127 至 a > 128 因为你别无选择,你可以使用你需要的那个。我们正在比较 a > 127 至 a >= 128,它们不需要不同的编码或不同的指令,因为它们具有相同的真值表。任何一个编码都是另一个的编码。 - David Schwartz
我以一般方式回应你的陈述“如果某个平台[<=较慢],编译器应该总是转换 <= 至 < 对于常数“。据我所知,这种转变涉及改变常数。例如, a <= 42 编译为 a < 43因为 < 是比较快的。在某些边缘情况下,这种转换不会有成效,因为新常量可能需要更多或更慢的指令。当然 a > 127 和 a >= 128 是等价的,编译器应该以(相同)最快的方式编码两种形式,但这与我说的不一致。 - BeeOnRope


我发现两者都不快。编译器在每个条件下使用不同的值生成相同的机器代码。

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

66
2017-08-27 02:16



请注意,这是特定于x86的。 - Michael Petrotta
我想你应该用它 if(a <=900) 证明它生成完全相同的asm :) - Lipis
@AdrianCornish对不起..我编辑了..它或多或少相同..但如果你改变第二个如果<= 900那么asm代码将完全相同:)它现在几乎相同..但你知道..为OCD :) - Lipis
@Boann可能会减少到if(true)并完全消除。 - Qsario
没有人指出这种优化 仅适用于不断比较。我可以保证会 不 这样做是为了比较两个变量。 - Jonathon Reinhart


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

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 - 条件寄存器按位OR)将这两个位组合成一个。所以 compare_loose 需要五条指令,而 compare_strict 需要四个。

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

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

但是这会错误地处理NaN。 NaN1 <= NaN2 和 NaN1 > NaN2 需要评估为假。


48
2017-08-27 18:32



幸运的是它在x86(x87)上不能像这样工作。 fucomip 设置ZF和CF. - Jonathon Reinhart
@JonathonReinhart:我认为你误解了PowerPC正在做什么 - 条件寄存器 cr  是 等同于旗帜 ZF 和 CF 在x86上。 (虽然CR更灵活。)海报正在谈论的是将结果移动到GPR:它在PowerPC上有两条指令,但x86有条件移动指令。 - Dietrich Epp
@DietrichEpp在我的陈述之后我想要添加的内容:然后你可以根据EFLAGS的值立即跳转。对不起,不清楚。 - Jonathon Reinhart
@JonathonReinhart:是的,您也可以根据CR的值立即跳转。答案不是谈论跳跃,这是额外指令的来源。 - Dietrich Epp


也许这本未命名的书的作者已经读过这本书了 a > 0 比跑得快 a >= 1 并认为这是普遍的。

但这是因为一个 0 涉及(因为 CMP 可以,取决于架构,取而代之,例如同 OR)而不是因为 <


34
2017-08-27 13:05



当然,在“调试”版本中,但它需要一个糟糕的编译器 (a >= 1) 比跑得慢 (a > 0),因为前者可以通过优化器简单地转换为后者。 - BeeOnRope
@BeeOnRope有时候我很惊讶优化器可以优化的复杂事物以及它不能做到的简单事情。 - glglgl
实际上,并且总是值得检查asm输出,因为它很重要。也就是说,上述转换是非常基础的,甚至在简单的编译器中也已经进行了数十年。 - BeeOnRope


至少,如果这是真的,编译器可以轻而易举地优化<= b到!(a> b),所以即使比较本身实际上更慢,除了最天真的编译器之外,你不会注意到差别。


29
2017-08-27 09:23



为什么!(a> b)是<= b的优化版本。不是!(a> b)2个操作合二为一? - Abhishek Singh
@AbhishekSingh NOT 只是由其他指令(je 与 jne) - Pavel Gatnar


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


15
2017-08-27 08:25