C/C++ : 将比较结果用作 int 真的没有分支吗?
C/C++ : is using the result of comparison as int really branchless?
我在很多 SO 答案中看到过这样的代码:
template <typename T>
inline T imax (T a, T b)
{
return (a > b) * a + (a <= b) * b;
}
作者说这个无分支。
但这在当前架构上真的是无分支的吗? (x86, ARM...)
是否有真正的标准保证这是无分支的?
x86 具有 SETcc
系列指令,可根据标志的值将字节寄存器设置为 1 或 0。这通常被编译器用来实现这种没有分支的代码。
如果您使用“天真的”方法
int imax(int a, int b) {
return a > b ? a : b;
}
编译器将使用 CMOVcc
(条件移动)指令族生成更高效的无分支代码。
ARM 能够有条件地执行每条指令,从而使编译器能够有效地编译您的和原始实现,原始实现更快。
我偶然发现了这个 SO 问题,因为我也在问我同样的问题……事实证明并非总是如此。比如下面的代码……
const struct op {
const char *foo;
int bar;
int flags;
} ops[] = {
{ "foo", 5, 16 },
{ "bar", 9, 16 },
{ "baz", 13, 0 },
{ 0, 0, 0 }
};
extern int foo(const struct op *, int);
int
bar(void *a, void *b, int c, const struct op *d)
{
c |= (a == b) && (d->flags & 16);
return foo(d, c) + 1;
}
… 在所有优化级别使用 gcc 3.4.6 (i386) 和 8.3.0 (amd64, i386) 编译为分支代码。 3.4.6 中的那个更手动 legibe,我将用 gcc -O2 -S -masm=intel x.c; less x.s
:
来演示
[…]
.text
.p2align 2,,3
.globl bar
.type bar , @function
bar:
push %ebp
mov %ebp, %esp
push %ebx
push %eax
mov %eax, DWORD PTR [%ebp+12]
xor %ecx, %ecx
cmp DWORD PTR [%ebp+8], %eax
mov %edx, DWORD PTR [%ebp+16]
mov %ebx, DWORD PTR [%ebp+20]
je .L4
.L2:
sub %esp, 8
or %edx, %ecx
push %edx
push %ebx
call foo
inc %eax
mov %ebx, DWORD PTR [%ebp-4]
leave
ret
.p2align 2,,3
.L4:
test BYTE PTR [%ebx+8], 16
je .L2
mov %cl, 1
jmp .L2
.size bar , . - bar
原来指针比较操作调用了一个比较,甚至调用了一个插入1的子程序。
即使使用 !!(a == b)
也不会有什么不同。
tl;博士
检查实际的编译器输出(使用 -S
汇编或使用 objdump -d -Mintel x.o
反汇编;如果不是在 x86 上,则删除 -Mintel
,这只会使汇编更清晰)汇编; compilers 是不可预测的野兽。
我在很多 SO 答案中看到过这样的代码:
template <typename T>
inline T imax (T a, T b)
{
return (a > b) * a + (a <= b) * b;
}
作者说这个无分支。
但这在当前架构上真的是无分支的吗? (x86, ARM...) 是否有真正的标准保证这是无分支的?
x86 具有 SETcc
系列指令,可根据标志的值将字节寄存器设置为 1 或 0。这通常被编译器用来实现这种没有分支的代码。
如果您使用“天真的”方法
int imax(int a, int b) {
return a > b ? a : b;
}
编译器将使用 CMOVcc
(条件移动)指令族生成更高效的无分支代码。
ARM 能够有条件地执行每条指令,从而使编译器能够有效地编译您的和原始实现,原始实现更快。
我偶然发现了这个 SO 问题,因为我也在问我同样的问题……事实证明并非总是如此。比如下面的代码……
const struct op {
const char *foo;
int bar;
int flags;
} ops[] = {
{ "foo", 5, 16 },
{ "bar", 9, 16 },
{ "baz", 13, 0 },
{ 0, 0, 0 }
};
extern int foo(const struct op *, int);
int
bar(void *a, void *b, int c, const struct op *d)
{
c |= (a == b) && (d->flags & 16);
return foo(d, c) + 1;
}
… 在所有优化级别使用 gcc 3.4.6 (i386) 和 8.3.0 (amd64, i386) 编译为分支代码。 3.4.6 中的那个更手动 legibe,我将用 gcc -O2 -S -masm=intel x.c; less x.s
:
[…]
.text
.p2align 2,,3
.globl bar
.type bar , @function
bar:
push %ebp
mov %ebp, %esp
push %ebx
push %eax
mov %eax, DWORD PTR [%ebp+12]
xor %ecx, %ecx
cmp DWORD PTR [%ebp+8], %eax
mov %edx, DWORD PTR [%ebp+16]
mov %ebx, DWORD PTR [%ebp+20]
je .L4
.L2:
sub %esp, 8
or %edx, %ecx
push %edx
push %ebx
call foo
inc %eax
mov %ebx, DWORD PTR [%ebp-4]
leave
ret
.p2align 2,,3
.L4:
test BYTE PTR [%ebx+8], 16
je .L2
mov %cl, 1
jmp .L2
.size bar , . - bar
原来指针比较操作调用了一个比较,甚至调用了一个插入1的子程序。
即使使用 !!(a == b)
也不会有什么不同。
tl;博士
检查实际的编译器输出(使用 -S
汇编或使用 objdump -d -Mintel x.o
反汇编;如果不是在 x86 上,则删除 -Mintel
,这只会使汇编更清晰)汇编; compilers 是不可预测的野兽。