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

由于某种原因,对数据进行分类(在时间区之前)奇迹般地使主要循环速度快近六倍:

#include 
#include 
#include 

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(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}

没有 std: sort( 数据, 数据+数组Size); 代码在 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);
    }
}

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


我的第一个想法是排序 将数据带入缓存, 但这是愚蠢的,因为数组 刚刚生成。

为什么处理一个分类阵列的速度要快于处理一个未分类阵列的速度?

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


与不同的/后来的汇编者和备选办法具有相同效果:

为什么处理一个未排列的阵列的速度与处理一个用现代 x86-64 叮当的排序阵列的速度相同? gcc 优化标记 -O3 使代码慢于 -O2


当前回答

正如其他人已经提到的那样,神秘背后的是部门预测员。

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

在计算机结构中,分支预测器是一种数字电路,它试图猜测分支(如如果是当时的else结构)将以何种方式进行,然后才能确定这一点。分支预测器的目的是改善教学管道的流量。分支预测器在很多现代管道式微处理器结构(如x86)中实现高有效性能方面发挥着关键作用。双向分支通常是通过有条件的跳跃指令来实施。有条件跳跃可以是“不采取”的,也可以是有条件跳跃后立即实施的代码的第一个分支,或者可以是“获取”的,然后跳到存储第二分支的程序内存中的不同位置。在计算条件和有条件跳动通过指令管道的执行阶段之前,无法确定是否进行有条件跳动(见图1)。

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

没有部门预言家。

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

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

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

使用预测器,不要采取有条件的跳跃。让我们假设预测不会采取有条件的跳跃。

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

我们假设预测不会采取有条件的跳跃

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

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

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

这是一个很简单的演示, 澄清了分支预测器的基本部分。 如果这些 gifs 令人烦恼, 请随意将其从答案中删除, 访问者也可以从 PredictorDemo 获得现场演示源代码 。

其他回答

我用MATLAB 2011b 和我的MacBook Pro(Intel i7, 64位, 2.4 GHz) 尝试了以下MATLAB 代码的相同代码 :

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

上述MATLAB代码的结果如下:

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

校对:Soup

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

基于这一点,看来MATLAB比C执行慢了175倍,没有分类,比C执行慢了350倍,换言之,(分支预测)MATLAB执行效果为1.46x,C执行效果为2.7x。

这是肯定的!

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

If the array is sorted, your condition is false at the first step: data[c] >= 128, then becomes a true value for the whole way to the end of the street. That's how you get to the end of the logic faster. On the other hand, using an unsorted array, you need a lot of turning and processing which make your code run slower for sure...

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

因此,在程序上,分支预测导致过程的慢化...

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

1. 静态

2. 动态

微处理器在第一次遇到有条件分支时使用静态分支预测,在随后执行有条件分支代码时则使用动态分支预测。为了有效编写代码以利用这些规则,在撰写 if-else 或 开关 语句时,先检查最常见的情况,然后逐步工作到最不常见的情况。循环不一定要求固定分支预测使用任何特殊的代码顺序,因为通常只使用循环迭代器的条件。

分流收益!

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

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

当出现 if-else \ 切换语句时, 表达式必须被评估以确定要执行哪个区块。 在编译者生成的组装代码中, 插入有条件的分支指令 。

分支指令可导致计算机开始执行不同的指令序列,从而偏离其默认的按顺序执行指令的行为(即如果表达式是虚假的,程序会跳过区块的代码),这取决于某些条件,即我们情况下的表达式评价。

尽管如此, 编译者试图预测结果, 然后再对结果进行实际评估。 它会从区块中获取指示, 如果表达方式是真实的, 那么就太好了! 我们得到了时间来评估它, 并在代码中取得了进步; 如果不是那样, 我们运行错误的代码, 管道就会被冲洗, 正确的区块会运行 。

可视化:

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

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

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

其他答复的假设是,一个人需要对数据进行分类是不正确的。

以下代码不排序整个阵列,但只排序其中的200个元素部分,因此运行速度最快。

只排序 k- 元素区域时, 以线性时间( O(n)) 完成预处理, 而不是以 O( n. log(n)) 时间来排序整个数组 。

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

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

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

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

这个“证明”也与任何算法问题无关, 比如排序顺序, 并且确实是分支预测。

C++ 中经常使用的布尔操作在编译的程序中产生许多分支。 如果这些分支是内部循环, 且难以预测, 则它们可以大大减缓执行速度。 布尔变量以8位数整数存储, 值为 0, 值为假值, 值为 1 值为真值 。

布尔变量被超额确定,因为所有以布尔变量作为输入变量的操作员都检查输入值是否有比 0 或 1 的其他值,但以布尔值作为输出的操作员不能产生比 0 或 1. 的其他值。 这样,以布尔变量作为输入的操作效率就比必要低。 请举例说明 :

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;
}

此代码远非最佳 。 如果出现错误, 分支可能要花很长的时间。 如果可以肯定地知道, 布林操作没有比 0 和 1 的其他值, 则可以使布林操作效率更高。 原因是, 编译者没有做出这样的假设, 如果变量未初始化或者来自未知来源, 则这些变量可能有其他值。 如果 a 和 b 被初始化为有效值, 或者如果它们来自产生布林输出的操作员, 则上述代码可以优化。 最优化的代码看起来是这样 :

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

使用字符代替布尔, 以便使用比位操作员( & 和 & ) 而不是布尔操作员( 和 ) 。 比位操作员是单项指令, 只需要一个时钟周期 。 OR 操作员( 和 ) 工作, 即使 a 和 b 的值比 0 或 1. 操作员( ) 和 Exclusive 或 操作员( ) 可能会产生不一致的结果, 如果操作员的值比 0 和 1 不同 , 操作员( ) 和 Exclusive 或操作员( ) 可能会产生不一致的结果 。

~ 无法用于非。 相反, 您可以在变量上做一个布尔, 变量为 0 或 1 , 使用 XOR, 使用 1 :

bool a, b;
b = !a;

可优化到 :

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

a \\ b 无法被 & b 替换为 & b 表达式, 如果 b 是假的表达式, 则该表达式不应被评估( \ \ 将不评估 b, & will) 。 同样, a \ b 也不能被 \ b 替换为 \ b , 如果 b 是真实的, 则该表达式不应被评估 。

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

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

在大多数情况下是最佳的(除非您预期 表达式会产生很多分支错误)。