这是C++代码的一块 显示一些非常特殊的行为

出于某种原因,对数据进行分类(之前奇迹般地使主环速度快近六倍:

#include <algorithm>
#include <ctime>
#include <iostream>

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

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

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop.
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}
  • 不无std::sort(data, data + arraySize);代码在11.54秒内运行
  • 根据分类数据 代码在1.93秒内运行

(分类本身需要的时间比这个通过数组的时间要长, 所以如果我们需要计算未知数组, 它实际上不值得做 。)


起初,我以为这只是一种语言或编译器异常, 所以我尝试了爪哇:

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)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop.
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

其结果类似,但不太极端。


我第一种想法是 分类能把数据带进缓存缓存,但那是愚蠢的 因为阵列是刚刚产生的。

  • 这是怎么回事?
  • 为什么处理一个分类阵列的速度要快于处理一个未排序阵列的速度?

守则正在总结一些独立的术语,因此命令不应重要。


相关/后续行动不同/以后的编译者和选项的相同效果:


当前回答

官方的回答是来自

  1. 英特尔 -- -- 避免因部门错误而承担的费用
  2. 英特尔 - 分行和循环重组以防止误判
  3. 科学论文 -- -- 分支预测计算机结构
  4. 书籍:J.L.Hennnesy、D.A. Patterson:计算机结构:定量方法
  5. 发表在科学出版物上的文章:T.Y.Yeh、Y.N.Patt在分支预测中做了许多这些文章。

你也可以从这个可爱的图表图为什么树枝预测器被弄糊涂了

2-bit state diagram

原始代码中的每个元素都是随机值

data[c] = std::rand() % 256;

所以预测器会变形为std::rand()口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交

另一方面,一旦对预测进行分类, 预测器将首先进入一个 强烈未被采纳的状态, 当值变化到高值时, 预测器将分三步走, 从强烈未被采纳到强烈被采纳。


其他回答

避免分支预测错误的一种方法是建立一个搜索表,并用数据来编制索引。 Stefan de Bruijn在答复中讨论了这一点。

但在此情况下,我们知道值在范围[0,255],我们只关心值 128。这意味着我们可以很容易地提取一小块来说明我们是否想要一个值:通过将数据移到右边的7位数,我们只剩下0位或1位数,我们只有1位数时才想要增加值。让我们把这个位数称为“决定位数 ” 。

将决定位数的 0/1 值作为索引输入一个阵列, 我们就可以生成一个代码, 无论数据是排序还是未排序, 都同样快速。 我们的代码总是会添加一个值, 但是当决定位数为 0 时, 我们将会添加一个值, 我们并不关心的地方 。 以下是代码 :

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

此代码浪费了一半的添加值, 但从未出现分支预测失败 。 随机数据比有实际的如果声明的版本要快得多 。

但在我的测试中,一个清晰的查看表比这个稍快一些, 可能是因为对一个查看表的索引比位变换略快一些。 这显示了我的代码是如何设置和使用搜索表的( 无法想象地称为“ 搜索表 ” ) 。lut代码中“ 查看表格” 。 这是 C++ 代码 :

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

在此情况下, 查看表只有256 字节, 所以它在一个缓存中非常适合, 并且非常快。 如果数据是 24 位值, 而我们只想要其中一半的话, 这个技术就不会有效... 搜索表会太大而不切实际。 另一方面, 我们可以将上面显示的两种技术结合起来: 首先将比特移开, 然后将一个查看表索引。 对于一个仅需要顶端半值的 24 位值, 我们可能会将数据右移12 位值, 并留下一个 12 位值的表格索引。 12 位表指数意味着一个有 4096 个值的表格, 这可能是实用的 。

将技术编成一个阵列,而不是使用if语句,可用于决定使用哪个指针。我看到一个实施二进制树的图书馆,而不是有两个命名指针(指针)。pLeftpRight或什么的)有长2至2的指针阵列,并使用“决定位位”技术来决定应跟随哪一个。例如,而不是:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

这个图书馆会做一些事情,比如:

i = (x < node->value);
node = node->link[i];

以下是这个代码的链接:红黑树, 永久封存

C+++ 中经常使用的布尔操作在 C+++ 中生成了编译程序中的许多分支。 如果这些分支是内部循环,并且难以预测,它们可以大大放慢执行速度。布尔变量以8位整数和数值存储。0用于false1用于true.

布尔变量被超值确定为超值, 也就是说, 所有有布尔变量作为输入的运算符都检查输入是否有其它值, 而不是01,但将布林作为输出输出的操作器除01。这样,用布林变量作为输入的操作效率就低于必要的效率。例如:

bool a, b, c, d;
c = a && b;
d = a || b;

这通常由汇编者以下列方式加以实施:

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

