C/C++ : 将比较结果用作 int 真的没有分支吗？

Question

我在很多 SO 答案中看到过这样的代码：

template <typename T> 
inline T imax (T a, T b)
{
    return (a > b) * a + (a <= b) * b;
}

作者说这个无分支。

但这在当前架构上真的是无分支的吗？ (x86, ARM...) 是否有真正的标准保证这是无分支的？

Answer 1

x86 具有 SETcc 系列指令，可根据标志的值将字节寄存器设置为 1 或 0。这通常被编译器用来实现这种没有分支的代码。

如果您使用“天真的”方法

int imax(int a, int b) {
    return a > b ? a : b;
}

编译器将使用 CMOVcc（条件移动）指令族生成更高效的无分支代码。

ARM 能够有条件地执行每条指令，从而使编译器能够有效地编译您的和原始实现，原始实现更快。

Answer 2

我偶然发现了这个 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 是不可预测的野兽。

C/C++ : 将比较结果用作 int 真的没有分支吗？

C/C++ : is using the result of comparison as int really branchless?

c++

comparison

branch-prediction

tl;博士