我正在读一本书,作者说if( a < 901 )
比if( a <= 900 )
更快。
与此简单示例不完全相同,但循环复杂代码略有性能变化。我想这必须对生成的机器代码做一些事情,以防它甚至是真的。
不,它在大多数架构上都不会更快。您没有指定,但在x86上,所有的整数比较通常都会在两个机器指令中实现:
test
或cmp
指令,设置EFLAGS
Jcc
(jump) instruction,取决于比较类型(和代码布局):
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:
因此,两者之间的唯一区别是jg
与jge
指令。这两个人将花费相同的时间。
我想解决的问题是,没有任何迹象表明不同的跳转指令需要相同的时间。回答这个问题有点棘手,但这就是我能给出的:在Intel Instruction Set Reference中,它们都在一个共同的指令下组合在一起,Jcc
(如果符合条件则跳转)。在Optimization Reference Manual下,在附录C中,相同的分组一起进行。延迟和吞吐量。
延迟 - 执行内核完成执行构成指令的所有μop所需的时钟周期数。
吞吐量 - 在发出端口可以再次接受相同指令之前等待所需的时钟周期数。对于许多指令,指令的吞吐量可能远远小于其延迟
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
对于大多数架构,编译器和语言的组合,它不会更快。
其他答案集中在x86体系结构,我不知道ARM体系结构(你的示例汇编程序似乎是)足以对生成的代码做出具体评论,但这是一个非常特定于体系结构的micro-optimisation的例子,并且很可能是一种反优化,因为它是一种优化。
因此,我建议这种micro-optimisation是cargo cult编程的一个例子,而不是最好的软件工程实践。
可能有一些架构,这是一个优化,但我知道至少有一个架构,相反可能是真的。古老的Transputer架构只有等于或大于或等于的机器代码指令,因此所有比较都必须从这些原语构建。
即便如此,在几乎所有情况下,编译器都可以按照这样的方式对评估指令进行排序:在实践中,没有任何比较比任何其他比较都有任何优势。最糟糕的情况是,它可能需要添加一个反向指令(REV)来交换operand stack上的前两项。这是一个单字节指令,需要一个周期才能运行,所以可能的开销最小。
这样的微优化是优化还是反优化取决于您使用的特定体系结构,因此养成使用体系结构特定微优化的习惯通常是个坏主意,否则您可能会本能地当它不合适时使用一个,看起来这正是你正在阅读的书所倡导的。
即使有任何差异,您也不应该注意到差异。此外,在实践中,你将不得不做一个额外的a + 1
或a - 1
,以使条件成立,除非你将使用一些魔术常数,这是一个非常糟糕的做法。
您可以说在大多数脚本语言中该行是正确的,因为额外的字符会导致代码处理稍慢。但是,正如最顶层的回答所指出的那样,它在C ++中应该没有任何效果,而使用脚本语言完成的任何事情都可能并不关心优化。
当我写这个答案的时候,我只是在看一般关于<vs. <=的标题问题,而不是a < 901
与a <= 900
的常数的具体例子。许多编译器总是通过在<
和<=
之间进行转换来缩小常数的大小,例如:因为x86立即操作数对-128..127具有较短的1字节编码。
对于ARM,尤其是AArch64,能够立即编码取决于能够将窄字段旋转到字中的任何位置。所以cmp w0, #0x00f000
可以编码,而cmp w0, #0x00effff
可能不是。因此,用于比较的make-it-less规则与编译时常量并不总是适用于AArch64。
在大多数机器上使用汇编语言,<=
的比较与<
的比较成本相同。这适用于您是否对其进行分支,将其布尔化为创建0/1整数,或将其用作无分支选择操作的谓词(如x86 CMOV)。其他答案只解决了这部分问题。
但是这个问题是关于C ++运算符,优化器的输入。通常他们都同样有效率;这本书的建议听起来完全是假的,因为编译器总是可以改变他们在asm中实现的比较。但至少有一个例外,即使用<=
可能会意外地创建编译器无法优化的内容。
作为循环条件,有些情况下<=
与<
在质量上有所不同,当它阻止编译器证明循环不是无限时。这可以产生很大的不同,禁用自动矢量化。
与带符号溢出(UB)不同,无符号溢出被明确定义为base-2环绕。有条件的循环计数器通常是安全的,基于签名溢出UB优化的编译器不会发生:++i <= size
总是最终变为false。 (What Every C Programmer Should Know About Undefined Behavior)
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
总是如此。所以这个循环对于size=0
是无限的,并且编译器必须尊重它,即使你作为程序员可能永远不打算传递size = 0。如果编译器可以将此函数内联到调用者中,它可以证明size = 0是不可能的,那么很好,它可以像i < size
一样进行优化。
像if(!size) skip the loop;
do{...}while(--size);
这样的asm是一种优化for( i<size )
循环的常用方法,如果在循环内部不需要i
的实际值(Why are loops always compiled into "do...while" style (tail jump)?)。
但那不可能是无限的:如果用size==0
输入,我们得到2 ^ n次迭代。 (Iterating over all unsigned integers in a for loop C使得有可能在所有无符号整数上表示一个循环,包括零,但如果没有进位标志就像在asm中一样,这并不容易。)
由于循环计数器的可能性,现代编译器通常只是“放弃”,并且几乎没有积极地进行优化。
使用无符号的i <= n
击败了clang的成语识别,它使用基于Gauss的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;
}
x86-64 asm from clang7.0 and gcc8.2 on the Godbolt compiler explorer
# 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)。 sub eax,1
/ jnz
而不是add eax,1
/ cmp / jcc会更有效率。 1 uop而不是2(在sub / jcc或cmp / jcc的宏融合之后)。两个循环之后的代码无条件地写入EAX,因此它不使用循环计数器的最终值。
从历史上看(我们说的是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到内存速度比的时代相关,但它现在几乎完全无关紧要。
假设我们正在讨论内部整数类型,那么没有可能比另一种更快。它们在语义上显然是相同的。他们都要求编译器做同样的事情。只有可怕的破坏编译器会为其中一个生成劣质代码。
如果有一些平台,其中<
比<=
快于简单整数类型,编译器应始终将<=
转换为<
以获取常量。任何编译器都不会只是一个糟糕的编译器(对于该平台)。
我发现两者都不快。编译器在每个条件中使用不同的值生成相同的机器代码。
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
- 条件寄存器按位OR)将这两个位组合成一个。所以compare_loose
需要五个指令,而compare_strict
需要四个指令。
您可能认为编译器可以像这样优化第二个函数:
int compare_loose(double a, double b) { return ! (a > b); }
但是这会错误地处理NaN。 NaN1 <= NaN2
和NaN1 > NaN2
都需要评估为假。
也许这本未命名的书的作者已经读过a > 0
跑得比a >= 1
快,并认为这是普遍的。
但这是因为涉及0
(因为CMP
可以,取决于架构,例如用OR
取代)而不是因为<
。
至少,如果这是真的,编译器可以轻而易举地优化<= b到!(a> b),所以即使比较本身实际上更慢,除了最天真的编译器之外,你不会注意到差别。
它们具有相同的速度。也许在一些特殊的架构中他/她说的是对的,但至少在x86家族中我知道它们是相同的。因为为此,CPU将进行减法(a-b),然后检查标志寄存器的标志。该寄存器的两位称为ZF(零标志)和SF(符号标志),它在一个周期内完成,因为它将通过一个屏蔽操作完成。
这将高度依赖于编译C的底层架构。某些处理器和体系结构可能具有等于或小于等于在不同循环数中执行的明确指令。
这可能是非常不寻常的,因为编译器可以解决它,使其无关紧要。