< 比 <= 快吗?

Is < faster than <=?

提问人:Vinícius 提问时间:8/27/2012 最后编辑:ivaigultVinícius 更新时间:9/2/2022 访问量:149335

问:

比 ?if (a < 901)if (a <= 900)

与这个简单示例中不完全相同,但在循环复杂代码上存在轻微的性能变化。我想这必须与生成的机器代码有关,以防万一它是真的。

C++ C 性能 程序集 关系运算符

评论

193赞 Jason C 3/23/2014
鉴于这个问题的历史意义、答案的质量以及表现中其他最重要的问题仍然悬而未决的事实,我认为没有理由关闭这个问题(尤其是不要删除,正如目前的投票结果所示)。最多它应该被锁定。此外,即使问题本身是误导/幼稚的,它出现在一本书中的事实也意味着原始的错误信息存在于某个地方的“可信”来源中,因此这个问题是建设性的,因为它有助于澄清这一点。
10赞 Joshua 11/16/2016
在 8086 上确实如此。
2赞 Mikhail T. 1/27/2021
所有的答案似乎都是关于C的,而这个问题被标记为C++ - 根本没有告诉任何给定的...<<=a
0赞 Peter Cordes 11/26/2021
@Joshua:8086 具有 and(以及等效的无符号分支条件)。所以不,如果我们谈论的是普通的比较和分支,它在 x86 上并不快,而且从来没有。汇编 - CMP 之后的 JG/JNLE/JL/JNGE - 这些指令自 8086 以来一直存在。我建议删除您之前包含错误信息的评论,或澄清您的特殊情况。在 asm 中,允许可以保存字节的较小即时常量,因此 GCC 会为您转换jgjge<
0赞 Joshua 11/27/2021
@PeterCordes:出于某种原因,我学习的编译器总是会生成,而不是在编译 x86 时生成,但直接生成没有问题。正如你所指出的,这是非常愚蠢的,我有理由相信现代编译器不会这样做。但是你忍受了你所拥有的编译器。jl +2 jmp ...jgejg ...

答:

1839赞 Jonathon Reinhart 8/27/2012 #1

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

  • A 或指令,其中设置testcmpEFLAGS
  • 以及 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


我想解决一个评论,即没有任何迹象表明不同的跳转指令需要相同的时间。这个问题有点难以回答,但我可以给出以下结论:在《英特尔指令集参考》中,它们都按照一个通用指令组合在一起(如果满足条件,则跳转)。在《优化参考手册》的附录 C. 延迟和吞吐量中,进行了相同的分组。Jcc

延迟 — 所需的时钟周期数 执行核心,用于完成所有 μOPS 的执行 指令。

吞吐量 — 所需的时钟周期数 等待发出端口可以自由接受相同的指令 再。对于许多指令,指令的吞吐量可以是 明显小于其延迟

的值为:Jcc

      Latency   Throughput
Jcc     N/A        0.5

脚注如下:Jcc

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

因此,英特尔文档中没有任何内容将一条指令与其他指令区别对待。Jcc

如果考虑用于实现指令的实际电路,可以假设 中的不同位上有简单的 AND/OR 门,以确定是否满足条件。因此,没有理由说,测试两个位的指令所花费的时间应该比只测试一个位的指令多或少(忽略门传播延迟,它远小于时钟周期)。EFLAGS


编辑:浮点

这也适用于 x87 浮点:(与上面的代码几乎相同,但用 而不是 。doubleint

        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

评论

248赞 Jonathon Reinhart 8/27/2012
@Dyppl实际上并且是相同的指令,:-)jgjnle7F
24赞 Elazar Leibovich 8/28/2012
更不用说如果一个选项确实比另一个选项快,优化器可以修改代码。
4赞 jontejj 6/1/2013
仅仅因为某些东西产生相同数量的指令并不一定意味着执行所有这些指令的总时间是相同的。实际上,可以更快地执行更多指令。每个周期的指令不是一个固定的数字,它因指令而异。
25赞 Jonathon Reinhart 6/1/2013
@jontejj我非常清楚这一点。你读过我的答案吗?我没有说明相同数量的指令,我说过它们被编译为基本相同的指令,除了一个跳转指令正在查看一个标志,而另一个跳转指令正在查看两个标志。我相信我已经提供了足够的证据来证明它们在语义上是相同的。
5赞 Jonathon Reinhart 6/3/2013
@jontejj 你说得非常好。为了尽可能多地了解这个答案,我可能应该给它一点清理。感谢您的反馈。
14赞 Telgin 8/27/2012 #2

