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

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


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

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

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


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


当前回答

这是肯定的!

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

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

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

Branch Prediction

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

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

1. 静态

2. 动态

Branch Prediction

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

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

其他回答

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

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

或类似:

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

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

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

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

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

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

你问题的答案很简单

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

排序的数组: 直路

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

未排列的队列: 曲线路

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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


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

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

我刚读过这个问题及其答案,我觉得缺少答案。

消除我发现在管理下语言中特别出色的分支预测的一个常见方法是, 表格搜索而不是使用分支(虽然我还没有在本案中测试过它 ) 。

如果:

  1. 它是一个小桌子 很可能在处理器中隐藏
  2. 您正在一个非常紧凑的循环中运行着一些东西和/或处理器可以预加载数据。

背景和原因

从处理器的角度来看,您的内存是慢的。为了弥补速度的差异,在您的处理器( L1/L2 缓存) 中嵌入了几个缓存。 想象一下, 您正在做你的好计算, 并发现您需要一个内存。 处理器会得到它的“ 装载” 操作, 并将内存部分装入缓存中, 然后用缓存来进行其余的计算。 因为内存相对缓慢, 此“ 装载” 将会减缓您的程序 。

像分支预测一样,这在Pentium处理器中被优化了:处理器预测,它需要在操作实际到达缓存之前装入一个数据,并试图将数据装入缓存中。我们已经看到,分支预测有时会发生可怕的错误 -- -- 在最坏的情况下,你需要回去等待一个记忆负荷,这将需要永远的时间(我们已看到,分支预测有时会发生可怕的错误)。换句话说,失败的分支预测是坏的,在分支预测失败之后的记忆负荷实在是太可怕了!).

幸运的是,对于我们来说,如果记忆存取模式可以预测,处理器将装在快速缓存中,一切都很好。

我们首先需要知道的是? 虽然小一点一般比较好,但大拇指规则是坚持使用大小为 4096 字节的搜索表格。作为一个上限:如果您查看的表格大于 64K, 可能值得重新考虑 。

构建表格

因此我们发现我们可以创建一个小表格。 接下来要做的是设置一个查找功能。 查找功能通常是使用几个基本整数操作( 以及, 或者, xor, 转换, 转换, 添加, 删除, 或倍增) 的小型函数。 您想要将您的输入通过外观功能转换为表格中某种“ 独一无二的密钥 ” , 这样就可以简单给出您想要它做的所有工作的答案 。

在此情况下 : 128 表示我们可以保留这个值, < 128 表示我们摆脱它。 最简单的方法就是使用“ 和 ” : 如果我们保留它, 我们和它使用 7FFFFFFF; 如果我们想要摆脱它, 我们和它使用 0。 注意 128 也是一种2 的功率, 所以我们可以继续制作一个32768/128 整数的表格, 并填满它 1 0 和很多 7FFFFFFFFFFFF。

受管理语言

毕竟,管理下的语言会用分支来检查阵列的界限,以确保你不会搞砸...

嗯,不确切地说... : -)

在取消管理下语文的这一分支方面,已经做了相当多的工作。

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

在此情况下, 编译者明显知道边界条件永远不会被击中 。 至少微软 JIT 编译者( 但我预计爪哇会做类似的事情) 将会注意到这一点并完全取消检查 。 WOW 表示没有分支 。 同样, 它也会处理其他明显的例子 。

如果您遇到管理下语言的查询问题 -- -- 关键是添加 a& 0x[something]FFF使边界检查可以预测, 并且看着它更快地发展。

本案的结果

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

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

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();

分流收益!

重要的是要理解分支错误控制不会减慢程序。 错误预测的成本就好像不存在分支预测,而你等待着对表达方式的评价来决定运行的代码(下段有进一步的解释 ) 。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

每当有if-else \ switch语句中,必须评价表达式,以决定应执行哪个区块。在编译器生成的组装代码中,有条件分支分支分支插入说明。

分支指令可导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即如果表达式为虚假,程序跳过代码)if(根据某些条件,即我们案件的表达方式评价)

尽管如此,汇编者试图在对结果进行实际评估之前预测结果。if如果表达式是真实的,那么就太好了!我们得到了评估它所需的时间,并在代码中取得了进展;如果不是,我们运行错误的代码,管道被冲洗,正确的模块被运行。

可视化:

假设你需要选择路线1或路线2, 等待你的伴侣检查地图, 你已经停留在 ##,等待, 或者你可以选择路线1, 如果你运气好(路线1是正确的路线), 那么伟大的你不必等待你的伴侣检查地图(你省下时间让他检查地图), 否则你就会转回去。

尽管冲水管道的速度超快,但如今赌博是值得的。 预测分类数据或缓慢变化的数据总是比预测快速变化容易,也好于预测快速变化。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

巴恩·斯特鲁斯特鲁斯特鲁普的回答对此问题:

这听起来像面试问题。是真的吗?你怎么知道?回答效率问题而不首先做一些测量是不明智的,所以知道如何衡量是很重要的。

于是,我用百万整数的矢量尝试过,然后得到:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

我跑了好几次才确定。 是的,这个现象是真实的。我的关键代码是:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label
         << duration_cast<microseconds>(t1 — t0).count()
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

至少这个编译器、 标准库和优化设置是真实存在的。 不同的执行可以而且确实提供了不同的答案。 事实上,有人做了更系统的研究( 快速的网络搜索会找到它) , 而大多数执行都显示了这种效果。

其中一个原因是分支预测: 类算法中的关键操作是“if(v[i] < pivot]) …”对于排序序列,测试总是真实的,而对于随机序列,选定的分支则随机变化。

另一个原因是,当矢量已经分类后,我们从不需要将元素移到正确位置。这些小细节的影响是我们看到的5或6个系数。

Quicksort(以及一般分类)是一项复杂的研究,吸引了计算机科学中最伟大的一些思想。 一种良好的功能是选择良好的算法和关注硬件的运行效果的结果。

如果您想要写入高效代码, 您需要了解一些关于机器结构的知识 。