标签: branch-prediction

与此答案相关:https://stackoverflow.com/a/11227902/4714970

在上面的答案中,提到了如何通过避免分支来避免分支预测失败.

用户通过替换以下内容来演示:

if (data[c] >= 128)
{
    sum += data[c];
}

附:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这两个是如何等效的(对于特定的数据集,不是严格等同的)？

在类似的情况下,我可以采取哪些一般方法来做类似的事情？它总是通过使用>>和~？

我遇到过一些场景，我想说函数的返回值可能在函数体内，而不是调用它的 if 语句。

例如，假设我想将代码从使用LIKELY宏移植到使用新[[likely]]注释。但这些在句法上不同的地方：

#define LIKELY(...) __builtin_expect(!!(__VA_ARGS__),0)
if(LIKELY(x)) { ... } 

对比

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

没有简单的方法可以重新定义LIKELY宏以使用注释。会定义一个函数

inline bool likely(bool x) { 
  if(x) [[likely]] return true;
  else return false;
}

将提示传播到if？像

if(likely(x)) { ... }

类似地，在通用代码中，很难在实际if语句中直接表达算法似然信息，即使该信息在其他地方是已知的。例如，a copy_ifwhere 谓词几乎总是假的。据我所知，没有办法用属性来表达，但如果分支权重信息可以通过函数传播，这是一个已解决的问题。

到目前为止，我还没有找到关于这个的文档，我不知道通过查看输出的程序集来测试这个的好设置。

我最近在这里阅读了这个问题为什么处理排序数组比未排序数组更快？并且发现答案绝对令人着迷,在处理基于Data的分支时,它完全改变了我对编程的看法.

我目前有一个用C编写的相当基本但功能完备的解释型Intel 8080仿真器,操作的核心是一个256长的交换机案例表,用于处理每个操作码.我最初的想法是,这显然是最快的工作方法,因为操作码编码在整个8080指令集中并不一致,并且解码会增加很多复杂性,不一致性和一次性情况.一个装有预处理器宏的开关盒表非常整洁,易于维护.

不幸的是,在阅读上述帖子之后,我发现我的电脑中的分支预测器绝对没有办法预测开关盒的跳跃.因此,每次切换案例时,必须完全擦除管道,导致几个周期延迟,否则应该是一个非常快速的程序(在我的代码中甚至没有多次乘法).

我相信大多数人都在想"哦,这里的解决方案很简单,转向动态重新编译".是的,这看起来似乎会削减大部分开关盒并大大提高速度.不幸的是,我的主要兴趣是模拟旧的8位和16位时代控制台(这里的英特尔8080只是一个例子,因为它是我最简单的模拟代码),其中保持精确指令的周期和时序对于视频和声音很重要必须根据这些确切的时间进行处理.

当处理这种级别的准确性时,性能成为一个问题,即使对于旧的控制台(例如,查看bSnes).在处理具有长管道的处理器时,是否有任何追索权或者这仅仅是事实？

这个问题及其答案最近被标记为史诗答案,这让我感到奇怪; 我可以根据CPU分支预测失败来衡量Windows中正在运行的应用程序的性能吗？我知道存在一些静态分析工具,这可能有助于在分支预测情况下优化代码以获得良好性能,并且手动技术可以通过简单地进行更改和重新测试来提供帮助,但我正在寻找一些可以自动化的机制.报告在一段时间内,当Windows应用程序运行时,分支预测失败的总数,我希望Visual C++的一些Profiler工具可以帮助我.

为了这个问题,有问题的应用程序可以使用本机编译器(如Visual C++ for Windows)构建,也可以使用其他本机编译器构建,例如GCC,FreePascal,Delphi或TurboAssembler.可执行文件可能根本没有任何调试信息.我想知道我是否可以检测并计算分支预测失败,可能是通过某些Windows服务(如WMI)读取内部CPU信息,或者可能完全在运行Windows的虚拟化环境中运行,例如使用VirtualBox,然后完全运行虚拟化Windows环境与我的测试应用程序,VirtualBox内部,并进行虚拟CPU的运行时分析.或者其他一些我不知道的技术,因此这个问题.

是的,我用Google搜索.唯一看起来很有希望的是来自AMD的PDF.我们提到了一些非常接近我想做的事情,但似乎是为没有任何操作系统的人在原始评估硬件平台上编写的:

5.1.分行.适用性.条件分支错误预测可能是具有大量决策逻辑的代码中的重要问题.

当选择真或假路径的可能性是随机的或接近50-50分裂时,条件分支可能被错误预测.分支预测硬件不能"学习"模式,并且不能正确预测分支.采集.收集此表中的事件以测量分支预测性能:

分支使用以下公式计算分支的采用率和每个分支的指令数的比率:分支采用率= Taken_branches/Ret_instructions分支采用率= Taken_branches /分支
每个分支的指令= Ret_instructions /分支

更新:我想我可以说我正在寻找一种方法来读取英特尔酷睿i7 PMU模块或其他CPU的等效功能.看起来英特尔VTUNE(来自Adrian的评论)非常接近我的要求.

我试图通过测量运行具有可预测分支的循环的时间与具有随机分支的循环来充分理解分支预测.

所以我写了一个程序,它采用不同顺序排列的0和1的大数组(即所有0,重复0-1,所有rand),并根据当前索引是0还是1,执行时间迭代数组分支浪费的工作.

我预计难以猜测的阵列需要更长时间才能运行,因为分支预测器会更频繁地猜错,并且两组阵列上的运行之间的时间差值将保持不变,而不管时间量如何 - 浪费工作.

然而,随着浪费时间的工作量的增加,阵列之间的运行时间差异增加了很多.

