这是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 < 128data >= 128。因此,您应该用 a 来找到分区点脑细胞细胞研究(使用Lg(arraySize) = 15比较),然后从该点做一个直线积累。

类似的东西( 未检查 )

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

或, 略微糊涂

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

一种既快又快的方法,约近分类或未排序的解决方案为 :sum= 3137536;(假设分布真正统一,预计价值为191.5的16384个样本):-)

其他回答

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

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

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

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

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

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

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

C+++ 中经常使用的布尔操作在 C+++ 中生成了编译程序中的许多分支。 如果这些分支是内部循环,并且难以预测,它们可以大大放慢执行速度。布尔变量以8位整数和数值存储。0用于false1用于true.

布尔变量被超值确定为超值, 也就是说, 所有有布尔变量作为输入的运算符都检查输入是否有其它值, 而不是01,但将布林作为输出输出的操作器除01。这样,用布林变量作为输入的操作效率就低于必要的效率。例如:

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

此代码远非最佳。 分支分支在出现错误的情况下可能需要很长的时间。 如果可以肯定地知道, 操作家除了使用其他的值之外没有其他的值, 布尔操作可以更高效得多 。01。为什么汇编器没有做出这样的假设,其原因是,如果变量未初始化或来自未知来源,则变量可能还有其他值。如果ab已经初始化为有效值, 或者它们来自产生 Boolean 输出的运算符。 优化的代码看起来是这样 :

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

char使用代替bool以便能够使用比特顺序运算符( B) 。&|而不是 Boolean 运算符 (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1) (% 1)&&||)bitwith运算符是只使用一个时钟周期的单一指令。|工作,即使ab具有其他数值的数值01AAD 经营者(AD)&和例外或经营人(或经营人(或经营人))^)如果特有产品有其他价值,则可能得出不一致的结果,如果特有产品有其他价值,则结果可能不一致。01.

~无法用于 NST 。 相反, 您可以在已知的变量上生成布尔 。011:

bool a, b;
b = !a;

可优化到 :

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

a && b无法替换为a & b如果b是一个表达式,如果afalse ( &&将不评价b, &同样地,a || b无法替换为a | b如果b是一个表达式,如果atrue.

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

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

在大多数情况下最理想(除非预期&&表达式会生成多个分支错误) 。

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

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

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

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

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

确实有三种不同的分支:

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

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

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

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

参考文献:

毫无疑问,我们中有些人会感兴趣的是,如何确定对CPU的分支种植者有问题的代码。cachegrind使用--branch-sim=yes将外环数量减少到10 000个,并编成g++给出这些结果:

分类 :

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

未分类 :

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

向下钻入cg_annotate我们可以看到有关循环:

分类 :

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

未分类 :

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

这样可以方便地识别有问题的行 - 在未排序的版本中if (data[c] >= 128)造成164 050 007个错误预测的附带条件的分支(第1行)。Bcm),根据暗礁的分支 - 指示模型, 而它只造成10,006 在分类版本中。


或者,在Linux上,你可以使用性能计数器子系统完成同样的任务,但使用CPU计数器进行本地性能。

perf stat ./sumtest_sorted

分类 :

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

未分类 :

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

它还可以进行源代码批注,进行拆卸。

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

见见性能辅导以获取更多细节。