提问人:Vinícius 提问时间:8/27/2012 最后编辑:ivaigultVinícius 更新时间:9/2/2022 访问量:149335
< 比 <= 快吗?
Is < faster than <=?
问:
比 ?if (a < 901)
if (a <= 900)
与这个简单示例中不完全相同,但在循环复杂代码上存在轻微的性能变化。我想这必须与生成的机器代码有关,以防万一它是真的。
答:
不,它不会在大多数架构上更快。您没有指定,但在 x86 上,所有积分比较通常将在两个机器指令中实现:
- A 或指令,其中设置
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:
因此,两者之间的唯一区别是指令与指令。两者将花费相同的时间。jg
jge
我想解决一个评论,即没有任何迹象表明不同的跳转指令需要相同的时间。这个问题有点难以回答,但我可以给出以下结论:在《英特尔指令集参考》中,它们都按照一个通用指令组合在一起(如果满足条件,则跳转)。在《优化参考手册》的附录 C. 延迟和吞吐量中,进行了相同的分组。Jcc
延迟 — 所需的时钟周期数 执行核心,用于完成所有 μOPS 的执行 指令。
吞吐量 — 所需的时钟周期数 等待发出端口可以自由接受相同的指令 再。对于许多指令,指令的吞吐量可以是 明显小于其延迟
的值为:Jcc
Latency Throughput
Jcc N/A 0.5
脚注如下:Jcc
- 条件跳转指令的选择应基于第 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
评论
jg
jnle
7F
这将高度依赖于 C 编译到的底层架构。某些处理器和体系结构可能具有等于或小于和等于的显式指令,这些指令以不同的周期数执行。
不过,这将是非常不寻常的,因为编译器可以绕过它,使其无关紧要。
评论
我看到两者都不是更快的。编译器在每个条件中生成具有不同值的相同机器代码。
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
评论
if(a <=900)
即使有差异,您也不应该注意到差异。此外,在实践中,除非你要使用一些魔法常数,否则你必须做一个额外的操作或使条件成立,这无论如何都是一个非常糟糕的做法。a + 1
a - 1
评论
假设我们谈论的是内部整数类型,那么一个不可能比另一个更快。它们在语义上显然是相同的。它们都要求编译器做完全相同的事情。只有严重损坏的编译器才会为其中之一生成劣质代码。
如果某个平台比简单整数类型更快,编译器应始终转换为 for 常量。任何没有的编译器都只是一个糟糕的编译器(对于该平台)。<
<=
<=
<
评论
<
<=
(a < C)
(a <= C-1)
C
C
(a < -127)
a > 127
a > 128
a > 127
a >= 128
<=
<
a <= 42
a < 43
<
a > 127
a >= 128
它们具有相同的速度。也许在某些特殊的架构中,他/她说的是对的,但在 x86 系列中,至少我知道它们是相同的。因为为此,CPU 将进行减法 (a - b),然后检查标志寄存器的标志。该寄存器的两个位称为 ZF(零标志)和 SF(符号标志),它是在一个周期内完成的,因为它将通过一个掩码操作来完成。
至少,如果这是真的,编译器可以简单地将 <= b 优化为 !(a > b),因此,即使比较本身实际上较慢,除了最幼稚的编译器之外,您也不会注意到差异。
评论
NOT
je
jne
)
a<=b
!(a>b)
也许那本不知名的书的作者读过比它跑得更快,并认为这是普遍正确的。a > 0
a >= 1
但这是因为涉及 a(因为根据体系结构的不同,可以替换为 ),而不是因为 .0
CMP
OR
<
评论
(a >= 1)
(a > 0)
从历史上看(我们说的是 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 与内存速度比的时代是相关的,但在今天几乎完全无关紧要。
评论
jge
<=
not <
>=
<=
cmp B,A; bcs addr
对于浮点代码,即使在现代架构上,<= 比较也可能确实更慢(一条指令)。这是第一个函数:
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_strict
cror
compare_loose
compare_strict
你可能会认为编译器可以像这样优化第二个函数:
int compare_loose(double a, double b) { return ! (a > b); }
但是,这将错误地处理 NaN。 并且需要两者都评估为 false。NaN1 <= NaN2
NaN1 > NaN2
评论
fucomip
cr
ZF
CF
可以说,在大多数脚本语言中,该行是正确的,因为额外的字符会导致代码处理速度稍慢。 然而,正如最上面的答案所指出的,它在 C++ 中应该没有效果,并且使用脚本语言所做的任何事情都可能不那么关心优化。
评论
TL;DR答案
对于大多数架构、编译器和语言的组合,不会比 .<
<=
完整答案
其他答案都集中在 x86 架构上,我不知道 ARM 架构(您的示例汇编程序似乎是)足以专门评论生成的代码,但这是一个微优化的例子,它非常特定于架构,并且很可能是反优化,因为它是优化。
因此,我认为这种微观优化是货物崇拜编程的一个例子,而不是最佳软件工程实践。
反例
可能有一些架构是一种优化,但我知道至少有一个架构可能恰恰相反。古老的 Transputer 架构只有等于和大于或等于的机器代码指令,因此所有比较都必须从这些原语构建。
即便如此,在几乎所有情况下,编译器都可以以这样一种方式对评估指令进行排序,即在实践中,任何比较都比任何其他比较都没有任何优势。但最坏的情况是,它可能需要添加反向指令 (REV) 来交换操作数堆栈上的前两个项目。这是一个单字节指令,需要一个周期才能运行,因此具有尽可能小的开销。
总结
像这样的微优化是优化还是反优化取决于你使用的特定架构,所以养成使用特定于架构的微优化的习惯通常是一个坏主意,否则你可能会本能地在不合适的时候使用微优化,看起来这正是你正在阅读的书所倡导的。
当我写这个答案的第一个版本时,我只看关于 < vs. <= 的标题问题,而不是常数 vs. 的具体例子。许多编译器总是通过在 和 之间转换来缩小常量的大小,例如,因为 x86 直接操作数具有较短的 1 字节编码,用于 -128..127。a < 901
a <= 900
<
<=
对于 ARM 来说,能够立即编码取决于能否将窄字段旋转到单词中的任何位置。所以是可编码的,而不是。因此,与编译时常量进行比较的“缩小”规则并不总是适用于 ARM。AArch64 要么是 shift-12,要么不是任意旋转,用于 和 等指令,这与 32 位 ARM 和 Thumb 模式不同。cmp r0, #0x00f000
cmp r0, #0x00efff
cmp
cmn
< 与 <= 的一般情况,包括运行时变量条件
在大多数机器上的汇编语言中,比较 的开销与比较的开销相同。无论您是对它进行分支、对其进行布尔化以创建 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,1
jnz
add eax,1
评论
<
<=
test ecx,ecx
bt eax, 3
jbe
cmp
test
bt
cmp
0xYYY
0xYYY000
cmn
cmp w0, #0xf000
cmp w0, #0xefff
and, or, eor
0x1fe
0xff0
mov
or
只有当创建计算机的人不擅长布尔逻辑时。他们不应该这样做。
每个比较 ( ) 都可以以相同的速度完成。>=
<=
>
<
每一次比较,都只是一个减法(差异),看看它是正数还是负数。
(如果设置了,则数字为负数)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
当然,计算机实际上并不需要执行 OR 操作。
因为它可以只是从电路中反转。==0
==1
==0
msb
无论如何,他们肯定不会被计算成哈哈a >= b
a>b || a==b
评论
a
b
a-b
sub rax, 12345
cmp
b-a
reg - imm
在 C 和 C++ 中,编译器的一个重要规则是“假设”规则:如果执行 X 的行为与执行 Y 的行为完全相同,那么编译器可以自由选择它使用哪一个。
在您的例子中,“a < 901”和“a <= 900”总是具有相同的结果,因此编译器可以自由地编译任一版本。如果一个版本更快,无论出于何种原因,那么任何高质量的编译器都会为更快的版本生成代码。因此,除非你的编译器生成了非常糟糕的代码,否则两个版本将以相同的速度运行。
现在,如果你遇到这样一种情况,即两位代码总是会产生相同的结果,但编译器很难证明,和/或编译器很难证明哪个版本更快,那么你可能会得到不同的代码以不同的速度运行。
PS 如果处理器支持单字节常量(更快)和多字节常量(更慢),则原始示例可能会以不同的速度运行,因此与 255(1 字节)进行比较可能比与 256(2 字节)进行比较更快。我希望编译器能做任何更快的事情。
评论
cmp ecx, imm8
cmp ecx, imm32
0x1000
0x0fff
评论
<
<=
a
jg
jge
<
jl +2 jmp ...
jge
jg ...