(X轴是浪费时间的工作量,Y轴是运行时间)

有谁理解这种行为？您可以在以下代码中看到我正在运行的代码:

#include <stdlib.h>
#include <time.h>
#include <chrono>
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
static const int s_iArrayLen = 999999;
static const int s_iMaxPipelineLen = 60;
static const int s_iNumTrials = 10;

int doWorkAndReturnMicrosecondsElapsed(int* vals, int pipelineLen){
        int* zeroNums = new int[pipelineLen];
        int* oneNums = new int[pipelineLen];
        for(int i = 0; i < pipelineLen; ++i)
                zeroNums[i] = oneNums[i] = 0;

        chrono::time_point<chrono::system_clock> start, end;
        start = chrono::system_clock::now();
        for(int i = 0; i …

我一直在尝试以下内容,并注意到这里定义的无分支"if"(现在有&-!!替换*!!)可以使用clang在64位Intel目标上加速某些瓶颈代码(几乎)2倍:

// Produces x if f is true, else 0 if f is false.
#define  BRANCHLESS_IF(f,x)          ((x) & -((typeof(x))!!(f)))

// Produces x if f is true, else y if f is false.
#define  BRANCHLESS_IF_ELSE(f,x,y)  (((x) & -((typeof(x))!!(f))) | \
                                     ((y) & -((typeof(y)) !(f))))

请注意,f应该是一个没有副作用的相当简单的表达式,以便编译器能够进行最佳的优化.

性能高度依赖于CPU和编译器.clang的无分支'if'表现非常出色; 我还没有找到任何无分支的'if/else'更快的情况.

我的问题是:这些是安全的,可移植的吗(意味着可以保证在所有目标上得到正确的结果),并且可以更快地制作吗？

无分支if/else的示例用法

这些计算64位最小值和最大值.

inline uint64_t uint64_min(uint64_t a, uint64_t b)
{
  return BRANCHLESS_IF_ELSE((a <= b), a, b);
}

inline uint64_t uint64_max(uint64_t a, uint64_t b)
{
  return BRANCHLESS_IF_ELSE((a >= b), …

本书的第3章称为计算机系统架构:程序员的观点,它表示一个类似的实现

testl %eax, %eax
cmovne (%eax), %edx

是无效的,因为如果预测失败,那么我们将有NULL解除引用.还声明我们应该使用分支代码.

不过,不使用条件跳转会导致相同的结果吗？例如:

.L1:
jmp *%eax

testl %eax, %eax
jne .L1

是否有可能欺骗gcc为x86-32输出类似的内容？假设我有一个指向函数的指针数组,其中一些是有效的,有些则不是,我称每个函数都不是NULL.

在参考这个问题时,答案指出未排序的数组花费更多时间,因为它未通过分支预测测试.但如果我们对程序进行微小改动:

import java.util.Arrays;
import java.util.Random;


public class Main{

    public static void main(String[] args) {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c) {
            data[c] = rnd.nextInt() % 256;
        }

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i) {
            // …

我有一个自定义ASSERT(...)宏,我在C++应用程序中使用.

#include <stdlib.h>
#include <iostream>

/// ASSERT(expr) checks if expr is true.  If not, error details are logged
/// and the process is exited with a non-zero code.
#ifdef INCLUDE_ASSERTIONS
#define ASSERT(expr)                                                      \
    if (!(expr)) {                                                        \
        char buf[4096];                                                   \
        snprintf (buf, 4096, "Assertion failed in \"%s\", line %d\n%s\n", \
                 __FILE__, __LINE__, #expr);                              \
        std::cerr << buf;                                                 \
        ::abort();                                                        \
    }                                                                     \
    else // This 'else' exists to catch the user's following semicolon
#else
#define ASSERT(expr)
#endif

最近我正在阅读一些Linux内核模块代码并遇到了 …

在现代奔腾上,似乎不再可能给处理器提供分支提示.假设一个分析编译器(如带有配置文件引导优化的gcc)可以获得有关可能的分支行为的信息,那么它可以做些什么来生成更快执行的代码？

我所知道的唯一选择是将不太可能的分支移动到函数的末尾.还有别的事吗？

更新.

http://download.intel.com/products/processor/manual/325462.pdf第2a卷第2.1.1节说

"分支提示前缀(2EH,3EH)允许程序向处理器提供关于分支最可能的代码路径的提示.仅将这些前缀用于条件分支指令(Jcc).其他使用分支提示前缀和/或保留其他具有Intel 64或IA-32指令的未定义操作码;此类使用可能会导致不可预测的行为."

我不知道这些实际上是否有任何影响.

另一方面,第3.4.1节.的http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf说

"编译器生成的代码可以提高英特尔处理器中分支预测的效率.英特尔C++编译器通过以下方式实现:

• 将代码和数据保存在不同的页面上
• 使用条件移动指令来消除分支
• 生成与静态分支预测算法一致的代码
• 在适当的地方内联
• 如果迭代次数是可预测的,则展开

通过配置文件引导优化,编译器可以布置基本块以消除函数的最频繁执行路径的分支或至少提高其可预测性.分支预测不一定是源级别的关注点.有关更多信息,请参阅英特尔C++编译器文档."

http://cache-www.intel.com/cd/00/00/40/60/406096_406096.pdf在"PGO的性能改进"中说

"PGO最适用于具有许多频繁执行的分支的代码,这些代码在编译时很难预测.例如,代码具有密集的错误检查,其中错误条件在大多数情况下都是错误的.不经常执行的(冷)错误处理代码可以重新定位,因此分支很少被错误预测.最小化冷代码交错到频繁执行的(热)代码可以改善指令缓存行为."