这将高度依赖于 C 编译到的底层架构。某些处理器和体系结构可能具有等于或小于和等于的显式指令,这些指令以不同的周期数执行。

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

评论

2赞 Martin York 8/27/2012
如果 cyles 存在差异。1)它不会被检测到。2)任何有价值的编译器都已经在不改变代码含义的情况下从慢速形式转换为快速形式。因此,植入的结果指令将是相同的。
0赞 Telgin 8/28/2012
完全同意,无论如何,这将是一个非常微不足道和愚蠢的差异。当然,在一本应该与平台无关的书中,没有什么可提及的。
0赞 Martin York 8/29/2012
@lttlrck:我明白了。花了我一会儿(愚蠢的我)。不,它们是无法检测到的,因为还有很多其他事情发生,使它们无法进行测量。处理器停止/缓存未命中/信号/进程交换。因此,在正常的操作系统情况下,单周期级别上的东西在物理上是无法测量的。如果你能消除测量中的所有干扰(在具有板载内存且没有操作系统的芯片上运行),那么你仍然需要担心计时器的粒度,但从理论上讲,如果你运行它足够长的时间,你可以看到一些东西。
68赞 Adrian Cornish 8/27/2012 #3

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

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

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

我的例子来自 Linux 上x86_64平台上的 GCC。if

编译器编写者是非常聪明的人,他们认为这些事情以及我们大多数人认为理所当然的许多其他事情。

我注意到,如果它不是常量,那么无论哪种情况都会生成相同的机器代码。

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

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

评论

10赞 Michael Petrotta 8/27/2012
请注意,这是特定于 x86 的。
11赞 Lipis 8/27/2012
我认为你应该用它来证明它生成了完全相同的asm:)if(a <=900)
2赞 Lipis 8/27/2012
@AdrianCornish对不起..我编辑了它..它或多或少是一样的..但是,如果将第二个 if 更改为 <=900,则 ASM 代码将完全相同:)现在差不多了..但你知道..对于强迫症:)
3赞 Qsario 8/27/2012
@Boann 这可能会减少到 if (true) 并完全消除。
5赞 Jonathon Reinhart 8/27/2012
没有人指出这种优化仅适用于常量比较。我可以保证不会像这样比较两个变量。
6赞 shinkou 8/27/2012 #4

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

评论

1赞 jcolebrand 8/27/2012
有什么不好的做法?递增或递减计数器?那么你如何存储索引符号呢?
6赞 JustinDanielson 8/28/2012
他的意思是,如果您正在比较 2 种变量类型。当然,如果你要为循环或其他东西设置值,这是微不足道的。但是,如果你有 x <= y,并且 y 是未知的,那么将其“优化”为 x < y + 1 会更慢
0赞 Jonathon Reinhart 8/28/2012
@JustinDanielson同意了。更不用说丑陋、混乱等了。
98赞 David Schwartz 8/27/2012 #5

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

如果某个平台比简单整数类型更快,编译器应始终转换为 for 常量。任何没有的编译器都只是一个糟糕的编译器(对于该平台)。<<=<=<

评论

