这是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);
    }
}

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


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

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

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


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


当前回答

避免分支预测错误的一种方法是建立一个搜索表,并用数据来编制索引。 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];

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

其他回答

由于一种被称为分支预测的现象,分类的阵列的处理速度要快于未排序的阵列。

分支预测器是一个数字电路(在计算机结构中),它试图预测一个分支会走哪条路,从而改善教学管道的流量。电路/计算机预测下一步并进行执行。

错误的预测导致回到前一步,执行另一个预测。 假设预测是正确的,代码将持续到下一步骤。 错误的预测导致重复同一步骤,直到出现正确的预测。

你问题的答案很简单

在未排列的阵列中,计算机进行多次预测,导致误差的可能性增加。而在分类的阵列中,计算机的预测减少,误差的可能性减少。 做更多的预测需要更多的时间。

排序的数组: 直路

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未排列的队列: 曲线路

______   ________
|     |__|

部门预测: 猜测/预测哪条道路是直的,未检查就沿着这条道路走

___________________________________________ Straight road
 |_________________________________________|Longer road

虽然两条道路都到达同一目的地,但直路更短,另一条更长。如果你错误地选择另一条道路,就没有回头路,所以如果你选择更长的路,你就会浪费一些更多的时间。这与计算机中发生的事情相似,我希望这能帮助你更好地了解。


我还想列举:@Simon_ weaver评论中:

它不会减少预测数量 — — 它会减少不正确的预测。 它仍然必须通过循环预测每一次...

如果您对这个代码可以做的更多优化感到好奇, 请考虑 :

以原始循环开始 :

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

通过循环互换,我们可以安全地将这一循环改为:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

然后,你可以看到,if条件条件在始终执行时为常数。i循环,这样你就可以升起if外出 :

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

假设浮点模型允许, 内环会崩溃成一个单一的表达式( 假设浮点模型允许的话 ) 。/fp:fast被抛出,例如)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

这比以前快了十万倍

除了树枝预测可能会减慢你的速度之外 分解阵列还有另一个优势

您可以有一个停止状态, 而不是仅仅检查值, 这样你只能环绕相关数据, 忽略其它数据 。
分支预测只会错失一次。

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

在同一行中(我认为没有任何答案强调这一点),最好提到有时(特别是在软件中,在软件中,性能很重要——如Linux内核),如果声明如下,你可以找到一些:

if (likely( everything_is_ok ))
{
    /* Do something */
}

或类似:

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

两者likely()unlikely()事实上,它们是通过使用诸如海合会(海合会)等东西来界定的宏观。__builtin_expect帮助编译者插入预测代码以有利于条件, 同时考虑到用户提供的信息 。 海合会支持其他能改变运行程序行为或发布低级别指令的内建元素, 如清除缓存等 。文献文件穿过海合会现有的建筑

通常这种优化主要在硬实时应用程序或内嵌系统中找到,在这些系统中,执行时间很重要且至关重要。例如,如果您正在检查某些错误条件,而错误条件只发生1/10000 000次,那么为什么不通知编译者?这样,默认情况下,分支预测会假设该条件是假的。

这是肯定的!

分处预测逻辑会放慢速度, 因为代码中的转换会发生! 就像你走一条直街或一条路, 转得很多,

如果对数组进行了排序,您的状态在第一步是虚假的:data[c] >= 128,然后成为通向街道尽头的整个路程的真正价值。这就是你如何更快地达到逻辑的终点。另一方面,使用一个未分类的阵列,你需要大量转动和处理,这可以保证你的代码运行速度较慢...

看看我在下面为你们创造的图象,哪条街会更快完工?

Branch Prediction

因此,从方案上说,子分支预测导致进程变慢...

最后,很高兴知道 我们有两种分支预测 每个分支将对你的代码产生不同的影响:

1. 静态

2. 动态

Branch Prediction

微处理器在第一次遇到有条件的分支时使用静态分支预测,在随后执行有条件的分支代码时使用动态分支预测。

为了有效地编写你的代码,以便利用这些规则,在撰写时if-ele 单位开关循环不一定需要固定分支预测的任何特殊代码顺序,因为通常只使用循环迭代器的条件。