标签: branch-prediction

我正在学习计算机体系结构课程。我从另一所大学找到了这个网站，其中的笔记和视频迄今为止对我有帮助：CS6810，犹他大学。我正在完成该网站上发布的一些旧作业，特别是这个。我试图理解管道和相关概念，特别是停顿和分支延迟槽。

我现在正在看旧作业中的第一个问题，并且不确定如何做这些问题。

问题如下：

考虑以下代码段，其中 30% 的时间执行分支，70% 的时间不执行分支。

R1 = R2 + R3

R4 = R5 + R6

R7 = R8 + R9

如果 R10 = 0，则分支到 linex

R11 = R12 + R13

R14 = R11 + R15

R16 = R14 + R17

...

线性：R18 = R19 + R20

R21 = R18 + R22

R23 = R18 + R21

...

考虑一个 10 级有序处理器，其中指令在第一级中获取，并且分支结果在三个级后已知。估计以下场景下处理器的 CPI（假设处理器中的所有停顿都与分支相关，并且分支占所有执行指令的 15%）：

1. 在每个分支上，获取都会停止，直到知道分支结果为止。

2. 每个分支都被预测为不被采用，并且如果该分支被采用，则误取的指令将被压缩。

3. 处理器有两个延迟槽，分支后面的两条指令总是被取出并执行，并且

   3.1. 您无法找到任何说明来填充延迟槽。

   3.2. 您可以将分支之前的两条指令移至延迟槽中。

   3.3. 您可以将标签“linex”后的两条指令移至延迟槽中。

   3.4. 您可以在分支（在原始代码中）之后立即将一条（注意：一条，而不是两条！）指令移至延迟槽中。

我不确定如何开始看待这个问题。我已经阅读了所有笔记并观看了该网站上的视频，并阅读了 …

具体来说，我问的是双“！” 在 __built_in 的参数中。

按照“C”语言，它是双重否定吗？

当波前执行时,它提供细粒度多线程.其中一个后果是没有分支预测要求,如下面的幻灯片所示:

但我无法理解这一点.有人可以用一种简单的方式解释这个吗？

根据C++分支感知预测,我准备了一个测试,看看它有多么有效.

所以,在对照样本中,我写道:

int count=0;
for (auto _ : state) {
    if(count%13==0) {
        count+=2;
    }
    else
        count++;
    benchmark::DoNotOptimize(count);
}

在C++11分支预测中,我写道:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

int count=0;
for (auto _ : state) {
    if(UNLIKELY(count%13==0)) {
        count+=2;
    }
    else
        count++;
    benchmark::DoNotOptimize(count);
}

在一个C++20,

int count=0;
for (auto _ : state) {
    if(count%13==0)[[unlikely]]{
        count+=2;
    }
    else
        count++;
    benchmark::DoNotOptimize(count);
}

不幸的是,不支持quick-bench.但无论如何,我把它留在那里.

现在,在gcc和clang下获得基准测试对于这样一个基本的例子没有效果.

我做错了吗？

我在最坏情况下的输入（反向顺序列表）和随机输入上对插入排序进行基准测试。

import Control.Monad
import Data.List
import System.Random
import Control.Exception
import Control.DeepSeq
import Criterion.Main

--- Sorting ---
insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = x `insert` (sort xs)

--- Generators ---
worstCaseGen :: Int -> [Int]
worstCaseGen n = [n, n-1..1]

bestCaseGen :: Int -> [Int]
bestCaseGen n = [1..n]

randomGen :: Int -> StdGen -> [Int]
randomGen n = take n . randoms

--- Testing ---
main = do
  gen <- newStdGen …

我正在尝试衡量由std::shared_ptr和创建的指针的效率std::make_shared。

我有下一个测试代码：

#include <iostream>
#include <memory>
#include <vector>


struct TestClass {
    TestClass(int _i) : i(_i) {}
    int i = 1;
};

void sum(const std::vector<std::shared_ptr<TestClass>>& v) {
    unsigned long long s = 0u;
    for(size_t i = 0; i < v.size() - 1; ++i) {
        s += v[i]->i * v[i + 1]->i;
    }
    std::cout << s << '\n';
}

