没有成本的分支预测?

8
我刚刚偶然发现了这件事,我非常好奇现代CPU(当前的,也许是移动的或嵌入式的)在下面这种情况下是否实际上没有分支成本。

1.假设我们有以下代码:

x += a; // let's assume they are both declared earlier as simple ints  
if (flag)  
   do A  // let's assume A is not the same as B  
else  
   do B  // and of course B is different than A  

2. 相比之下:
if (flag)  
{  
  x += a   
  do A  
}  
else  
{  
   x += a  
   do B  
}

假设 AB 在流水线指令方面完全不同:
  1. 第二种方法会更快吗?

  2. CPU 能够聪明地知道无论标志是什么,下一条指令都是相同的吗(因此它们不必因分支预测错误而丢弃流水线阶段)?

注意:

在第一种情况下,如果出现分支预测错误,CPU 没有选择,只能放弃执行 do A 或 do B 的前几个流水线阶段,因为它们是不同的。我认为第二个示例类似于延迟分支:“即使我不知道标志是什么,我也要检查它,但我可以继续进行下一条指令,因为它是相同的,无论标志是什么,我已经有了下一条指令,并且使用它对我来说没问题。”

编辑:
我做了一些研究,得到了一些不错的结果。你如何解释这种行为?抱歉我的最新编辑,但我遇到了一些缓存问题,就我所看到的,这些是更准确的结果和代码示例。

这是使用 -O3 编译的代码,编译器版本为 gcc version 4.8.2(Ubuntu 4.8.2-19ubuntu1)。

情况1。

#include <stdio.h>

extern int * cache;
extern bool * b;
extern int * x;
extern int * a;
extern unsigned long * loop;

extern void A();
extern void B();

int main()
{
    for (unsigned long i = 0; i < *loop; ++i)
    {
        ++*cache;

        *x += *a;

        if (*b)
        {
            A();
        }
        else
        {
            B();
        }
    }

    delete b;
    delete x;
    delete a;
    delete loop;
    delete cache;

    return 0;
}

int * cache = new int(0);
bool * b = new bool(true);
int * x = new int(0);
int * a = new int(0);
unsigned long * loop = new unsigned long(0x0ffffffe);

void A() { --*x; *b = false; }
void B() { ++*x; *b = true; }

案例2
#include <stdio.h>

extern int * cache;
extern bool * b;
extern int * x;
extern int * a;
extern unsigned long * loop;

extern void A();
extern void B();

int main()
{
    for (unsigned long i = 0; i < *loop; ++i)
    {
        ++*cache;

        if (*b)
        {
            *x += *a;
            A();
        }
        else
        {
            *x += *a;
            B();
        }
    }

    delete b;
    delete x;
    delete a;
    delete loop;
    delete cache;

    return 0;
}

int * cache = new int(0);
bool * b = new bool(true);
int * x = new int(0);
int * a = new int(0);
unsigned long * loop = new unsigned long(0x0ffffffe);

void A() { --*x; *b = false; }
void B() { ++*x; *b = true; }

在两种方法的 -O3 版本之间几乎没有明显的区别,但是没有 -O3,第二种情况在我的机器上运行速度略快。我已经测试了没有 -O3 和循环 = 0xfffffffe 的情况下。
最佳时间:
alin@ubuntu:~/Desktop$ time ./1
real 0m20.231s
user 0m20.224s
sys 0m0.020s
alin@ubuntu:~/Desktop$ time ./2
real 0m19.932s
user 0m19.890s
sys 0m0.060s

4
这些东西通常由编译器进行优化,而不是在执行/CPU级别进行。 - Rohan
3
我认为编译器优化程序会把它的工作做好,将其分解以产生相同的代码。 - Non-maskable Interrupt
@Calvin 提取公共代码会破坏优化尝试。 - melpomene
1
@AlinIonutLipan:我从未见过x86机器上的编译器这样做(将情况1转换为情况2),但几十年前我确实在RISC机器上看到过(但不完全像这样)。而且确实是由编译器完成的。一般来说,您不能太依赖编译器优化,但这是一个相对简单和明显的针孔优化。我建议始终编写情况1,因为这对编译器更容易。 - yzt
嗨Ian,我在想x和b如何指向同一内存位置,因为它们每个都从自己的new调用中获取它们的内存?你能否更具体地解释一下? - Alin Ionut Lipan
显示剩余2条评论
2个回答

6

这个问题有两个方面:

第一,编译器会进行优化吗?

我们来做一个实验:

test.cc

#include <random>
#include "test2.h"

int main() {
  std::default_random_engine e;
  std::uniform_int_distribution<int> d(0,1);
  int flag = d(e);

  int x = 0;
  int a = 1;

  if (flag) {
    x += a;
    doA(x);
    return x;
  } else {
    x += a;
    doB(x);
    return x;
  }
}

test2.h

void doA(int& x);
void doB(int& x);

test2.cc

void doA(int& x) {}
void doB(int& x) {}

test2.cc和test2.h的存在仅是为了防止编译器优化掉所有内容。编译器无法确定是否存在副作用,因为这些函数存在于另一个翻译单元中。

现在我们编译为汇编:

gcc -std=c++11 -S test.cc