8赞 autistic 6/10/2013
+1 我同意。在编译器决定它们将具有哪种速度之前,两者都没有速度。对于编译器来说,这是一个非常简单的优化,因为考虑到它们通常已经执行了死代码优化、尾部调用优化、循环提升(有时还有展开)、各种循环的自动并行化等......为什么要浪费时间思考过早的优化?运行原型,对其进行分析以确定最重要的优化所在,按重要性顺序执行这些优化,并在此过程中再次分析以衡量进度......<<=
0赞 BeeOnRope 6/16/2016
在一些边缘情况下,在 <= 下,具有一个常量值的比较可能会更慢,例如,当从 to 的转换(对于某些常数)导致在指令集中编码更加困难时。例如,在比较中,指令集可能能够以紧凑的形式表示从 -127 到 128 的有符号常量,但该范围之外的常量必须使用更长、更慢的编码或完全其他指令加载。因此,像这样的比较可能没有直接的转换。(a < C)(a <= C-1)CC(a < -127)
0赞 David Schwartz 6/16/2016
@BeeOnRope 问题不在于执行由于具有不同常量而产生的不同操作是否会影响性能,而在于使用不同的常量表示相同的操作是否会影响性能。所以我们不是在比较,因为你别无选择,你使用你需要的那个。我们比较的是 ,它不需要不同的编码或不同的指令,因为它们具有相同的真值表。一个编码的任何编码都同样是另一个编码。a > 127a > 128a > 127a >= 128
0赞 BeeOnRope 6/17/2016
我以一种笼统的方式回应了您的陈述,即“如果某个平台 [<= 较慢],编译器应始终转换为 for 常量”。据我所知,这种转换涉及改变常数。例如,被编译为因为更快。在某些边缘情况下,这种转换不会有成效,因为新常量可能需要更多或更慢的指令。当然,和是等价的,编译器应该以(相同)最快的方式对这两种形式进行编码,但这与我所说的并不矛盾。<=<a <= 42a < 43<a > 127a >= 128
15赞 Masoud 8/27/2012 #6

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

30赞 Eliot Ball 8/27/2012 #7

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

评论

0赞 Abhishek Singh 4/7/2015
为什么!(a>b) 是 <=b 的优化版本。不是!(a>b) 二合一操作?
6赞 Pavel Gatnar 4/15/2015
@AbhishekSingh只是由其他指令(与。NOTjejne)
0赞 Don Hatch 9/11/2020
在IEEE浮点数中,与 的含义不同。a<=b!(a>b)
34赞 glglgl 8/27/2012 #8

也许那本不知名的书的作者读过比它跑得更快,并认为这是普遍正确的。a > 0a >= 1

但这是因为涉及 a(因为根据体系结构的不同,可以替换为 ),而不是因为 .0CMPOR<

评论

1赞 BeeOnRope 6/16/2016
当然,在“调试”版本中,但是运行速度慢需要一个糟糕的编译器,因为优化器可以轻易地将前者转换为后者。(a >= 1)(a > 0)
2赞 glglgl 6/16/2016
@BeeOnRope 有时我会惊讶于优化器可以优化哪些复杂的事情,而它却无法做到哪些简单的事情。
1赞 BeeOnRope 6/17/2016
事实上,检查asm输出中极少数重要的函数总是值得的。也就是说,上述转换是非常基本的,即使在简单的编译器中也已经执行了几十年。
622赞 Lucas 8/28/2012 #9

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

评论

11赞 greyfade 8/28/2012
此外,像 x86 这样的体系结构实现了类似 的指令,这些指令测试零和符号/携带标志。jge
4赞 Jon Hanna 8/28/2012
即使对于给定的体系结构也是如此。没有一个编译器编写者注意到,并添加了优化以用更快的替换较慢的几率是多少?
9赞 8/28/2012
在 8080 上也是如此。它有跳到零和跳到负的指令,但没有一个可以同时测试两者。
5赞 Lucas 8/28/2012
6502 和 65816 处理器系列也是如此,摩托罗拉 68HC11/12 也适用于此。
38赞 Gunther Piez 8/29/2012
即使在 8080 上,也可以在一条指令中实现测试,交换操作数并测试(相当于)这是交换操作数所期望的:。这就是英特尔省略此测试的原因,他们认为这是多余的,您当时负担不起冗余指令:-)<=not <>=<=cmp B,A; bcs addr
54赞 ridiculous_fish 8/28/2012 #10

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

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

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

现在考虑这个函数:

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

这需要与上述相同的工作,但现在有两个兴趣点:“小于”和“等于”。这需要额外的指令(-条件寄存器按位OR)将这两个位合并为一个。所以需要五条指令,而需要四条指令。compare_strictcrorcompare_loosecompare_strict

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

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

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

评论