此代码远非最佳。 分支分支在出现错误的情况下可能需要很长的时间。 如果可以肯定地知道, 操作家除了使用其他的值之外没有其他的值, 布尔操作可以更高效得多 。01。为什么汇编器没有做出这样的假设,其原因是,如果变量未初始化或来自未知来源,则变量可能还有其他值。如果ab已经初始化为有效值, 或者它们来自产生 Boolean 输出的运算符。 优化的代码看起来是这样 :

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char使用代替bool以便能够使用比特顺序运算符( B) 。&|而不是 Boolean 运算符 (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1)&&||)bitwith运算符是只使用一个时钟周期的单一指令。|工作,即使ab具有其他数值的数值01AAD 经营者(AD)&和例外或经营人(或经营人(或经营人))^)如果特有产品有其他价值,则可能得出不一致的结果,如果特有产品有其他价值,则结果可能不一致。01.

~无法用于 NST 。 相反, 您可以在已知的变量上生成布尔 。011:

bool a, b;
b = !a;

可优化到 :

char a = 0, b;
b = a ^ 1;

a && b无法替换为a & b如果b是一个表达式,如果afalse ( &&将不评价b, &同样地,a || b无法替换为a | b如果b是一个表达式,如果atrue.

如果操作符是变量, 则使用比位运算符更有利 :

bool a; double x, y, z;
a = x > y && z < 5.0;

在大多数情况下最理想(除非预期&&表达式会生成多个分支错误) 。

在分类的情况下,你可以做的比依靠成功的分支预测或任何无分支比较的把戏:完全删除分支。

事实上,阵阵列被分割在一个毗连区内,data < 128data >= 128。因此,您应该用 a 来找到分区点脑细胞细胞研究(使用Lg(arraySize) = 15比较),然后从该点做一个直线积累。

类似的东西( 未检查 )

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

或, 略微糊涂

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

一种既快又快的方法,约近分类或未排序的解决方案为 :sum= 3137536;(假设分布真正统一,预计价值为191.5的16384个样本):-)

正如其他人已经提到的,神秘背后的背后是什么?处 预测员.

我不是要补充一些东西,而是要用另一种方式解释这个概念。维基文字有一个简明的介绍,里面有文字和图表。我确实喜欢下面的解释,下面用一个图表来用直觉来描述处的预言。

在计算机结构中,分支预测器是一种数字电路,它试图猜到分支(如如果是当时的else结构)将走哪条路,然后才能确定这一点。分支预测器的目的是改善教学管道的流量。分支预测器在很多现代管道式微处理器结构(如x86)实现高效运行方面发挥着关键作用。

双向分机通常是用有条件跳跃指令执行的。 有条件跳跃要么可以“ 不采取” , 继续使用在有条件跳跃后立即出现的代码第一分支, 要么可以在存储代码第二分支的方案记忆中“ 采取” 并跳到不同位置。 无法确定在计算条件和有条件跳跃通过指令管道的执行阶段之前是否采取有条件跳跃(见图1)。

figure 1

根据所述情况,我写了动画演示,以显示在不同情况下如何在管道中执行指示。

  1. 没有部门预言家。

没有分支预测,处理器必须等到有条件跳跃指令通过执行阶段后,下一个指令才能进入管道的接货阶段。

该示例包含三个指令, 第一个是有条件跳跃指令。 后两个指令可以进入管道, 直到有条件跳跃指令执行为止 。

without branch predictor

完成3项指示需要9小时周期。

  1. 使用预测器,不要采取有条件的跳跃。让我们假设预测是接受有条件的跳跃。

enter image description here

完成3项指示需要7小时周期。

  1. 使用预测器 进行有条件的跳跃 假设预测是接受有条件的跳跃。

enter image description here

完成3项指示需要9小时周期。

在分支误用的情况下,浪费的时间相当于从取货阶段到执行阶段的输油管阶段的数量。 现代微处理器往往有相当长的输油管,因此误用延迟时间在10到20小时之间。 结果,输油管更长时间增加了对更先进的分支预测器的需求。

如你所见,我们似乎没有理由不使用 部门预言家。

这是一个很简单的演示,可以澄清分支预言家的基本部分。如果这些小精灵很烦人,请随意将他们从答案中删除,访问者也可以从中获取源代码。PrepdictorDemo 分支介质

当对数组进行排序时,数据在 0 到 255 之间分布, 大约在迭代的前半部不会输入if- 声明if报表如下。 )

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

The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else分支预测器的目的是改善教学管道的流量。 分支预测器在实现高效运行方面发挥着关键作用 !

让我们做一些板凳标记 来更好理解它

性能、性能、性能、性能、性能、性能、性能、性能、性能、性能、性能、性能、性能、性能、性能、性if如果条件总是真实的,或者总是假的,处理器中的分支预测逻辑将拾取该模式。另一方面,如果该模式无法预测,那么,if- 声明会更贵得多

让我们用不同的条件来衡量这个循环的性能:

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

以下是环绕时间与不同的真假模式 :

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

“A ““真实的假造模式可以使if- 计算速度比“或”慢6倍。良好当然,哪一种模式是好的,哪一种模式是坏的,取决于汇编者的确切指示和具体处理者。

因此,部门预测对业绩的影响是毫无疑问的!