现在我们来看一下最有意思的组装部分:

  call  _ZNSt24uniform_int_distributionIiEclISt26linear_congruential_engineImLm16807ELm0ELm2147483647EEEEiRT_
  movl  %eax, -40(%rbp); <- setting flag
  movl  $0, -44(%rbp);   <- setting x
  movl  $1, -36(%rbp);   <- setting a
  cmpl  $0, -40(%rbp);   <- first part of if (flag)
  je    .L2;             <- second part of if (flag)
  movl  -44(%rbp), %edx  <- setting up x
  movl  -36(%rbp), %eax  <- setting up a
  addl  %edx, %eax       <- adding x and a
  movl  %eax, -44(%rbp)  <- assigning back to x
  leaq  -44(%rbp), %rax  <- grabbing address of x
  movq  %rax, %rdi       <- bookkeeping for function call
  call  _Z3doARi         <- function call doA
  movl  -44(%rbp), %eax
  jmp   .L4
.L2:
  movl  -44(%rbp), %edx  <- setting up x
  movl  -36(%rbp), %eax  <- setting up a
  addl  %edx, %eax       <- perform the addition
  movl  %eax, -44(%rbp)  <- move it back to x
  leaq  -44(%rbp), %rax  <- and so on
  movq  %rax, %rdi
  call  _Z3doBRi
  movl  -44(%rbp), %eax
.L4:

从上面的代码可以看出,编译器并没有对其进行优化处理。但我们也没有要求它进行优化。

g++ -std=c++11 -S -O3 test.cc

接下来是有趣的组装:

main:
.LFB4729:
  .cfi_startproc
  subq  $56, %rsp
  .cfi_def_cfa_offset 64
  leaq  32(%rsp), %rdx
  leaq  16(%rsp), %rsi
  movq  $1, 16(%rsp)
  movq  %fs:40, %rax
  movq  %rax, 40(%rsp)
  xorl  %eax, %eax
  movq  %rdx, %rdi
  movl  $0, 32(%rsp)
  movl  $1, 36(%rsp)
  call  _ZNSt24uniform_int_distributionIiEclISt26linear_congruential_engineImLm16807ELm0ELm2147483647EEEEiRT_RKNS0_10param_typeE
  testl %eax, %eax
  movl  $1, 12(%rsp)
  leaq  12(%rsp), %rdi
  jne   .L83
  call  _Z3doBRi
  movl  12(%rsp), %eax
.L80:
  movq  40(%rsp), %rcx
  xorq  %fs:40, %rcx
  jne   .L84
  addq  $56, %rsp
  .cfi_remember_state
  .cfi_def_cfa_offset 8
  ret
.L83:
  .cfi_restore_state
  call  _Z3doARi
  movl  12(%rsp), %eax
  jmp   .L80

这有点超出我的能力范围,无法清晰地展示汇编代码和代码之间的一对一关系,但你可以从对doA和doB调用中看出设置都是通用的并且在if语句外完成的。(在jne .L83上面的那行)。所以,编译器确实执行了这种优化。
第二部分:
如果给定第一个代码,我们如何知道CPU是否执行了此优化?
实际上,我不知道如何测试这个问题。所以我不知道。鉴于乱序执行和推测执行存在,我认为这是合理的。但证明就在结果中,我没有办法测试这个结果。因此,我不愿意做出任何肯定或否定的声明。

唯一真正的区别将是缺乏名称混淆和不同的随机函数名称调用。在我看来这很好。我在两种情况下都跳过了大部分设置。 - OmnipotentEntity
谢谢你的回答,我明白我们应该始终简洁地编写第一种情况。我想知道第二种情况是否可能比第一种情况更快(假设编译器对值一无所知,假设我们到处都是指针,编译器还不能知道副作用)。不知道如何优化第一种情况?我将自己进行一些测试,看看第二种情况是否可以更快,如果可以,速度会快多少。 - Alin Ionut Lipan
我只测试了第二种情况,以显示它将编译为与第一种情况在语义上等效的内容。根据您提供的有限示例,我无法看出第二种情况可能比第一种情况更快(仅相等)。也许您可以提供更多细节? - OmnipotentEntity
这就是我的意思,名称修饰对于非C++程序员来说很困惑,而且问题也被标记为C,flag = rand(); 就足够简单了。 - chqrlie
@chqrlie 如果您提出了这些更改(包括C代码和已注释的生成汇编),我将很乐意接受。我只是因为默认设置而进入了C++模式。 - OmnipotentEntity
显示剩余3条评论

5

过去,CPU明确支持一种类似的功能 - 在分支指令之后,无论分支是否被执行,下一条指令总是会被执行(可查看“分支延迟槽”)。

我相信现代CPU在分支预测错误时会直接丢弃整个管道。在执行时间尝试进行你所建议的优化没有意义,因为编译器可以轻松在编译时完成它。


啊,我正试图回忆起“延迟槽”的名称,以便发布与您几乎完全相同的答案。 :D - yzt
谢谢,我之前不知道延迟槽,这似乎正是我缺少的信息 :) 所以我认为写不干净的情况2没有意义。 - Alin Ionut Lipan
根据情况写出最清晰的内容,通常只需要一句话。 - Alan Stokes

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接