Vin*_*rta 1508 c++ performance assembly relational-operators
我正在读一本书,作者说这if( a < 901 )比书更快if( a <= 900 ).
与此简单示例不完全相同,但循环复杂代码略有性能变化.我想这必须对生成的机器代码做一些事情,以防它甚至是真的.
Jon*_*art 1658
不,它在大多数架构上都不会更快.您没有指定,但在x86上,所有的整数比较通常都会在两个机器指令中实现:
test或cmp指令EFLAGSJcc(跳转)指令,取决于比较类型(和代码布局):
jne - 如果不相等则跳转 - > ZF = 0jz - 如果为零(等于)则跳转 - > ZF = 1jg - 如果更大则跳跃 - > 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指令.这两个人将花费相同的时间.
我想解决的问题是,没有任何迹象表明不同的跳转指令需要相同的时间.这个问题有点难以回答,但这是我能给出的:在英特尔指令集参考中,它们都在一条通用指令下组合在一起Jcc(如果满足条件则跳转).在优化参考手册的附录C中,相同的分组一起进行.延迟和吞吐量.
延迟 - 执行内核完成执行构成指令的所有μop所需的时钟周期数.
吞吐量 - 在发出端口可以再次接受相同指令之前等待所需的时钟周期数.对于许多指令,指令的吞吐量可能远远小于其延迟
值为Jcc:
Latency Throughput
Jcc N/A 0.5
以下脚注Jcc:
7)条件跳转指令的选择应基于第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
Luc*_*cas 585
从历史上看(我们说的是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到内存速度比的时代相关,但它现在几乎完全无关紧要.
Dav*_*rtz 89
假设我们正在讨论内部整数类型,那么没有可能比另一种更快.它们在语义上显然是相同的.他们都要求编译器做同样的事情.只有可怕的破坏编译器会为其中一个生成劣质代码.
如果有一些平台,<是速度比<=为简单的整数类型,编译器应该总是转换<=到<为常数.任何编译器都不会只是一个糟糕的编译器(对于该平台).
Adr*_*ish 67
我发现两者都不快.编译器在每个条件中使用不同的值生成相同的机器代码.
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
rid*_*ish 50
对于浮点代码,即使在现代架构上,<=比较确实可能更慢(通过一条指令).这是第一个功能:
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需要评估为假.
glg*_*lgl 34
也许这本未命名的书的作者阅读的a > 0速度要快于a >= 1并认为这是普遍存在的.
但这是因为a 0涉及(因为CMP可以,取决于架构,例如替换OR)而不是因为<.
Eli*_*all 32
至少,如果这是真的,编译器可以轻而易举地优化<= b到!(a> b),所以即使比较本身实际上更慢,除了最天真的编译器之外,你不会注意到差别.
Mas*_*oud 15
它们具有相同的速度.也许在一些特殊的架构中他/她说的是对的,但至少在x86家族中我知道它们是相同的.因为为此,CPU将进行减法(a-b),然后检查标志寄存器的标志.该寄存器的两位称为ZF(零标志)和SF(符号标志),它在一个周期内完成,因为它将通过一个屏蔽操作完成.
小智 14
这将高度依赖于编译C的底层架构.某些处理器和体系结构可能具有等于或小于等于在不同循环数中执行的明确指令.
这可能是非常不寻常的,因为编译器可以解决它,使它无关紧要.
Mar*_*oth 11
对于大多数架构,编译器和语言的组合,它不会更快.
其他的答案都集中在x86的架构,我不知道ARM架构(其中的例子汇编好像是)不够好,特别是对生成的代码进行评论,但是这是一个示例微优化这是非常架构特定的,并且可能是一种反优化,因为它是一种优化.
因此,我建议这种微优化是货物崇拜编程的一个例子,而不是最好的软件工程实践.
可能有一些架构,这是一个优化,但我知道至少有一个架构,反之亦然.令人尊敬的Transputer架构只有等于或大于或等于的机器代码指令,因此必须从这些原语构建所有比较.
即便如此,在几乎所有情况下,编译器都可以按照这样的方式对评估指令进行排序:在实践中,没有任何比较比任何其他比较都有任何优势.但最糟糕的情况是,可能需要添加反向指令(REV)来交换操作数堆栈中的前两项.这是一个单字节指令,需要一个周期才能运行,所以可能的开销最小.
这样的微优化是优化还是反优化取决于您使用的特定体系结构,因此养成使用体系结构特定微优化的习惯通常是个坏主意,否则您可能会本能地当它不合适时使用一个,看起来这正是你正在阅读的书所倡导的.
即使有任何差异,您也不应该注意到差异.此外,在实践中,除非你要使用一些魔法常数,否则你将不得不做一个额外的a + 1或者a - 1使条件成立,这是一种非常糟糕的做法.
当我写这个答案的第一个版本时，我只是在看关于<与<=的标题问题，而不是常数a < 901与.的具体示例a <= 900。<许多编译器总是通过在和 之间进行转换来缩小常量的大小<=，例如，因为 x86 立即数操作数的 1 字节编码较短，为 -128..127。
对于 ARM 来说，能够编码为立即数取决于能够将狭窄字段旋转到字中的任何位置。所以cmp r0, #0x00f000可以编码，而cmp r0, #0x00efff不能编码。因此，与编译时常量进行比较的“缩小规则”并不总是适用于 ARM。cmp对于和之类的指令，AArch64 要么移位 12，要么不移位，而不是任意旋转cmn，这与 32 位 ARM 和 Thumb 模式不同。
在大多数机器上的汇编语言中， 的比较<=与 的比较具有相同的成本<。无论您是在其上进行分支、对其进行布尔化以创建 0/1 整数，还是将其用作无分支选择操作（如 x86 CMOV）的谓词，这都适用。其他答案只解决了这部分问题。
但这个问题是关于 C++ 运算符，即优化器的输入。 通常情况下，它们的效率是相同的。书中的建议听起来完全是假的，因为编译器总是可以转换他们在 asm 中实现的比较。但至少有一个例外，使用<=可能会意外地创建编译器无法优化的东西。
作为循环条件，在某些情况下 与<=有本质上的不同<，当它阻止编译器证明循环不是无限时。 这会产生很大的影响，禁用自动矢量化。
与有符号溢出 (UB) 不同，无符号溢出被明确定义为以 2 为基数环绕。带符号循环计数器通常不会受到这种情况的影响，因为编译器基于带符号溢出 UB 进行优化，不会发生：++i <= size最终总是会变为 false。（每个 C 程序员都应该了解未定义行为）
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.
如果循环内不需要 的实际值，则 Asmif(!size) skip the loop; do{...}while(--size);是一种通常有效的优化循环的方法（为什么循环总是编译成“do...while”样式（尾部跳转）？）。for( i<size )i
但 do{}while 不能是无限的：如果输入size==0，我们会得到 2^n 次迭代。（在 for 循环 C 中迭代所有无符号整数 使得可以表达对包括零在内的所有无符号整数的循环，但是如果没有进位标志，就像在 asm 中那样，这并不容易。）
由于循环计数器的环绕是可能的，现代编译器通常只是“放弃”，并且不那么积极地优化。
使用 unsignedi <= 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 整数加法自动矢量化，i在 XMM 寄存器的元素中并行运行 4 个值。
# "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 上的微指令）。 sub eax,1/jnz代替add eax,1/cmp/jcc 会更有效。1 uop 而不是 2 （在 sub/jcc 或 cmp/jcc 宏融合之后）。两个循环之后的代码无条件写入 EAX，因此它不使用循环计数器的最终值。
| 归档时间： |
|
| 查看次数： |
116171 次 |
| 最近记录： |