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

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


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

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

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


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


当前回答

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

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

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

其他回答

在对数据进行分类时,业绩显著改善的原因是,如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节,处 处 处 预测和错误预防处罚.

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

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

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

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

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

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

这个问题已经回答过很多次了。我还是想提醒大家注意另一个有趣的分析。

最近,这个例子(稍作修改)也被用来演示如何在 Windows 上显示一个代码在程序本身中被剖析。 顺便提一下, 作者还展示了如何使用结果来确定代码的大部分时间用于分解和未排序的案例中。 最后, 文章还展示了如何使用HAL( Hardware Empaction Develople) 的一个鲜为人知的特征来确定未分类案例中的分支错误发生多少。

链接在此 :自我辩护示范

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

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

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

这是肯定的!

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

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

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

Branch Prediction

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

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

1. 静态

2. 动态

Branch Prediction

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

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