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

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


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

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

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


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


当前回答

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

以下代码不排序整个阵列,但只排序其中的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;
}

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

其他回答

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

以原始循环开始 :

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

这比以前快了十万倍

当对数组进行排序时,数据在 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倍。良好当然,哪一种模式是好的,哪一种模式是坏的,取决于汇编者的确切指示和具体处理者。

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

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

以下代码不排序整个阵列,但只排序其中的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;
}

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

以上行为之所以发生 是因为分局的预测

要理解分支预测,首先必须了解指令管道。

运行一个指令的步骤可以与运行上一个和下一个指令的步骤序列相重叠,这样可以同时同时执行不同的步骤。 这种技术被称为指令管衬,用来增加现代处理器的输送量。 要更好地了解这一点,请看维基百科的示例.

一般而言,现代处理器有相当长(和宽)的管道,因此许多教学可能正在飞行中。现代微处理器 A 90-minute指南!首先是引入基本自序管管,然后从那里开始。

但为容易,让我们考虑一个简单的 单用这四个步骤的单向输油管。
(像经典的5级RIRC,但忽略了单独的MEM阶段。 ))

  1. IF -- -- 从内存获取指令
  2. ID - 解码指令
  3. EX - 执行指令
  4. WB - 回写到 CPU 注册簿

一般为2项指示提供4级输油管。
4-stage pipeline in general

回到上述问题,让我们考虑以下指示:

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

如果没有部门预测,将出现下列情况:

要执行指令B或指令C,处理器必须等待(缓档直至指示A离开输油管中的EX阶段,因为进入指示B或指示C的决定取决于指示A的结果(即从何处取取取)。

无预测:何时if条件为真 : enter image description here

无预测:何时if条件为假 : enter image description here

由于等待指示A的结果,在上述情况下(没有分支预测;对真实和假的预测)所花的CPU周期总数为7个。

那么什么是分支预测?

分支预测器将尝试猜测分支( 如果- 如果- 如果- 如果- else 结构) 将往哪个方向走, 然后再确定这一点。 它不会等待指令 A 到达管道的 EX 阶段, 而是会猜测决定并转到该指令( 以我们为例 ) ( B 或 C ) 。

如果猜对了,输油管看起来是这样的: enter image description here

如果后来发现猜测是错误的,那么部分执行的指示就会被丢弃,管道从正确的分支开始,造成延误。如果分支错误,浪费的时间相当于管道从取货阶段到执行阶段的阶段数。现代微处理器往往有相当长的管道,因此错误处理的延迟时间在10到20小时的周期之间。输油管越长,对货物的需求就越大。分支分支预测器.

在业务方案代码中,这是有条件的、分支预测员第一次没有任何信息作为预测基础,因此第一次随机选择下一个指令。 (或返回到后方)静静在循环中,它可以将预测建立在历史之上。对于按升序排序的阵列,有三种可能性:

  1. 所有元素小于 128
  2. 所有元素大于 128
  3. 一些开始的新元素还不到128个,后来则大于128个

让我们假设预测器 将总是假设 真正的分支 在第一个运行。

因此,在第一种情况下,它总是要真正的分支,因为历史上它所有的预测都是正确的。 在第二种情况下,它最初预测错误,但经过几次反复,它会正确预测。 在第二种情况下,它最初将正确预测,直到元素低于128。 之后,它会失败一段时间,当它看到分支预测在历史上失败时,它会失败一段时间,它会正确。

在所有这些情况下,失败的数量将太少,因此,只需放弃部分执行的指示,从正确的分支重新开始,就只需要放弃部分执行的指示的几次,导致CPU周期减少。

但如果是随机的未排序数组,预测将需要丢弃部分执行的指示,然后大部分时间以正确的分支重新开始,结果与分类数组相比,CPU周期会增加。


进一步读作:

  • 现代微处理器 A 90-minute指南!
  • Dan Luu关于分支预测的文章(涵盖较老的分支预测器,而不是现代的IT-TAGE或倍数)
  • https://en.wikipedia.org/wiki/Branch_predictor
  • 处处预测和口译员的工作表现 -- -- 不相信民俗- 2015年,Intel's Haswell在预测Python口译员主循环的间接分支(由于不简单模式,历史上存在问题)方面表现如何,相对于未使用 IT-TAGE 的早期CPU。 (虽然他们不帮助完全随机的这个案例。如果在Skylake CPU的环中,当源被编译为分支时,如果在环中,Skylake CPU的误判率仍为50%。 )
  • 最新 Intel 处理器的静态分支预测- CPUs在运行分支指令时实际做什么,该指令没有动态预测。ifbreak)))后取(像环状)已被使用,因为它比什么都没有好。 设置代码, 这样快速路径/ 普通大小写最小化的分支对 I -cache 密度和静态预测都有好处, 所以编译者已经这样做了 。实际效果联 联 年 月 日 月 日 月 月 日 月 月 日 月 月 月 日 月 月 日 月 月 日 月 月 月 日 月 月 日 月 月 月 日 月 的 月 月 月 日 月 月 日 月 的 月 月 月 月 日 月 月 月likely / unlikely在 C 源中提示, 而不是在大多数 CPU 中暗示硬件分支预测, 除了通过静态预测。 )

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

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

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