<比<=快吗?

if (a < 901)if (a <= 900)快吗?

与这个简单的例子不完全一样,但是循环复杂代码的性能有轻微的变化。我想这必须与生成的机器代码有关,以防它甚至是真的。

144211 次浏览

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

  • testcmp指令,设置EFLAGS
  • #0(跳转)指令,具体取决于比较类型(和代码布局):
  • 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]      ; acmp     eax, DWORD PTR [esp+28]      ; bjge     .L2                          ; jump if a is >= b; Do something 1.L2:

    if (a <= b) {// Do something 2}

编译为:

    mov     eax, DWORD PTR [esp+24]      ; acmp     eax, DWORD PTR [esp+28]      ; bjg      .L5                          ; jump if a is > b; Do something 2.L5:

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


我想解决那个评论,即没有任何东西表明不同的跳转指令需要相同的时间。这个回答有点棘手,但我可以给出的是:在英特尔指令集参考中,它们都分组在一个共同的指令Jcc(如果满足条件则跳转)下。在附录C中,优化参考手册下进行了相同的分组。

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

吞吐量-所需的时钟周期数等待问题端口可以自由接受相同的指令对于许多指令,一条指令的吞吐量可以是远远小于它的延迟

Jcc的值是:

      Latency   ThroughputJcc     N/A        0.5

下面的脚注Jcc

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

因此,Intel文档中的任何内容都不会将一条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 EFLAGSfstp    st(0)seta    al                     ; Set al if above (CF=0 and ZF=0).test    al, alje      .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, alje      .L5; Do something 2.L5:leaveret

这将高度依赖于C被编译到的底层架构。一些处理器和架构可能有等于或小于等于的显式指令,它们在不同数量的周期中执行。

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

我发现两者都不快。编译器在每种情况下生成具有不同值的相同机器代码。

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

我的示例if来自Linuxx86_64平台上的GCC。

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

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

int b;if(a < b)cmpl  -4(%rbp), %eaxjge   .L2
if(a <=b)cmpl  -4(%rbp), %eaxjg .L3

此外,在实践中,你必须做一个额外的a + 1a - 1来使条件成立,除非你要使用一些神奇的常量,这是一个非常糟糕的做法。

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

如果有一些平台,对于简单的整数类型,<<=快,编译器应该总是将常量的<=转换为<。任何不这样做的编译器都只是一个糟糕的编译器(对于该平台)。

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

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

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

但这是因为涉及到0(因为CMP可以根据架构替换为OR),而不是因为<

从历史上看(我们说的是20世纪80年代和90年代初),有一些架构是这样的。根本问题是整数比较本质上是通过整数减法实现的。这导致了以下情况。

Comparison     Subtraction----------     -----------A < B      --> A - B < 0A = B      --> A - B = 0A > B      --> A - B > 0

现在,当A < B时,减法必须借用一个高比特才能使减法正确,就像您在手动加减时进行携带和借用一样。这个“借用”位通常被称为进位,可以通过分支指令进行测试。如果减法相同为零,则会设置第二位,称为零位,这意味着相等。

通常至少有两条条件分支指令,一条在进位分支,一条在零位分支。

现在,为了了解问题的核心,让我们扩展上一个表以包含进位和零位结果。

Comparison     Subtraction  Carry Bit  Zero Bit----------     -----------  ---------  --------A < B      --> A - B < 0    0          0A = B      --> A - B = 0    1          1A > B      --> A - B > 0    1          0

因此,实现A < B的分支可以在一条指令中完成,因为在这种情况下进位位是明确的只有,,即,

;; Implementation of "if (A < B) goto address;"cmp  A, B          ;; compare A to Bbcz  address       ;; Branch if Carry is Zero to the new address

但是,如果我们想要进行小于或等于的比较,我们需要对零标志进行额外的检查以捕获相等的情况。

;; Implementation of "if (A <= B) goto address;"cmp A, B           ;; compare A to Bbcz address        ;; branch if A < Bbzs address        ;; also, Branch if the Zero bit is Set

因此,在某些机器上,使用“小于”比较可能保存一条机器指令。这在亚兆赫兹处理器速度和1:1 CPU与内存速度比的时代是相关的,但今天几乎完全不相关。

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

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

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

太长别读答案

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

完整答案

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

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

反例

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

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

总结

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

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

对于ARM来说,能够编码为即时值取决于能够将窄字段旋转到单词中的任何位置。因此cmp r0, #0x00f000是可编码的,而cmp r0, #0x00efff是不可编码的。因此,与编译时常量相比,使其更小的规则并不总是适用于ARM。与32位ARM和Thumb模式不同,对于cmpcmn等指令,AArch64要么按12移位,要么不按12移位,而不是任意旋转。


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

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

作为一个循环条件,在某些情况下,当它阻止编译器证明循环不是无限的时,#0在质量上与#1不同。这会有很大的不同,禁用自动矢量化。

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

void foo(unsigned size) {unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAXfor(unsigned i=0 ; i <= upper_bound ; i++)...

编译器只能以保留所有可能输入值的C++源的(定义的和合法可观察的)行为的方式进行优化,除了那些导致未定义行为的。

(一个简单的i <= size也会产生问题,但我认为计算上限是一个更现实的例子,意外地为一个你不关心但编译器必须考虑的输入引入无限循环的可能性。

在这种情况下,#0导致#1,#2始终为真。所以这个循环对#0来说是无限的,编译器必须尊重这一点即使你作为程序员可能从未打算传递size=0。如果编译器可以将此函数内联到调用者中,证明size=0是不可能的,那么太好了,它可以像i < size一样优化。

if(!size) skip the loop;do{...}while(--size);这样的Asm是优化for( i<size )循环的一种通常有效的方法,如果循环内部不需要i的实际值(为什么循环总是编译成“do…这时候”风格(尾跳)?)。

但是do{}这时候不能是无限的:如果用size==0输入,我们得到2^n次迭代。(遍历for循环中的所有无符号整数 C使得在包括零在内的所有无符号整数上表达循环成为可能,但如果没有进位标志,就不容易了。)

由于循环计数器的环绕是一种可能性,现代编译器通常只是“放弃”,并且不会那么积极地优化。

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

使用无符号#0可以击败clang的习语识别,该习语识别使用封闭形式优化#1循环基于高斯的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;}

x86-64 asm

 # clang7.0 -O3 closed-formcmp     edi, -1       # n passed in EDI: x86-64 System V calling conventionje      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times# else fall through into the closed-form calcmov     ecx, edi         # zero-extend n into RCXlea     eax, [rdi - 1]   # n-1imul    rax, rcx         # n * (n-1)             # 64-bitshr     rax              # n * (n-1) / 2add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bitret          # computed without possible overflow of the product before right shifting.LBB1_1:xor     eax, eaxret

但是对于幼稚的版本,我们只是从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 -O3sum_1_to_n(unsigned int):xor     ecx, ecx           # i = 0xor     eax, eax           # retval = 0.LBB0_1:                       # do {add     eax, ecx             # retval += iadd     ecx, 1               # ++1cmp     ecx, edijbe     .LBB0_1            # } while( i<n );ret

无论哪种方式,GCC都不使用闭式形式,因此循环条件的选择不会真正伤害它;它通过SIMD整数加法自动向量化,在XMM寄存器的元素中并行运行4i值。

# "naive" inner loop.L3:add     eax, 1       # do {paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114cmp     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] += 4cmp     eax, edxjne     .L13      # }while( i != upper_limit );
then horizontal sum xmm0and peeled cleanup for the last n%3 iterations, or something.     

它还有一个纯标量循环,我认为它用于非常小的n,和/或无限循环情况。

顺便说一句,这两个循环都在循环开销上浪费了一条指令(以及Sandybridge系列CPU上的uop)。sub eax,1/jnz而不是add eax,1/cmp/jcc会更有效率。1 uop而不是2(在sub/jcc或cmp/jcc的宏融合之后)。两个循环之后的代码无条件地写入EAX,所以它没有使用循环计数器的最终值。

只有在创造计算机的人不擅长布尔逻辑的情况下。他们不应该这样。

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

每一个比较是什么,只是一个减法(差异),看看它是积极的/消极的。
(如果设置了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 lol

仅当计算路径依赖于数据时:

a={1,1,1,1,1000,1,1,1,1}while (i<=4){for(j from 0 to a[i]){ do_work(); }i++;}

将计算比while(i<4)多250倍

实际样本将是计算mandelbrot-set。如果包含一个迭代1000000次的像素,它会导致滞后,但与<=使用概率的重合太低。

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

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

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

PS如果处理器支持单字节常量(更快)和多字节常量(更慢),原始示例可能以不同的速度运行,因此与255(1字节)进行比较可能比与256(2字节)进行比较更快。