Branch prediction 和 Branch target prediction

发表于 |

假如 predicate 的概率是未知的，抑或 predicate 只会被设置一次，那么下面那种写法的性能更好呢？

  1. Branch prediction

    1
    2
    3
    4
    5
    6
    void dispatch() {
        if (predicate)
            logicA();
        else
            logicB();
    }

  2. Branch target prediction

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    fp = nullptr;
    void set_fp() {
        if (predicate)
            fp = logicA;
        else
            fp = logicB;
    }
    void dispatch() {
        fp();
    }

比较

Branch prediction is predicting whether or not the branch will be taken. Branch target prediction is prediction where the branch is going to.

Branch prediction 指的是预测是否选择这个分支。Branch target prediction 是预测这个分支走到哪里。从汇编角度来说，Branch prediction 指的是要不要 test 然后 je。Branch target prediction 指的是 jmp 到一个 $12345 还是一个 $eax。

  1. Unconditional branch, fixed target
    • 无限循环
    • goto
    • break、continue
    • 非虚函数调用
  2. Unconditional branch, variable target
    • 从函数返回
    • 虚函数调用
    • Function pointer call
    • switch 语句：如果被编译为 jump table
  3. Conditional branch, fixed target
    • if
    • switch 语句：如果被编译为 if
    • 带 condition 的 loop
    • && 和 || 操作符
    • ?: 这个三目运算符
  4. Conditional branch, variable target
    这个情况通常不会发生。但作为优化，编译器可能合成出一个来。比如下面的这个可能被编译成一个 conditional indirect jump，比如 jne *%eax。 
    1
    if (condition) { obj->VirtualFunctionCall(); }

一般 variable target 跳转无法内联的成本也要考虑在内。

Branch Target Buffer

对于当前 PC 通过 BTB 预测下一条 PC 是什么。如果预测错了，BTB 的对应条目会被更新。一个 naive 的 BTB 需要和程序本身一样大了。

所以，BTB 也是一个 LRU 一样的东西。只是 cache 住最可能需要被预测的指令。并且，BTB 的 “key” 也不需要整个 PC，而是 PC 的低几位。

Reference

  1. https://stackoverflow.com/questions/21608874/branch-prediction-vs-branch-target-prediction
  2. https://en.wikipedia.org/wiki/Branch_target_predictor
  3. https://stackoverflow.com/questions/32290875/branch-prediction-and-branch-target-prediction-optimization
  4. https://one2bla.me/cs6290/lesson4/branch-target-buffer.html