9

在阅读了有关此问题的许多评论后，有几个人（此处和此处）建议此代码：

int val = 5;
int r = (0 < val) - (val < 0); // this line here

会引起分枝。不幸的是，他们都没有给出任何理由或说明它为什么会导致分支（tristopia 建议它需要类似cmove的指令或谓词，但并没有真正说明原因）。

这些人是否正确地认为“表达式中使用的比较不会产生分支”实际上是神话而不是事实？（假设你没有使用一些深奥的处理器）如果是这样，你能举个例子吗？

我原以为不会有任何分支（鉴于没有合乎逻辑的“短路”），现在我很好奇。

4

3 回答 3

5

为了简化问题，只考虑表达式的一部分：val < 0. 本质上，这意味着“如果val为负，则返回1，否则0”；你也可以这样写：

val < 0 ? 1 : 0

如何将其转换为处理器指令在很大程度上取决于编译器和目标处理器。最简单的方法是编写一个简单的测试函数，如下所示：

int compute(int val) {
    return val < 0 ? 1 : 0;
}

并查看编译器生成的汇编代码（例如，使用gcc -S -o - example.c）。对于我的机器，它无需分支即可完成。但是，如果我将其更改为 return5而不是1，则会出现分支指令：

...
    cmpl    $0, -4(%rbp)
    jns     .L2
    movl    $5, %eax
    jmp     .L3
.L2:
    movl    $0, %eax
.L3:
...

因此，“在表达式中使用的比较不会生成分支”确实是一个神话。（但“在表达式中使用的比较总是会产生一个分支”也不是真的。）

响应此扩展/说明的补充：

我在问是否有任何（健全的）平台/编译器可能有一个分支。MIPS/ARM/x86(_64)/等。我正在寻找的只是一个证明这是一种现实可能性的案例。

这取决于你认为什么是“健全”的平台。如果古老的6502 CPU 系列是理智的，我认为val > 0没有分支就无法计算它。另一方面，大多数现代指令集都提供某种类型的 set-on-X 指令。

（val < 0实际上即使在 6502 上也可以不进行分支计算，因为它可以实现为位移。）

于 2013-05-03T01:11:21.293 回答
4

胜利的经验主义：

int sign(int val) {
    return (0 < val) - (val < 0);
}

编译优化。gcc (4.7.2) 产生

sign:
.LFB0:
    .cfi_startproc
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edi
    subl    %edi, %eax
    ret
    .cfi_endproc

没有分支。铿锵声（3.2）：

sign:                                   # @sign
    .cfi_startproc
# BB#0:
    movl    %edi, %ecx
    shrl    $31, %ecx
    testl   %edi, %edi
    setg    %al
    movzbl  %al, %eax
    subl    %ecx, %eax
    ret

两者都不。（在 x86_64、Core i5 上）

于 2013-05-03T01:34:26.093 回答
1

这实际上是依赖于架构的。如果存在根据另一个值的符号将值设置为 0/1 的指令，则不会发生分支。如果没有这样的指令，则需要进行分支。

于 2013-05-03T01:38:45.903 回答