标签: branch-prediction

struct Obj {
  int x;
  int y;
  int z;
};

int Compare(Obj* a, Obj* b) {
  if (a->x > b->x) return 1;
  else if (a->x < b->x) return -1;

  if (a->y > b->y) return 1;
  else if (a->y < b->y) return -1;

  if (a->z > b->z) return 1;
  else if (a->z < b->z) return -1;

  return 0;
}

如上面的代码所示，最多有3个条件分支来获取比较结果。比较函数将由某种函数调用。如何优化代码来杀死条件分支，从而提高比较函数的性能？

--- 更新 --- 由于调用者 func 是快速排序的改进版本，它需要更大、更少和相等的结果。所以比较函数应该用-1、1、0来区分三个结果。

现代 C++ 中有[[likely]]和属性。G++ 和 clang++ 中[[unlikely]]都有相应的__builtin_expect(x, 1)内置函数。__builtin_expect(x, 0)但也有__builtin_unpredictable(x)和__builtin_expect_with_probability(x, 1, 0.5)或（同样）__builtin_expect_with_probability(x, 0, 0.5)内置函数，它告诉编译器防止 CPU 用来自（错误）预测分支的指令填充管道，因为从错误预测路径刷新+恢复管道的成本在统计上大于执行 w/o完全是投机执行。

在和分支上使用[[likely]]或同样[[unlikely]]使用属性（如以下代码片段所示）是否等同于使用假设属性？ifelse[[unpredictable]]

if (x) [[likely]] {
    // "if" branch
} else [[likely]] {
    // "else" branch
}

或者

if (x) [[unlikely]] {
    // "if" branch
} else [[unlikely]] {
    // "else" branch
}

据我所知，如果存在，if则编译器默认将分支视为默认情况，如果不存在（因为它通常是从当前函数提前退出的不愉快路径检查的形式）。因此，如果我只是省略任何一个属性，那么它并不等同于指定假设属性。[[likely]]else[[unlikely]]else[[unpredictable]]

考虑这段代码：

.globl _non_tail, _tail
.text

.code32
_non_tail:
    lcall $0x33, $_non_tail.heavensgate
    ret

.code64
_non_tail.heavensgate:
    # do stuff. there's 12 bytes on the stack before the first argument
    lret

.code32
_tail:
    pushl (%esp)
    movw %cs, 4(%esp)
    ljmp $0x33, $_tail.heavensgate

.code64
_tail.heavensgate:
    # do stuff. there's 8 bytes on the stack before the first argument
    lret

会_tail导致返回堆栈缓冲区错误预测未来的返回吗？一方面，它将近调用与远返回配对，但另一方面，它仍然返回到与正常情况完全相同的位置。

在阅读了为什么处理排序数组比处理未排序数组更快？,我在主循环中添加了一个额外的测试.似乎这个额外的测试使程序更快.

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
         data[c] = std::rand() % 256;

    //Don't sort the array
    //std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];

            //With …

分支预测逻辑有多"粘性"？如果从指令缓存中删除代码,统计数据是否保持不变？

换句话说,如果代码很复杂或者没有批量处理,那么分支预测是否会有所帮助？

让我们假设商品英特尔服务器硬件比2011年更新.

我在很多 SO 答案中都看到过这种代码：

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

哪里有作者说这个无分支。

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

您是否可以有意识地以特定方式编写代码,以便分支预测器将选择大多数情况下的选项.例如,错误检查资源是否已加载.如果可能的话,你如何利用这个优势？

CPU使用分支预测来加速代码,但仅限于实际采用第一个分支.

为什么不简单地采取两个分支？也就是说,假设两个分支都将被命中,缓存两侧,并在必要时采取适当的分支.缓存不需要无效.虽然这需要编译器预先加载两个分支(更多的内存,适当的布局等),但我认为适当的优化可以简化两者,以便可以从单个预测器获得接近最优的结果.也就是说,需要更多的内存来加载两个分支(对于N个分支是指数的),大多数时候应该能够在完成执行分支之前足够快地用新代码"重新缓存"失败的分支. .

if(x)Bl else Br;

不假设采用Bl,而是假设采用Bl和Br(某种类型的并行处理或特殊交织),并且在实际确定分支之后,一个分支随后无效,然后可以释放缓存以供使用(可能是一些需要特殊技术的类型才能正确填写和使用它.

实际上,不需要预测电路,并且所有用于此的设计可以用于处理两个分支.

任何想法,如果这是可行的？

特定向量（未屏蔽）发生硬件中断，CPU 检查 IF 标志并将 RFLAGS、CS 和 RIP 压入堆栈，同时后端仍有指令完成，其中一条指令的分支预测结果是错误的。通常管道会被刷新，前端开始从正确的地址获取，但在这种情况下，中断正在进行中。

当中断发生时，流水线中的指令会发生什么情况？

我已经读过这篇文章，显然解决方案是立即刷新管道中的所有内容，这样就不会发生这种情况，然后生成指令将 RFLAGS、CS、RIP 推送到 TSS 中内核堆栈的位置；然而，问题出现了，它如何知道与最新架构状态关联的 (CS:)RIP，以便能够将其推送到堆栈上（假设前端 RIP 现在将领先）。这类似于 port0 上的采取分支执行单元如何知道当采取预测结果错误时应该获取的 (CS:)RIP 的问题——是编码到指令中的地址以及预言？当你想到陷阱/异常时，也会出现同样的问题，CPU需要将当前指令（故障）或下一条指令（陷阱）的地址推送到内核堆栈，但是它是如何计算出这条指令的地址的当它处于管道的中途时——这让我相信地址必须被编码到指令中并使用长度信息计算出来，这可能全部在预解码阶段完成。

流水线中的分支惩罚是由 ALU 和 IF 之间的非零距离造成的。

这个声明是什么意思？