标签: branch-prediction

我有这个C函数:

double f(int x)
{
    if (x <= 0)
        return 0.0;
    else
        return x * log(x);
}

我在一个紧凑的循环中调用,并希望摆脱分支,看看它是否提高了性能.

我不能用这个:

double f(int x)
{
    return x * log(x);
}

因为它返回的NaN时间x == 0(大约25%的时间都是如此).

有没有另一种方法来实现它,以便它返回0时x == 0,但仍然摆脱分支？

(我不太关心负输入,因为这些是错误,而零则不是.)

据我所知,Return Stack Buffer仅支持4到16个条目(来自wiki:http://en.wikipedia.org/wiki/Branch_predictor#Prediction_of_function_returns)并且不是键值对(基于ret指令位置的索引) ).这是真的吗？上下文切换发生时RSB会发生什么？

假设我们进入了50个函数,这些函数在返回堆栈缓冲区长度为16的CPU中没有返回,之后会发生什么？这是否意味着所有预测都失败了？你能说明一下吗？这种情况在递归函数调用中是否相同？

谢谢!

以下copy_bit功能可以简化为类似的功能out[out_bit] = in[in_bit]吗？(即不使用if声明)

template< typename T >
inline void copy_bit( T& out, const T in, const std::size_t out_bit, const std::size_t in_bit )
{
    if ( (in & (1 << in_bit)) != 0 )
    {
        out |= (1 << out_bit); // Set bit
    }
    else
    {
        out &= ~(1 << out_bit); // Clear bit
    }
}

// Set bit 4 in x to bit 11 in y
copy_bit( x, y, 4, 11 );

更新:为了清楚起见,这不是家庭作业或XY问题,建议 …

我试图在这个着名的问题中复制这个例子.我的代码看起来像这样:

#![feature(test)]
extern crate rand;
extern crate test;

use test::Bencher;
use rand::{thread_rng, Rng};

type ItemType = u8;
type SumType = u64;
const TEST_SIZE: usize = 32_768;

#[bench]
fn bench_train(b: &mut Bencher) {
    let numbers = get_random_vec();
    b.iter(|| calc_sum(&numbers));
}

#[bench]
fn bench_train_sort(b: &mut Bencher) {
    let mut numbers = get_random_vec();
    numbers.sort();     // <-- the magic difference
    b.iter(|| calc_sum(&numbers));
}

fn get_random_vec() -> Vec<ItemType> {
    thread_rng().gen_iter().take(TEST_SIZE).collect()
}

fn calc_sum(numbers: &Vec<ItemType>) -> SumType {
    let mut sum = 0;
    for …

在谈论ifs的表现时,我们通常会谈论错误预测如何阻止管道.我看到的推荐解决方案是:

1. 相信通常有一个结果的条件的分支预测器; 要么
2. 如果合理可能的话,避免使用一点点魔法分支; 要么
3. 有条件的移动尽可能.

我找不到的是我们是否能尽早计算出病情,以便在可能的情况下提供帮助.所以,而不是:

... work
if (a > b) {
    ... more work
}

做这样的事情:

bool aGreaterThanB = a > b;
... work
if (aGreaterThanB) {
    ... more work
}

这样的事情可能会完全避免这个条件的停顿(取决于管道的长度和我们可以放在bool和if之间的工作量)？这并不一定是因为我写的,但有什么办法,以评估条件语句早,所以CPU不必尝试和预测的分支？

此外,如果这有帮助,编译器可能会做什么呢？

像Kaby Lake这样的现代CPU如何处理小分支？(在下面的代码中是跳转到标签LBB1_67).据我所知,分支不会有害,因为跳转不如16字节块大小,这是解码窗口的大小.

或者是否有可能由于某些宏观操作融合,分支将被完全省略？

        sbb     rdx, qword ptr [rbx - 8]
        setb    r8b
        setl    r9b
        mov     rdi, qword ptr [rbx]
        mov     rsi, qword ptr [rbx + 8]
        vmovdqu xmm0, xmmword ptr [rbx + 16]
        cmp     cl, 18
        je      .LBB1_67
        mov     r9d, r8d
.LBB1_67:                               #   in Loop: Header=BB1_63 Depth=1
        vpcmpeqb        xmm0, xmm0, xmmword ptr [rbx - 16]
        vpmovmskb       ecx, xmm0
        cmp     ecx, 65535
        sete    cl
        cmp     rdi, qword ptr [rbx - 32]
        sbb     rsi, qword ptr [rbx - 24]
        setb    dl
        and …

初步信息：根据最近的ISO C ++委员会旅行报告，将在最新版本的GNU GCC中添加并提供条件分支的[[ likely ]]和[[ unlikely ]]属性C++20（您可以在在线编译器wandbox.org上使用它）。

问题：以下构造

if (cond) [[ likely ]] { ... }

相当于以下一个？

if (__builtin_expect(bool(cond), 1)) { ... }

为了有效使用它，不同编译器之间是否存在性能差异或实现细微差别？

我试图了解分支预测单元如何在 CPU 中工作。

我已经使用了papilinux，perf-events但它们都没有给出准确的结果（就我而言）。

这是我的代码：

void func(int* arr, int sequence_len){
  for(int i = 0; i < sequence_len; i++){
      // region starts
      if(arr[i]){
          do_sth();
      }
      // region ends
  }
}

我的数组由 0 和 1 组成。它有一个大小为 的图案sequence_len。例如，如果我的尺码是 8，那么它有一个图案0 1 0 1 0 0 1 1或类似的图案。

试验 1：

我试图了解 CPU 如何预测这些分支。因此，我使用 papi 并为错误预测的分支预测设置了性能计数器（我知道它也计算间接分支）。

int func(){
  papi_read(r1);
  for(){
    //... same as above
  }
  papi_read(r2);
  return r2-r1;
}

int main(){
   init_papi();
   for(int i = 0; i < …

在尝试以 CSC 格式对简单稀疏单元下三角后向求解的实现进行基准测试时，我观察到奇怪的行为。性能似乎有很大差异，具体取决于汇编指令在可执行文件中的最终位置。我在同一问题的许多不同变体中观察到这一点。一个最小的例子是获取重复的实施指令

void lowerUnitTriangularTransposedBacksolve(const EntryIndex* col_begin_indices,
                                            const Index* row_indices,
                                            const Value* values,
                                            const Index dimension, Value* x) {
  if (dimension == 0) return;

  EntryIndex entry_index = col_begin_indices[dimension];
  Index col_index = dimension;
  do {
    col_index -= 1;
    const EntryIndex col_begin = col_begin_indices[col_index];

    if (entry_index > col_begin) {
      Value x_temp = x[col_index];
      do {
        entry_index -= 1;
        x_temp -= values[entry_index] * x[row_indices[entry_index]];
      } while (entry_index != col_begin);
      x[col_index] = x_temp;
    }
  } while (col_index != 0);
}

在两个函数中benchmarkBacksolve1和benchmarkBacksolve2 …

我写了这个非常简单的 Rust 函数：

fn iterate(nums: &Box<[i32]>) -> i32 {
    let mut total = 0;
    let len = nums.len();
    for i in 0..len {
        if nums[i] > 0 {
            total += nums[i];
        } else {
            total -= nums[i];
        }
    }

    total
}

我编写了一个基本的基准测试，它使用一个有序数组和一个无序数组调用该方法：

fn criterion_benchmark(c: &mut Criterion) {
    const SIZE: i32 = 1024 * 1024;

    let mut group = c.benchmark_group("Branch Prediction");

    // setup benchmarking for an ordered array
    let mut ordered_nums: Vec<i32> = vec![];
    for i in 0..SIZE {
        ordered_nums.push(i - …