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

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


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

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

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


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


当前回答

在对数据进行分类时,业绩显著改善的原因是,如A/CN.9/WG.WG.III/WG.WG.III/WP.A/WG.WG.III/WP.A/A/WG.WG.III/WP.A/WG.A/WP.A/WG.A/WP.A/WP.A/WP.A/WG.A/WP.A/WP.A/WP.A/WP.A/WP.神秘的答案.

现在,如果我们看看代码

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

我们能发现这个特别的if... else...当满足条件时,该分支将添加某种内容。这种类型的分支可以很容易地转换成条件移动语句,该语句将汇编成有条件移动指令:cmovl,在一个x86取消了分支系统,从而取消了潜在的分支预测罚款。

C因此,C++,该语句,该语句将直接(不作任何优化)编成有条件移动指令x86,是永久经营人... ? ... : ...。因此,我们将上述声明重写为相应的声明:

sum += data[c] >=128 ? data[c] : 0;

在保持可读性的同时,我们可以检查加速系数。

在一个情报机关上,核心 i7-2600K@3.4 GHz和视觉工作室2010发布模式,基准是:

x86x86

假设情景 时间( 秒)
分处 - 随机数据 8.885
分支 - 分类数据 1.528
无分支 - 随机数据 3.716
无分支 - 排序数据 3.71

x64 x64

假设情景 时间( 秒)
分处 - 随机数据 11.302
分支 - 分类数据 1.830
无分支 - 随机数据 2.736
无分支 - 排序数据 2.737

结果在多个测试中是稳健的。 当分支结果无法预测时, 我们得到一个巨大的加速, 但是当它可以预测时, 我们遭受了一点点痛苦。 事实上, 当使用有条件的动作时, 无论数据模式如何, 性能都是一样的 。

现在让我们仔细调查一下x86它们生成组件组, 我们使用两个函数来简单化max1max2.

max1使用条件分支if... else ...:

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2使用长期经营人... ? ... : ...:

int max2(int a, int b) {
    return a > b ? a : b;
}

在X86-64机器上GCC -S在下面生成组件。

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2由于使用教学,使用代码要少得多cmovge但真正的好处是max2不涉及分支跳跃,jmp,如果预测结果不正确,则会受到重大性能处罚。

那么,为什么有条件的行动效果更好呢?

典型x86处理器, 执行指令分为几个阶段。 大致说来, 我们用不同的硬件处理不同阶段。 因此, 我们不必等待一个指令完成才能启动一个新的指令。 这被称为管线,.

在一个分支中,下列的训导是由前面的训导决定的,所以我们不得管线。我们不是等待的,就是预告的。

在有条件迁移的情况下,有条件迁移指令的执行分为几个阶段,但早期阶段如:FetchDecode不取决于上一个指令的结果; 只有后一个阶段需要结果。 因此, 我们只能等待一个指令执行时间的一小部分。 这就是为什么有条件移动版本在预测容易时比分支慢的原因 。

这本书计算机系统:程序员的观点,第二版请查看3.6.6节。有条件移动指令整个第4章处理器建筑第5.1.1.2节,以及第5.1.1.2节,处 处 处 预测和错误预防处罚.

有时,一些现代编译者可以以更好的性能优化我们的代码组装,有时有些编译者无法(有关代码是使用视觉工作室的本地编译者 ) 。 当无法预测的情况变得如此复杂,以至于编译者无法自动优化代码时,他们知道分支和有条件的动作之间的性能差异。

其他回答

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

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

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

一般而言,现代处理器有相当长(和宽)的管道,因此许多教学可能正在飞行中。现代微处理器 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 中暗示硬件分支预测, 除了通过静态预测。 )

官方的回答是来自

  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()口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交 口交

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


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

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

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

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

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

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

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

是关于分支预测的 是什么?

  • 分支预测器是古老的改进性能的技术之一,在现代建筑中仍然具有相关性。 虽然简单的预测技术能提供快速搜索和电力效率,但它们的误判率很高。

  • 另一方面,复杂的分支预测 — — 无论是基于神经的预测还是两级分支预测的变异 — — 提供了更好的预测准确性,但是它们消耗更多的能量和复杂性会成倍增加。

  • 此外,在复杂的预测技术中,预测分支所需的时间本身非常高 — — 从2到5个周期不等 — — 这与实际分支的执行时间相当。

  • 部门预测基本上是一个优化(最小化)问题,重点是实现尽可能低的误差率、低电耗和最低资源复杂性低。

确实有三种不同的分支:

附加条件的分支- 根据运行时间条件,PC(程序表计数器)被修改为指示流中前方的地址。

后向附加条件分支- PC被修改为指令流的后向点。分支基于某种条件,例如当循环结束时的测试显示循环应该再次执行时,分支会向后到程序循环开始处。

无条件分支- 包括跳跃、程序呼叫和没有特定条件的返回。 例如, 无条件跳跃指令可能以组合语言编码为简单的“ jmp ” , 且指令流必须直接指向跳跃指令指向的目标位置, 而有条件跳跃, 代号为“ jmpne ” , 只有在对先前“ 比较” 指令中两个数值进行比较的结果显示数值不相等时, 才会改变教学流的方向。 (x86 结构使用的分段处理方案增加了额外的复杂度, 因为跳跃可以是“ 接近” (在段内) , 也可以是“ 远” (在段外) 。 每种类型都对分支预测算法有不同的影响 。

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

参考文献: