将 < 比快 < =?

Is < faster than <=?

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

在此简单示例中,不完全但复杂循环的代码中有轻微的性能变化。我假设这将不得不进行一些处理生成的机器码以防甚至真。

2012-08-27 02:10:12
问题评论:

看其历史意义,答案和性能的其他热门问题仍保持打开状态的事实的质量给定的无端为什么这个问题应该被关闭 (和尤其是未删除,为当前正在进行的选票)。最应该锁定它。同时,即使本身的问题是,提供错误信息 naive,它在一本书中所出现的事实意味着原始错误信息"可靠"源在某处,在那里存在,这个问题因此是建设性的它有助于澄清的。

您永远不会未告诉我们哪些书籍所引用。

键入<是比键入快两倍<=.

这是这个问题很好,可能会在原理涉及如 Python 的解释的语言感兴趣。应考虑如发布一个新的问题"是 > 比快 > = 在 Python 中吗?"但可以被视为重复的问题。欢迎使用的指南。

回答:

否,不会更快地在大多数体系结构上。您未指定,但在 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:

因此两者之间的唯一区别是与jge指令jg这两个会花同样多的时间。


我想解决的评论没有任何指示表明不同跳转指令,花同样多的时间。这就是有点难回答,但这是我可以提供︰ 在英特尔指令集参考,它们是所有分组在一起在一个公共指令, Jcc (Jump 满足条件时)。位于同一分组在一起依照优化参考手册 》,在附录 C.延迟和吞吐量。

滞后时间— 个执行核心,完成所有窗体说明 μops 的执行所需的时钟周期数。

吞吐量— 等待问题端口可以自由地接受相同的指令所需的时钟周期数。对于许多指令,指令的吞吐量可以大大小于其滞后时间

Jcc值包括︰

      Latency   Throughput
Jcc     N/A        0.5

使用Jcc上以下脚注:

7) 条件跳转指令的选择应基于节部分 3.4.1,"分支预测优化"的建议,以提高可预测性的分支。当分支成功预测时, jcc的反应实际上是零。

因此,英特尔文档中的任何内容曾经对待一个Jcc指令任何方式不同于其他。

如果一想到用于实现指导的实际电路,一个可以假定会有简单和/或EFLAGS,以确定是否满足条件的不同位上的关口。然后,没有理由指令测试两位应采取任何更多或更少的时间比测试只有一个 (Ignoring 门传播延迟,这是比时钟周期少得多。)


编辑︰ 浮动点

这对于 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

但这答案中的任何内容表明该jg的时间同一个jnle

@Dyppl 实际上jgjnle是同一指令是7F :-)

更不必说优化程序可以修改代码,如果确实是快于另一个选项。

只是因为东西产生相同数量的说明并不一定意味着总和总时间执行所有这些指令都是相同。实际上未能更快地执行多个指令。说明每个周期不固定的数量,它取决于指令。

我非常了解的 @jontejj。做您阅读甚至我的答案吗?我没有状态相同数目的说明有什么,我说,它们被编译为本质上完全相同instrutcions、 除一个跳转指令观察一个标志,和其他跳转指令看两个标志。我认为我已提供足够的证据,以表明它们是在语义上相同超过。

从历史上看 (我们正在讨论上世纪 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 与内存速度比率,纪元中但是目前几乎完全没有意义。

此外,如 x86 体系结构实现像jge,也不能测试这两个零号/携带标志说明。

历史视角+1

在 8080 上是如此。它已说明跳上零并跳转负,但不可以同时测试两个。

+ 1 这是解释为什么作者可能已编写了他做的唯一答案。

即使在 8080 上<=测试可以实现在条指令,具有交换操作数和测试not < (相当于>=) 这是所需的<=与交换操作数︰ cmp B,A; bcs addr英特尔通过省略此测试的原因,它们被视为冗余且您无法承受冗余说明在这些时间:-)

假设我们在讨论内部整数类型,没有能更快地比其他任何可能的方式。它们显然语义上相同。它们均要求编译器执行完全相同的操作。出现严重中断的编译器将生成代码较差的一种。

如果有一些平台在<已快于<=对于简单的整数类型,编译器应该总是转换<=<为常数。没有任何编译器,那只不过是坏的编译器 (平台)。

我同意 + 1。<<=直到编译器决定它们将具有哪些速度有速度。这是非常简单的优化的编译器时,他们通常已经执行死代码优化、 尾部调用优化、 提升循环 (和展开,在某些情况下),自动 parallelisation 的各种循环,等等...为什么浪费时间想过早的 optimisations?获取运行时,配置文件来确定最大 optimisations 的所在,按重要性的顺序执行这些 optimisations,沿测量进度的方法重新分析的原型...

还有有一个常数值进行比较可能是慢下某些边缘情况下 < =,例如,当转换(a < C)(a <= C-1) (对于某些常数C) 导致C会更难编码中的指令集。例如,指令集可以表示有符号的常量-127 至 128 压缩形式的比较,但该范围以外的常量必须使用更长、 更慢的编码,或者另一个指令完全加载。因此,比较喜欢(a < -127)可能没有一个简单的转换。

@BeeOnRope 问题是是否执行操作,因为它们有不同的常数不同可能会影响性能,但是否表示相同的操作,使用不同的常数可能会影响性能。因为那里别无选择,我们不比较a > 127a > 128 ,因此您可以使用所需的一个。我们在比较a > 127a >= 128,因为它们具有相同的真值表,它不能要求其他编码或不同的指令。任何一个编码是同样的编码另一个。

我已响应您的语句以常规方式,"如果有一些平台位置 [< = 已慢] 编译器应始终将转换<=<常数"。据我所知,该转换将涉及更改该常数。例如, a <= 42因为<快被编译为a < 43在某些边缘情况下,这种转换不会富有成效因为新的常量可能需要更多或更慢的说明进行操作。当然a > 127a >= 128等效和编译器应编码两个窗体中 (相同) 的快捷方式,但这并不是与我所说的内容不一致。

我看到,既不是更快。编译器将生成相同的机器代码中使用不同的值的每个条件。

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

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

我的示例if是 GCC 从 Linux 在 x86_64 平台上。

编译器编写器是相当聪明的人,,他们认为这些事情和许多其他的大多数人采取理所当然的。

我注意到是否它不是一个常数,相同的计算机代码将生成两种情况下。

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

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

请注意,这是特定于 x86。

我认为,应该使用if(a <=900) ,来演示它:) 生成完全相同的 asm

@AdrianCornish 很抱歉.我对其进行编辑.这或多或少是相同.但是,如果您更改为第二个 if < = 900 则 asm 代码将是完全相同的:)它是几乎相同的现在.但您知道.对于 OCD:)

If 可能获得减少的 @Boann (真) 和完全杜绝。

没有人已经指出的仅适用于恒定比较此优化。我可以保证它将能完成这样比较两个变量。

对浮点点代码 < = 比较确实有所下降 (由一条指令) 即使在现代的体系结构上。以下是第一个函数︰

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。

值得庆幸的是它不像这样能在 x86 (x 87)。fucomip设置 ZF 和 CF。

@JonathonReinhart︰ 我认为您是误解 PowerPC 正在做什么 — 条件注册cr 等价于如ZFCF在 x86 上的标志。(尽管 CR 是更灵活。海报谈论到 GPR 移动结果︰ 其中 PowerPC,采用两条指令,但 x86 条件移动指令。

@DietrichEpp 我打算添加后我的语句︰ 然后,可以立即跳的基于 EFLAGS 的值。很抱歉没有被清除。

@JonathonReinhart︰ 是的和您还可以立即跳转基于 CR 的值。答案不谈,这是额外的指令来自何处。

内容来源于Stack Overflow Is < faster than <=?
请输入您的翻译

Is < faster than <=?

确认取消