void test_shared_ptr(size_t n) {
    std::cout << __FUNCTION__ << "\n";
    std::vector<std::shared_ptr<TestClass>> v;
    v.reserve(n);
    for(size_t i = 0u; i < n; …

对于那些已经测量过或对此类注意事项有深入了解的人，假设您必须执行以下操作（仅选择任何示例）浮点运算符：

float calc(float y, float z)
{ return sqrt(y * y + z * z) / 100; }

哪里y和z可能是非正规数，让我们假设两种可能的情况，其中只有 y，只有 z，或者两者，以完全随机的方式，可以是非正规数

• 50%的时间
• <1% 的时间

现在假设我想避免处理非正规数的性能损失，我只想将它们视为 0，然后通过以下方式更改该段代码：

float calc(float y, float z)
{
   bool yzero = y < 1e-37;
   bool zzero = z < 1e-37;
   bool all_zero = yzero and zzero;
   bool some_zero = yzero != zzero;

   if (all_zero)
      return 0f;

   float ret;

   if (!some_zero) ret = sqrt(y * y + z * z);
   else if (yzero) …

在这段代码中，它被写成result += runs[i] > runs[i-1];一个隐式条件语句。在 C++ 中，分支预测器是否对该语句进行预测？或者我是否必须明确使用if关键字来进行分支预测？

using namespace std; 
int progressDays(vector<int> runs) {
    if (runs.size() < 2) {return 0;}
    int result = 0;
    for (int i = 1; i < runs.size(); i++) {result += runs[i] > runs[i-1];}
    return result;
}

我对分支预测了解一些。这发生在 CPU 上，与编译无关。尽管您可能能够告诉编译器一个分支是否比另一个分支更有可能，例如在 C++20 中，通过[[likely]]and [[unlikely]]（请参阅cppreference）这与 CPU 执行的分支预测是分开的（请参阅我可以使用我的代码改进分支预测吗？ ？）。

据我所知，当我有一个循环（带有退出条件）时，CPU 会预测退出条件不会得到满足，并尝试在循环内执行一些操作，即使条件尚未检查。如果 CPU 预测正确，它会节省一些时间，一切都会好起来。然而，如果它无法正确预测会发生什么？我知道这会对性能造成影响，但我不知道一些已经完成的操作是否被丢弃或逆转，或者只是如何处理。

现在我想出了两个简单的例子。第一个（如果我们忽略编译器可能只是在编译时计算总和并且我假设没有发生优化）对于 CPU 来说应该很容易预测。循环条件始终相同，并且循环中的条件仅切换一次。这意味着预测将为我们带来很好的性能提升，即使它失败了几次，添加一个数字也可以很容易地逆转。

在第二个示例中，退出条件也很容易预测。在循环体中，我int通过分配一个新数组malloc。请注意，我不是故意释放它的，因为我希望分配能够长期成功，以便 CPU 预测到这一成功。有时，当我用完内存（我没有计算总内存消耗并假设内存不会移动到磁盘）或发生其他错误时，分配会失败。这意味着ptrwill beNULL并且取消引用它是UB。没有定义会发生什么，它可能只是一个空操作，使我的程序崩溃或导致我的电脑飞走。因此我得出结论，CPU 不能简单地撤消这一点，我想知道会发生什么。

#include <stdlib.h>

#define VERSION 1

#if VERSION == 1
int main() {
    size_t sum = 0ull;

    for (size_t i = 0ull, max = 1'000ull; i < max;  ++i) {
        if (i < (max / 2)) {
            sum += 2 * i;
        } …

我在Cortex-R4中运行的C代码中进行优化.首先,当我在条件检查中指出"__builtin_expect"时,我没有看到汇编代码输出有任何变化.似乎编译器生成了不必要的跳转.

我的C代码:

           bit ++; (Likely)

if(__builtin_expect(bit >= 32),0) 
{ 
  bit -=32; // unlikely code
  xxxxxx;   // unlikely code
  xxxxxx;   // unlikely code
  xxxxxx;   // unlikely code
} 

bit = bit*2 // something  (Likely)
return bit; 

----生成的ASM代码--------(位=> r0)

                      ADD   r2,r2,#1 
                      CMP   r0,#0x20 
                      BCC  NoDecrement 
                      SUB   r0,r0,#0x20 
                      XXXXXXXXX 
                      XXXXXXXXX 
                      XXXXXXXXX 
NoDecrement LSL   r0,r0,#1 
                          BX  lr 

----我期望的ASM代码--------

                          ADD   r2,r2,#1 
                          CMP   r0,#0x20 
                          BHE   Decrement 
JumbBack       LSL   r0,r0,#1 
                          BX  lr 
Decrement      SUB   r0,r0,#0x20 
                          XXXXXXXXX 
                          XXXXXXXXX 
                          XXXXXXXXX 
                          B JumbBack

假设这段C代码在循环中运行,那么每次都必须跳转(因为if条件只传递一次).是否有任何其他编译器设置实际上,按预期生成代码.. ??