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

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


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

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

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


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


当前回答

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

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

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

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

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

其他回答

在ARARAR上,不需要分支,因为每项教学都有一个4位条件字段,该字段测试(零成本)任何(零成本)16种不同条件处理器状态登记簿中可能会出现这种情况, 如果指令的条件是假的, 则跳过指令 。 这样就不再需要短的分支, 并且不会为此算法进行分支预测 。因此,这种算法的分类版本将比ARM上未分类版本的运行慢,因为分类的间接费用增加。

这个算法的内环在ARM组装语言中 看起来像是:

MOV R0, #0   // R0 = sum = 0
MOV R1, #0   // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop  // Inner loop branch label
    LDRB R3, [R2, R1]   // R3 = data[c]
    CMP R3, #128        // compare R3 to 128
    ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1      // c++
    CMP R1, #arraySize  // compare c to arraySize
    BLT inner_loop      // Branch to inner_loop if c < arraySize

但这其实是大局的一部分:

CMP处理器状态登记册(PSR)中的状态位数总是更新,因为这是它们的目的,但大多数其他指令都不触动 PSR,除非添加一个选项S指示的后缀,规定应根据指示的结果更新PSR。就像4位条件的后缀一样,能够执行指示而不影响PSR,这个机制减少了对ARM分支的需求,也便利了硬件一级的不按订单发送,因为执行一些操作X更新状态位数后,随后(或平行)你可以做一系列其他工作,这些工作显然不应影响(或受到)状态位数的影响,然后可以测试X早先设定的状态位数状态状态。

条件测试字段和可选的“ 设定状态位” 字段可以合并, 例如 :

  • ADD R1, R2, R3表演 表演R1 = R2 + R3不更新任何状态位元 。
  • ADDGE R1, R2, R3仅在影响状态位数的先前指令导致大于或等于条件时,才执行相同的操作。
  • ADDS R1, R2, R3执行添加,然后更新N, Z, CV根据结果是否为负、零、载(未签字添加)或oVerflowed(已签署添加),在处理者地位登记册中的标记。
  • ADDSGE R1, R2, R3仅在以下情况下执行添加:GE测试是真实的, 然后根据添加结果更新状态比特 。

大多数处理器结构没有这种能力来说明是否应该为特定操作更新状态位元,这可能需要写入额外的代码来保存和随后恢复状态位元,或者可能需要额外的分支,或者可能限制处理器的运行效率:大多数 CPU 指令设置的架构的副作用之一是,在大多数指令之后强制更新状态位元,是很难分离哪些指令可以平行运行而不相互干扰的。更新状态位元具有副作用,因此对代码具有线性效果。ARM在任何指令上混合和匹配无分支条件测试的能力,在任何指令非常强大后,可以更新或不更新状态位数,对集会语言程序员和编译员来说,都极为强大,并制作非常高效的代码。

当您不需要分行时, 您可以避免冲刷管道的时间成本, 否则就是短的分支, 您也可以避免许多投机性蒸发形式的设计复杂性。 缓解最近发现的很多处理器弱点( 特例等)的最初天真效果影响 表明现代处理器的性能在多大程度上取决于复杂的投机性评估逻辑。 由于输油管很短,对分支的需求也大大减少, ARM不需要像 CISC 处理器那样依赖投机性评估。 ( 当然, 高端的ARM 实施过程包括投机性评估, 但是它只是绩效故事中的一小部分 ) 。

如果你曾经想过为什么ARM如此成功,那么这两种机制(加上另一个允许你“轮回”左转或右转的机制,任何算术操作员的两个论点之一或以零额外费用抵消内存存存取操作员的两种论点之一)的辉煌效力和互动作用是故事的一大部分,因为它们是ARM结构效率的最大来源。 1983年ARM ISA原设计师Steve Furber和Roger(现为Sophie)Wilson的聪明才智无论怎样强调都不为过。

分流收益!

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

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

每当有if-else \ switch语句中,必须评价表达式,以决定应执行哪个区块。在编译器生成的组装代码中,有条件分支分支分支插入说明。

分支指令可导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即如果表达式为虚假,程序跳过代码)if(根据某些条件,即我们案件的表达方式评价)

尽管如此,汇编者试图在对结果进行实际评估之前预测结果。if如果表达式是真实的,那么就太好了!我们得到了评估它所需的时间,并在代码中取得了进展;如果不是,我们运行错误的代码,管道被冲洗,正确的模块被运行。

可视化:

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

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

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

避免分支预测错误的一种方法是建立一个搜索表,并用数据来编制索引。 Stefan de Bruijn在答复中讨论了这一点。

但在此情况下,我们知道值在范围[0,255],我们只关心值 128。这意味着我们可以很容易地提取一小块来说明我们是否想要一个值:通过将数据移到右边的7位数,我们只剩下0位或1位数,我们只有1位数时才想要增加值。让我们把这个位数称为“决定位数 ” 。

将决定位数的 0/1 值作为索引输入一个阵列, 我们就可以生成一个代码, 无论数据是排序还是未排序, 都同样快速。 我们的代码总是会添加一个值, 但是当决定位数为 0 时, 我们将会添加一个值, 我们并不关心的地方 。 以下是代码 :

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

此代码浪费了一半的添加值, 但从未出现分支预测失败 。 随机数据比有实际的如果声明的版本要快得多 。

但在我的测试中,一个清晰的查看表比这个稍快一些, 可能是因为对一个查看表的索引比位变换略快一些。 这显示了我的代码是如何设置和使用搜索表的( 无法想象地称为“ 搜索表 ” ) 。lut代码中“ 查看表格” 。 这是 C++ 代码 :

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

在此情况下, 查看表只有256 字节, 所以它在一个缓存中非常适合, 并且非常快。 如果数据是 24 位值, 而我们只想要其中一半的话, 这个技术就不会有效... 搜索表会太大而不切实际。 另一方面, 我们可以将上面显示的两种技术结合起来: 首先将比特移开, 然后将一个查看表索引。 对于一个仅需要顶端半值的 24 位值, 我们可能会将数据右移12 位值, 并留下一个 12 位值的表格索引。 12 位表指数意味着一个有 4096 个值的表格, 这可能是实用的 。

将技术编成一个阵列,而不是使用if语句,可用于决定使用哪个指针。我看到一个实施二进制树的图书馆,而不是有两个命名指针(指针)。pLeftpRight或什么的)有长2至2的指针阵列,并使用“决定位位”技术来决定应跟随哪一个。例如,而不是:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

这个图书馆会做一些事情,比如:

i = (x < node->value);
node = node->link[i];

以下是这个代码的链接:红黑树, 永久封存

毫无疑问,我们中有些人会感兴趣的是,如何确定对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)
...

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

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

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