0赞 Jonathon Reinhart 8/28/2012
幸运的是,它在 x86 (x87) 上不能这样工作。 设置 ZF 和 CF。fucomip
5赞 Dietrich Epp 8/28/2012
@JonathonReinhart:我认为你误解了 PowerPC 在做什么——条件寄存器等同于 x86 上的标志。(尽管 CR 更灵活。发帖人谈论的是将结果移动到 GPR:它在 PowerPC 上需要两条指令,但 x86 有一个条件移动指令。crZFCF
0赞 Jonathon Reinhart 8/28/2012
@DietrichEpp 我想在我的陈述之后添加的是:然后你可以根据 EFLAGS 的值立即跳转。对不起,不清楚。
1赞 Dietrich Epp 8/28/2012
@JonathonReinhart:是的,你也可以根据CR的值立即跳转。答案不是在谈论跳跃,这是额外指令的来源。
4赞 Ecksters 8/29/2012 #11

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

评论

0赞 Tyler Crompton 9/5/2012
我有点不同意。在竞争性编程中,脚本语言通常为问题提供最快的解决方案,但必须应用正确的技术(阅读:优化)才能获得正确的解决方案。
18赞 Mark Booth 9/1/2012 #12

TL;DR答案

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

完整答案

其他答案都集中在 x86 架构上,我不知道 ARM 架构(您的示例汇编程序似乎是)足以专门评论生成的代码,但这是一个优化的例子,它非常特定于架构,并且很可能是反优化,因为它是优化。

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

反例

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

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

总结

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

5赞 Peter Cordes 1/20/2019 #13

当我写这个答案的第一个版本时,我只看关于 < vs. <= 的标题问题,而不是常数 vs. 的具体例子。许多编译器总是通过在 和 之间转换来缩小常量的大小,例如,因为 x86 直接操作数具有较短的 1 字节编码,用于 -128..127。a < 901a <= 900<<=

对于 ARM 来说,能够立即编码取决于能否将窄字段旋转到单词中的任何位置。所以是可编码的,而不是。因此,与编译时常量进行比较的“缩小”规则并不总是适用于 ARM。AArch64 要么是 shift-12,要么不是任意旋转,用于 和 等指令,这与 32 位 ARM 和 Thumb 模式不同。cmp r0, #0x00f000cmp r0, #0x00efffcmpcmn


< 与 <= 的一般情况,包括运行时变量条件

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

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

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

与有符号溢出 (UB) 不同,无符号溢出被明确定义为 base-2 环绕。有符号循环计数器通常是安全的,基于有符号溢出 UB 进行优化的编译器不会发生:最终总是会变成 false。(每个 C 程序员都应该知道的关于未定义行为的知识++i <= size)

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 始终为 true。因此,对于 size=0,这个循环是无限的,编译器必须尊重这一点,即使作为程序员的您可能从未打算传递 size=0。如果编译器可以将此函数内联到调用方中,在该调用方中可以证明 size=0 是不可能的,那么太好了,它可以像 .i < size

Asm like 是一种优化循环的正常有效方法,如果循环内部不需要 的实际值(为什么循环总是编译为“do...而“风格(尾巴跳跃)?if(!size) skip the loop;do{...}while(--size);for( i<size )i

但是 do{}while 不能是无限的:如果输入 ,我们会得到 2^n 次迭代。(遍历 for 循环 C 中的所有无符号整数可以表达对包括零在内的所有无符号整数的循环,但如果没有像 asm 中那样的进位标志,这并不容易。size==0

由于循环计数器的环绕是可能的,现代编译器通常只是“放弃”,并且不会进行几乎如此积极的优化。

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

使用 unsigned i <= 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 整数加法自动矢量化,在 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)。/ 而不是 /cmp/jcc 会更有效。1 UOP 而不是 2(在 Sub/JCC 或 CMP/JCC 宏观融合后)。两个循环之后的代码无条件地写入 EAX,因此它不使用循环计数器的最终值。sub eax,1jnzadd eax,1

评论

0赞 rustyx 1/20/2019
很好的人为例子。您关于使用EFLAGS对乱序执行的潜在影响的其他评论呢?是纯粹的理论,还是真的可以发生JB导致比JBE更好的流水线吗?
0赞 Peter Cordes 1/20/2019
@rustyx:我有没有在另一个答案下评论过?编译器不会发出导致部分标志停滞的代码,当然也不会针对 C 或 .但可以肯定的是,如果设置了 ZF (ecx==0),或者如果设置了 CF(EAX==1 的第 3 位),/ / 将跳跃,从而导致大多数 CPU 上的部分标志停滞,因为它读取的标志并不都来自写入任何标志的最后一条指令。在 Sandybridge 系列上,它实际上并没有停滞,只需要插入一个合并的 uop。/ 写入所有标志,但保留 ZF 不变。felixcloutier.com/x86/bt<<=test ecx,ecxbt eax, 3jbecmptestbt
0赞 Nate Eldredge 11/2/2020
据我了解,AArch64 上可用的即时式比您的答案听起来简单:它需要 12 位立即式,可以选择性地移动 12 位,因此您可以拥有 或 ,并且您还可以通过使用代替来有效地否定立即式。这仍然支持你的观点,因为是可编码的,但不是。但是“旋转到任何位置”的措辞听起来更像是对“位掩码”的描述,AFAIK 仅适用于按位逻辑指令:等。cmp0xYYY0xYYY000cmncmp w0, #0xf000cmp w0, #0xefffand, or, eor
0赞 Peter Cordes 11/2/2020
@NateEldredge:我认为我的描述非常适合 ARM 模式,在该模式下,它是一个 8 位字段,旋转了 2 的倍数。(所以是不可编码的,但可以编码。当我写这篇文章时,我还没有理解 AArch64 和 ARM Imstates 之间的区别,或者只有按位布尔值才能使用位范围/重复位模式编码。(和 ; 零注册是利用这些编码的一种方法。0x1fe0xff0movor
2赞 Puddle 7/9/2019 #14

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

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

每一次比较,都只是一个减法(差异),看看它是正数还是负数。
(如果设置了,则数字为负数)
msb

如何检查?子检查是否为阳性。
如何检查?子检查是否为阳性。
如何检查?子检查是否为阴性。
如何检查?子检查是否为阴性。
a >= ba-b >= 0a-ba <= b0 <= b-ab-aa < ba-b < 0a-ba > b0 > b-ab-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

当然,计算机实际上并不需要执行 OR 操作。
因为它可以只是从电路中反转。
==0==1==0msb

无论如何,他们肯定不会被计算成哈哈a >= ba>b || a==b

评论

0赞 Nate Eldredge 11/3/2020
然而,事情并没有那么简单。例如,如果在寄存器中并且是编译时常量,则 x86 可以在一条指令(或)中计算,但不能计算。有一个说明,但不是相反。许多其他机器也有类似的情况。aba-bsub rax, 12345cmpb-areg - imm
0赞 benrg 4/18/2022
这整个答案是错误的。例如,INT_MAX > INT_MIN,但 INT_MIN - INT_MAX 为 1(在机器代码级别,而不是在 C 中),其 msb 为 0。正确地进行这些比较比您想象的要难。
0赞 Puddle 4/20/2022
@benrg 显然,在代码中实现并不像访问进位/溢出的实际电路那样简单。这个答案是为了解释不同比较的逻辑。(这都是关于差异的。这显然会在 ALU 中处理。(也适用于不同的类型,如浮子)看这个。所以答案没有错。你提出的是整数的局限性。如果我们把INT_MIN放在一个长处,它会存储ffffffff80000000。做减法会得到ffffffff00000001。(否定)
1赞 gnasher729 9/2/2022 #15

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

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

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

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

评论

0赞 Peter Cordes 9/2/2022
通常,机器代码使用符号扩展的即时代码,因此 +128 与 +127 是 3 个字节的截止值,例如,在 x86 上为 6 个字节。这就是为什么 GCC 在编译比较时总是尝试减少常量的大小: 了解 if (a>=3) 的 gcc 输出(这在 ARM 上并不总是胜利,例如 可以立即旋转,而不能。哦,我看到我已经发布了关于这个问题的答案,指出了这些事情。cmp ecx, imm8cmp ecx, imm320x10000x0fff