为什么处理排序数组比处理未排序数组更快?

这是一段C++代码,显示了一些非常奇怪的行为。

出于某种原因,对数据进行排序(之前定时区域)奇迹般地使主循环快了近六倍:


#include 
#include 
#include 

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);
// Testclock_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(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';std::cout << "sum = " << sum << '\n';}
  • 如果没有std::sort(data, data + arraySize);,代码将在11.54秒内运行。
  • 使用排序的数据,代码在1.93秒内运行。

(排序本身比遍历数组需要更多的时间,所以如果我们需要为未知数组计算它,实际上不值得这样做。


最初,我认为这可能只是一种语言或编译器异常,所以我尝试Java:

import java.util.Arrays;import java.util.Random;
public class Main{public static void main(String[] args){// Generate dataint 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 fasterArrays.sort(data);
// Testlong 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);}}

类似但不那么极端的结果。


我的第一个想法是排序将数据带入缓存,但这很愚蠢,因为数组刚刚生成。

  • 这是怎么回事?
  • 为什么处理排序数组比处理未排序数组更快?

代码总结了一些独立的术语,所以顺序应该无关紧要。


相关/后续问答关于不同/更高版本编译器和选项的相同效果:

1774124 次浏览

分支预测。

对于已排序的数组,条件data[c] >= 128对于一组值首先是false,然后对于所有以后的值变为true。这很容易预测。对于未排序的数组,您需要支付分支成本。

您是分支预测失败。


什么是分支预测?

考虑一个铁路枢纽:

显示铁路交叉口的图像图片由Mecanismo,通过维基共享资源。在CC-By-SA 3.0许可下使用。

现在为了讨论,假设这是在19世纪-在长途或无线电通信之前。

你是一个盲人司机,你听到火车来了,你不知道它应该走哪条路。你停下来问司机他们想要哪个方向。然后你适当地设置开关。

火车很重,有很多惯性,所以它们需要永远启动和减速。

有更好的方法吗?你猜火车会往哪个方向走!

  • 如果你猜对了,它会继续下去。
  • 如果你猜错了,船长会停下来,后退,并对你大喊大叫,让你打开开关。然后它可以重新启动另一条路。

如果你每次都猜对了,火车永远不会停下来。
如果你经常猜错,火车会花很多时间停下来,备份和重新启动。


考虑一个if语句:在处理器级别,它是一个分支指令:

包含if语句的编译代码截图

你是一个处理器,你看到一个分支。你不知道它会朝哪个方向发展。你该怎么办?你停止执行并等待前面的指令完成。然后你继续沿着正确的路径前进。

现代处理器很复杂,并且有很长的管道。这意味着它们需要永远“预热”和“减速”。

有更好的方法吗?你猜树枝会往哪个方向走!

  • 如果你猜对了,你继续执行。
  • 如果你猜错了,你需要刷新管道并回滚到分支。然后你可以重新启动另一条路径。

如果你每次都猜对了,执行永远不会停止。
如果你经常猜错,你会花很多时间拖延、回滚和重新启动。


这是分支预测。我承认这不是最好的类比,因为火车可以用旗子发出方向信号。但在计算机中,处理器直到最后一刻才知道分支将走向哪个方向。

你将如何战略性地猜测,以尽量减少火车必须后退并沿着另一条路行驶的次数?你看看过去的历史!如果火车99%的时间向左行驶,那么你猜是向左行驶。如果它交替行驶,那么你交替猜测。如果它每三次走一条路,你猜的是一样的…

换句话说,你试图识别一种模式并遵循它。这或多或少是分支预测器的工作方式。

大多数应用程序都有行为良好的分支。因此,现代分支预测器通常会实现>90%的命中率。但是当面对不可预测的、没有可识别模式的分支时,分支预测器实际上是无用的。

阅读更多:维基百科上的“分支预测器”文章


正如上面所暗示的,罪魁祸首是这个if语句:

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

请注意,数据在0到255之间均匀分布。当数据被排序时,大约前半部分迭代不会进入if语句。之后,它们都将进入if语句。

这对分支预测器非常友好,因为分支连续多次沿着同一个方向前进。即使是一个简单的饱和计数器也会正确预测分支,除了它切换方向后的几次迭代。

快速可视化:

T = branch takenN = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

然而,当数据完全随机时,分支预测器变得无用,因为它不能预测随机数据。因此可能会有大约50%的错误预测(不比随机猜测好)。

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, ...branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...
= TTNTTTTNTNNTTT ...   (completely random - impossible to predict)

可以做些什么?

如果编译器无法将分支优化为条件移动,如果您愿意牺牲性能的易读性,您可以尝试一些黑客攻击。

替换:

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

有:

int t = (data[c] - 128) >> 31;sum += ~t & data[c];

这消除了分支并用一些按位操作替换它。

(请注意,此hack并不严格等同于原始的if语句。但在这种情况下,它对data[]的所有输入值都有效。)

基准:Core i7 920@3.5 GHz

C++-Visual Studio 2010-x64发行版

场景时间(秒)
分支-随机数据11.777
分支-排序数据2.352
无分支-随机数据2.564
无分支-排序数据2.587

Java-NetBeans 7.1.1 JDK 7-x64

场景时间(秒)
分支-随机数据10.93293813
分支-排序数据5.643797077
无分支-随机数据3.113581453
无分支-排序数据3.186068823

意见:

  • 与分支机构:排序数据和未排序数据之间存在巨大差异。
  • 关于Hack:排序数据和未排序数据之间没有区别。
  • 在C++情况下,当数据被排序时,黑客实际上比分支慢一点。

一般的经验法则是避免关键循环中依赖数据的分支(如本例所示)。


更新时间:

  • x64上带有-O3-ftree-vectorize的GCC 4.6.1能够生成条件移动,因此排序和未排序数据之间没有区别-两者都很快。

    (或者有点快:对于已经排序的情况,cmov可能会更慢,特别是如果GCC将其放在关键路径上而不仅仅是add,特别是在Broadwell之前的Intel上,其中cmov有2个周期延迟:gcc优化标志-O3使代码比-O2慢

  • VC++2010即使在/Ox下也无法为该分支生成条件移动。

  • 英特尔C++编译器(ICC)11做了一些神奇的事情。它交换两个循环,从而将不可预测的分支提升到外部循环。它不仅不受错误预测的影响,而且比VC++和GCC可以生成的速度快两倍!换句话说,ICC利用了测试循环来击败基准…

  • 如果您给Intel编译器无分支代码,它只是直接向量化它…并且与分支(使用循环交换)一样快。

这表明,即使是成熟的现代编译器在优化代码的能力上也会有很大的差异。

当数据排序时,性能大幅提高的原因是删除了分支预测惩罚,正如神秘的答案中精彩解释的那样。

现在,如果我们看一下代码

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

我们可以发现这个特定的if... else...分支的含义是在满足条件时添加一些东西。这种类型的分支可以很容易地转换为条件移动语句,该语句将被编译成条件移动指令:cmovl,在x86系统中。该分支因此潜在的分支预测惩罚被删除。

C中,因此在C++中,将直接(无需任何优化)编译为x86中的条件移动指令的语句是三元运算符... ? ... : ...。所以我们将上面的语句重写为等效的语句:

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

在保持易读性的同时,我们可以检查加速因子。

在Intel酷睿i7-2600K@3.4 GHz和Visual Studio 2010发布模式下,基准测试为:

x86

场景时间(秒)
分支-随机数据8.885
分支-排序数据1.528
无分支-随机数据3.716
无分支-排序数据3.71

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

max2使用三元运算符... ? ... : ...

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

在x86-64机器上,GCC -S生成下面的程序集。

:max1movl    %edi, -4(%rbp)movl    %esi, -8(%rbp)movl    -4(%rbp), %eaxcmpl    -8(%rbp), %eaxjle     .L2movl    -4(%rbp), %eaxmovl    %eax, -12(%rbp)jmp     .L4.L2:movl    -8(%rbp), %eaxmovl    %eax, -12(%rbp).L4:movl    -12(%rbp), %eaxleaveret
:max2movl    %edi, -4(%rbp)movl    %esi, -8(%rbp)movl    -4(%rbp), %eaxcmpl    %eax, -8(%rbp)cmovge  -8(%rbp), %eaxleaveret

由于使用了指令cmovgemax2使用的代码要少得多。但真正的收益是max2不涉及分支跳转,jmp,如果预测结果不对,分支跳转将有显著的性能损失。

那么为什么有条件的移动表现更好呢?

在典型的x86处理器中,一条指令的执行分为几个阶段。粗略地说,我们有不同的硬件来处理不同的阶段。所以我们不必等待一条指令完成再开始一条新指令。这称为流水线

在分支情况下,以下指令由前一条指令确定,因此我们不能进行流水线。我们必须等待或预测。

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

本书计算机系统:程序员的观点,第二版详细解释了这一点。您可以查看第3.6.6节的条件移动指令,整个第4章的处理器架构,以及第5.11.2节的分支预测与误判惩罚特殊处理。

有时候,一些现代编译器可以优化我们的代码,使其具有更好的性能,有时候有些编译器不能(有问题的代码使用的是Visual Studio的本机编译器)。在不可预测时了解分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化时编写具有更好性能的代码。

如果您对可以对此代码进行更多优化感到好奇,请考虑以下内容:

从原始循环开始:

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

这比以前快了10万倍。

毫无疑问,我们中的一些人会对识别CPU分支预测器有问题的代码的方法感兴趣。Valgrind工具cachegrind有一个分支预测器模拟器,通过使用--branch-sim=yes标志启用。在这个问题中的示例上运行它,外环数量减少到10000并使用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 Bim10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i).      .  .   .      {.      .  .   .          // primary loop327,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 Bim10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i).           .  .   .      {.           .  .   .          // primary loop327,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)行在cachegrind的分支预测器模型下导致164,050,007个错误预测的条件分支(Bcm),而在排序版本中仅导致10,006个。


或者,在Linux,您可以使用性能计数器子系统来完成相同的任务,但使用CPU计数器的本机性能。

perf stat ./sumtest_sorted

排序:

 Performance counter stats for './sumtest_sorted':
11808.095776 task-clock                #    0.998 CPUs utilized1,062 context-switches          #    0.090 K/sec14 CPU-migrations            #    0.001 K/sec337 page-faults               #    0.029 K/sec26,487,882,764 cycles                    #    2.243 GHz41,025,654,322 instructions              #    1.55  insns per cycle6,558,871,379 branches                  #  555.455 M/sec567,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 utilized2,584 context-switches          #    0.089 K/sec18 CPU-migrations            #    0.001 K/sec335 page-faults               #    0.012 K/sec65,076,127,595 cycles                    #    2.253 GHz41,032,528,741 instructions              #    0.63  insns per cycle6,560,579,013 branches                  #  227.183 M/sec1,646,394,749 branch-misses             #   25.10% of all branches
28.935500947 seconds time elapsed

它还可以使用反汇编进行源代码注释。

perf record -e branch-misses ./sumtest_unsortedperf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted------------------------------------------------...:                      sum += data[c];0.00 :        400a1a:       mov    -0x14(%rbp),%eax39.97 :        400a1d:       mov    %eax,%eax5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax4.60 :        400a26:       cltq0.00 :        400a28:       add    %rax,-0x30(%rbp)...

查看的性能教程了解更多详情。

我用MATLAB2011b我的MacBook Pro(Intel i7,64位,2.4 GHz)尝试了相同的代码,用于以下MATLAB代码:

% Processing time with Sorted data vs unsorted data%==========================================================================% Generate dataarraySize = 32768sum = 0;% Generate random integer data from range 0 to 255data = randi(256, arraySize, 1);

%Sort the datadata1= sort(data); % data1= data  when no sorting done

%Start a stopwatch timer to measure the execution timetic;
for i=1:100000
for j=1:arraySize
if data1(j)>=128sum=sum + data1(j);endendend
toc;
ExeTimeWithSorting = toc - tic;

上述MATLAB代码的结果如下:

  a: Elapsed time (without sorting) = 3479.880861 seconds.b: Elapsed time (with sorting ) = 2377.873098 seconds.

我得到的@GManNickG中的C代码的结果:

  a: Elapsed time (without sorting) = 19.8761 sec.b: Elapsed time (with sorting ) = 7.37778 sec.

基于此,看起来MATLAB几乎比没有排序的C实现慢175次,排序慢350次。换句话说,(分支预测的)效果对于MATLAB实现是1.46x,对于C实现是2.7x

由于数组排序时数据分布在0到255之间,因此前半部分迭代不会输入if语句(if语句在下面共享)。

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

问题是:是什么使得上述语句在某些情况下不执行,例如在排序数据的情况下?“分支预测器”来了。分支预测器是一种数字电路,在确定之前试图猜测分支(例如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

”真假模式可以使if语句比“”模式慢六倍!当然,哪种模式是好的,哪种模式是坏的取决于编译器生成的确切指令和特定的处理器。

所以分支预测对性能的影响是毋庸置疑的!

我刚刚读了这个问题及其答案,我觉得缺少答案。

消除分支预测的一种常见方法,我发现在托管语言中特别好的工作是表查找而不是使用分支(尽管我没有在这种情况下测试它)。

这种方法通常适用于以下情况:

  1. 它是一个小表,很可能被缓存在处理器中,并且
  2. 您正在一个非常紧密的循环中运行事物,并且/或者处理器可以预加载数据。

背景和原因

从处理器的角度来看,你的内存很慢。为了弥补速度上的差异,处理器内置了几个缓存(L1/L2缓存)。所以想象一下,你正在做很好的计算,并发现你需要一块内存。处理器将执行其“加载”操作,并将这块内存加载到缓存中,然后使用缓存来完成其余的计算。因为内存相对较慢,这种“加载”会减慢你的程序。

与分支预测一样,这在Pentium处理器中进行了优化:处理器预测它需要加载一段数据并尝试在操作实际命中缓存之前将其加载到缓存中。正如我们已经看到的,分支预测有时会出现可怕的错误——在最坏的情况下,您需要返回并实际等待内存加载,这将花费很长时间(换句话说:失败的分支预测很糟糕,分支预测失败后的内存负载非常可怕!)。

幸运的是,如果内存访问模式是可预测的,处理器会将其加载到快速缓存中,一切都很好。

我们需要知道的第一件事是什么是?虽然更小通常更好,但经验法则是坚持使用大小<=4096字节的查找表。作为上限:如果您的查找表大于64K可能值得重新考虑。

构造一个表

所以我们已经弄清楚了我们可以创建一个小表。接下来要做的就是安装一个查找函数。查找函数通常是使用几个基本整数操作(以及,或,异或,移位,添加,删除以及可能的乘法)的小函数。您希望将您的输入由查找函数转换为表中的某种“唯一键”,然后简单地为您提供您想要它做的所有工作的答案。

在这种情况下:>=128意味着我们可以保留值,<128意味着我们可以摆脱它。最简单的方法是使用AND:如果我们保留它,我们用7FFFFFFF与它;如果我们想摆脱它,我们用0与它。还要注意128是2的幂-所以我们可以继续制作一个包含32768/128整数的表,并用一个零和很多7FFFFFFFF填充它。

管理语言

您可能想知道为什么这在托管语言中运行良好。毕竟,托管语言使用分支检查数组的边界以确保您不会搞砸…

嗯,不完全是…:-)

在消除托管语言的这个分支方面已经做了相当多的工作。例如:

for (int i = 0; i < array.Length; ++i){// Use array[i]}

在这种情况下,编译器很明显边界条件永远不会被命中。至少Microsoft即时编译器(但我希望Java做类似的事情)会注意到这一点并完全删除检查。哇,这意味着没有分支。类似地,它会处理其他明显的情况。

如果您在托管语言中遇到查找问题-关键是在查找函数中添加& 0x[something]FFF以使边界检查可预测-并观察它的速度。

本案的结果

// Generate dataint arraySize = 32768;int[] data = new int[arraySize];
Random random = new Random(0);for (int c = 0; c < arraySize; ++c){data[c] = random.Next(256);}
/*To keep the spirit of the code intact, I'll make a separate lookup table(I assume we cannot modify 'data' or the number of loops)*/
int[] lookup = new int[256];
for (int c = 0; c < 256; ++c){lookup[c] = (c >= 128) ? c : 0;}
// TestDateTime startTime = System.DateTime.Now;long sum = 0;
for (int i = 0; i < 100000; ++i){// Primary loopfor (int j = 0; j < arraySize; ++j){/* Here you basically want to use simple operations - so norandom branches, but things like &, |, *, -, +, etc. are fine. */sum += lookup[data[j]];}}
DateTime endTime = System.DateTime.Now;Console.WriteLine(endTime - startTime);Console.WriteLine("sum = " + sum);Console.ReadLine();

避免分支预测错误的一种方法是构建查找表,并使用数据对其进行索引。Stefan de Bruijn在他的回答中讨论了这一点。

但在这种情况下,我们知道值在[0,255]范围内,我们只关心值>=128。这意味着我们可以轻松提取一个位来告诉我们是否需要一个值:通过将数据向右移动7位,我们剩下0位或1位,我们只有在有1位时才想要添加值。让我们将这个位称为“决策位”。

通过使用决策位的0/1值作为数组的索引,我们可以使代码无论数据是否排序都同样快。我们的代码总是会添加一个值,但是当决策位为0时,我们会在我们不关心的地方添加值。这是代码:

// Testclock_t start = clock();long long a[] = {0, 0};long long sum;
for (unsigned i = 0; i < 100000; ++i){// Primary loopfor (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];

这段代码浪费了一半的添加,但从来没有分支预测失败。它在随机数据上比带有实际if语句的版本快得多。

但是在我的测试中,显式查找表比这稍微快一点,可能是因为索引到查找表比位移动稍微快一点。这显示了我的代码是如何设置和使用查找表的(在代码中对“LookUp Table”毫无想象力地称为lut)。这是C++代码:

// Declare and then fill in the lookup tableint lut[256];for (unsigned c = 0; c < 256; ++c)lut[c] = (c >= 128) ? c : 0;
// Use the lookup table after it is builtfor (unsigned i = 0; i < 100000; ++i){// Primary loopfor (unsigned c = 0; c < arraySize; ++c){sum += lut[data[c]];}}

在这种情况下,查找表只有256字节,所以它非常适合缓存,而且速度很快。如果数据是24位值,这种技术不会很好地工作,而且我们只想要其中的一半……查找表会太大而不实用。另一方面,我们可以结合上面显示的两种技术:首先移动位,然后索引查找表。对于一个24位值,我们只想要上半部分值,我们可能会将数据向右移动12位,并留下12位值作为表索引。12位表索引意味着一个包含4096个值的表,这可能很实用。

索引到数组的技术,而不是使用if语句,可用于决定使用哪个指针。我看到一个实现二叉树的库,而不是有两个命名指针(pLeftpRight或其他什么),而是有一个长度为2的指针数组,并使用“决策位”技术来决定遵循哪个。例如,而不是:

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

这个库会做这样的事情:

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

以下是此代码的链接:红黑树永远困惑

在排序的情况下,您可以比依赖成功的分支预测或任何无分支比较技巧做得更好:完全删除分支。

事实上,数组被划分在一个与data < 128相邻的区域中,另一个与data >= 128相邻的区域中。所以你应该用二分搜索找到分区点(使用Lg(arraySize) = 15比较),然后从该点进行直接累加。

就像(未检查的)

int i= 0, j, k= arraySize;while (i < k){j= (i + k) >> 1;if (data[j] >= 128)k= j;elsei= 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;(假设真正均匀分布,16384个样本具有期望值191.5):-)

上述行为的发生是因为分支预测。

要了解分支预测,必须首先了解指令流水线。

运行一条指令的步骤可以与运行上一条和下一条指令的步骤序列重叠,以便不同的步骤可以并行并发执行。这种技术称为指令流水线,用于提高现代处理器的吞吐量。为了更好地理解这一点,请参阅这个维基百科上的例子

一般来说,现代处理器具有相当长(和宽)的流水线,因此许多指令可以在飞行中。参见现代微处理器一个90分钟的指南!它从介绍基本的有序流水线开始,然后从那里开始。

但为了方便让我们考虑一个仅包含这4个步骤的简单有序管道。
(类似于经典5级RISC,但省略了一个单独的MEM阶段。)

  1. IF--从内存中获取指令
  2. ID--解码指令
  3. EX--执行指令
  4. WB--写回CPU寄存器

4级流水线一般为2个指令。
一般4级流水线

回到上面的问题,让我们考虑以下说明:

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

如果没有分支预测,将发生以下情况:

要执行指令B或指令C,处理器必须等待(失速)直到指令A离开流水线中的EX阶段,因为决定转到指令B或指令C取决于指令A的结果(即从哪里获取下一个)。

没有预测:当#0条件为真时:在此处输入图片描述

没有预测:当#0条件为假时:在此处输入图片描述

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

什么是分支预测?

分支预测器将尝试在确定之前猜测分支(一个if-then-ther结构)将走哪条路。它不会等待指令A到达管道的EX阶段,但它会猜测决定并转到该指令(在我们的例子中是B或C)。

如果猜测正确,管道看起来像这样:在此处输入图片描述

如果后来检测到猜测是错误的,那么部分执行的指令将被丢弃,管道以正确的分支重新开始,从而产生延迟。在分支错误预测的情况下浪费的时间等于管道中从获取阶段到执行阶段的级数。现代微处理器往往有相当长的管道,因此错误预测延迟在10到20个时钟周期之间。管道越长,就越需要一个好的分支预测器

在OP的代码中,第一次条件时,分支预测器没有任何信息可以进行预测,所以第一次它会随机选择下一条指令。(或者回退到静态预测,典型的是前向不取,后向取)。稍后在for循环中,它可以根据历史记录进行预测。对于按升序排序的数组,有三种可能性:

  1. 所有元素都小于128
  2. 所有元素都大于128
  3. 一些开始的新元素小于128,后来它变得大于128

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

因此,在第一种情况下,它将始终采用真正的分支,因为历史上它的所有预测都是正确的。在第二种情况下,最初它会预测错误,但经过几次迭代,它会预测正确。在第3种情况下,它最初将正确预测,直到元素小于128。之后它将失败一段时间,并在历史上看到分支预测失败时纠正自己。

在所有这些情况下,失败的次数太少,因此,只有几次需要丢弃部分执行的指令并使用正确的分支重新开始,从而减少CPU周期。

但在随机未排序数组的情况下,预测将需要丢弃部分执行的指令,并在大部分时间使用正确的分支重新开始,并导致与排序数组相比更多的CPU周期。


进一步阅读:

  • 现代微处理器90分钟指南!
  • Dan Luu关于分支预测的文章(涵盖较旧的分支预测器,而不是现代的IT-TAGE或感知器)
  • https://en.wikipedia.org/wiki/Branch_predictor
  • 分支预测和解释器的性能-不要相信民间传说-2015年的论文,展示了英特尔的Haswell在预测Python解释器主循环的间接分支方面的表现(由于非简单模式,历史上有问题),与不使用IT-TAGE的早期CPU相比。(不过,它们对这种完全随机的情况没有帮助。当源代码编译为分支asm时,Skylake CPU上循环内的if仍然有50%的误判率。)
  • 较新的Intel处理器上的静态分支预测-当运行没有动态预测可用的分支指令时,CPU实际上做了什么。从历史上看,前向不采取(如ifbreak),后向采取(如循环)一直被使用,因为它总比什么都没有好。布置代码以使快速路径/常见情况最小化采取的分支对于I-缓存密度以及静态预测都有好处,所以编译器已经这样做了。(这是C源代码中likely/unlikely中的真实效果提示,实际上并没有暗示大多数CPU中的硬件分支预测,除非通过静态预测。)

在同一行中(我认为没有任何答案强调这一点),值得一提的是,有时(特别是在性能很重要的软件中——比如在Linux内核中),你可以找到一些if语句,如下所示:

if (likely( everything_is_ok )){/* Do something */}

或类似:

if (unlikely(very_improbable_condition)){/* Do something */}

likely()unlikely()实际上都是宏,它们是通过使用类似于GCC__builtin_expect的东西来定义的,以帮助编译器插入预测代码,以根据用户提供的信息支持条件。GCC支持其他内置程序,这些内置程序可以改变正在运行的程序的行为或发出低级指令,如清除缓存等。参见这个留档,了解可用的GCC内置程序。

通常这种优化主要出现在硬实时应用程序或嵌入式系统中,在这些地方执行时间很重要,而且至关重要。例如,如果你正在检查一些只发生1/10000000次的错误条件,那么为什么不通知编译器呢?这样,默认情况下,分支预测会假设条件为假。

C++中常用的布尔运算在编译程序中产生许多分支。如果这些分支位于循环内部并且难以预测,它们会显着减慢执行速度。布尔变量存储为8位整数,false的值为0true的值为1

布尔变量是过定的,因为所有将布尔变量作为输入的操作符都检查输入是否有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已经初始化为有效值,或者它们来自产生布尔输出的运算符,上述代码可以被优化。优化的代码看起来像这样:

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

使用char而不是bool是为了可以使用按位运算符(&|)而不是布尔运算符(&&||)。按位运算符是只需要一个时钟周期的单个指令。即使ab0bool0以外的值,OR运算符(|)也可以工作。如果操作数有0bool0以外的值,AND运算符(&)和EXCLUSIVE OR运算符(bool2)可能会给出不一致的结果。

~不能用于not。相反,您可以通过使用1对已知为01的变量进行XOR来对其进行布尔非:

bool a, b;b = !a;

可以优化为:

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

如果afalse,则b是不应该计算的表达式,则a && b不能替换为a & b&&不会计算b&会)。同样,如果aa & b2,则b是不应该计算的表达式,则a || b不能替换为a | b

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

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

在大多数情况下是最佳的(除非您期望&&表达式生成许多分支错误预测)。

官方的答案是

  1. 英特尔-避免分支错误预测的代价
  2. 英特尔-防止误判的分支和循环重组
  3. 科学论文-分支预测计算机体系结构
  4. 书籍:J. L. Hennessy,D. A. Patterson:计算机架构:定量方法
  5. 科学出版物上的文章:T. Y. Yeh,Y. N. Patt做了很多关于分支预测的文章。

您还可以从这个可爱的中看到为什么分支预测器会感到困惑。

2位状态图

原始代码中的每个元素都是一个随机值

data[c] = std::rand() % 256;

所以预测器将改变侧面作为std::rand()打击。

另一方面,一旦它被排序,预测器将首先进入强烈不采取的状态,当值变为高值时,预测器将在三次运行中从强烈不采取到强烈采取。


这个问题已经被很好地回答过很多次了。我仍然想提请小组注意另一个有趣的分析。

最近,这个例子(稍微修改了一下)也被用作演示如何在Windows上在程序本身中分析一段代码的一种方式。在此过程中,作者还展示了如何使用结果来确定代码在排序和未排序的情况下花费大部分时间的位置。最后,这篇文章还展示了如何使用HAL(硬件抽象层)的一个鲜为人知的特性来确定在未排序的情况下发生了多少分支错误预测。

链接在这里:自我剖析的示范

那是肯定的!……

分支预测使得逻辑运行得更慢,因为在你的代码中发生了切换!就像你要走一条直道或一条有很多转弯的街道,当然直道会更快完成!…

如果数组已排序,你的条件在第一步为false:data[c] >= 128,然后在整个街道尽头成为真值。这就是你更快地到达逻辑末尾的方式。另一方面,使用未排序的数组,你需要大量的翻转和处理,这肯定会使你的代码运行得更慢…

看看下面我为你创建的图片。哪条街会更快完成?

分支预测

所以在编程上,分支预测导致进程变慢…

同样在最后,很高兴知道我们有两种分支预测,每种预测都会对您的代码产生不同的影响:

1.静态

2.动态

分支预测

微处理器第一次使用静态分支预测遇到条件分支,动态分支预测用于成功执行条件分支代码。

为了有效地编写代码以利用这些优势规则,在编写如果-否则开关语句时,检查最首先是常见病例,然后逐步下降到最不常见的病例。循环不一定需要任何特殊的代码顺序静态分支预测,仅作为循环迭代器的条件正常使用

分支预测增益!

重要的是要理解分支错误预测不会减慢程序速度。错过预测的代价就像分支预测不存在,你等待表达式的评估来决定运行什么代码(下一段将进一步解释)。

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

只要有if-else\switch语句,就必须评估表达式以确定应该执行哪个块。在编译器生成的汇编代码中,插入了条件分支指令。

分支指令可能导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即如果表达式为false,则程序跳过if块的代码),具体取决于某些条件,这是我们的表达式评估。

话虽如此,编译器试图在实际评估之前预测结果。它将从if块中获取指令,如果表达式为真,那太好了!我们获得了评估它所需的时间并在代码中取得了进展;如果不是,那么我们运行了错误的代码,管道被刷新,运行正确的块。

可视化:

假设你需要选择路线1或路线2。等待你的伴侣检查地图,你已经在##停了下来等待,或者你可以选择路线1,如果你幸运的话(路线1是正确的路线),那么太好了,你不必等待你的伴侣检查地图(你节省了他检查地图的时间),否则你就会回头。

虽然冲洗管道非常快,但现在冒这个险是值得的。预测排序数据或变化缓慢的数据总是比预测快速变化更容易和更好。

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

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

  • 分支预测器是一种古老的性能改进技术,在现代架构中仍然存在相关性。虽然简单的预测技术提供了快速查找和电源效率,但它们存在很高的误判率。

  • 另一方面,复杂的分支预测——基于神经网络的或两级分支预测的变体——提供了更好的预测精度,但它们消耗更多的功率,复杂性呈指数级增长。

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

  • 分支预测本质上是一个优化(最小化)问题,重点是以最少的资源实现尽可能低的错误率、低功耗和低复杂性。

实际上有三种不同类型的分支:

向前条件分支-基于运行时条件,PC(程序计数器)被更改为指向指令流中的地址转发。

向后条件分支-PC被更改为在指令流中向后指向。分支基于某些条件,例如当循环结束时的测试指出应该再次执行循环时,向后分支到程序循环的开始。

无条件分支-这包括没有特定条件的跳转、过程调用和返回。例如,无条件跳转指令可能在汇编语言中被编码为简单的“jmp”,指令流必须立即被定向到跳转指令指向的目标位置,而可能被编码为“jmpne”的条件跳转只有在之前“比较”指令中两个值的比较结果显示值不相等时才会重定向指令流。(x86架构使用的分段寻址方案增加了额外的复杂性,因为跳转可以是“近”(段内)或“远”(段外)。每种类型对分支预测算法有不同的影响。)

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

参考文献:

正如其他人已经提到的,神秘背后的是分支预测器

我不是想添加什么,而是用另一种方式解释这个概念。维基上有一个简洁的介绍,其中包含文本和图表。我确实喜欢下面的解释,它使用图表直观地阐述了分支预测器。

在计算机体系结构中,分支预测器是试图猜测分支(例如如果-然后-否则结构)将在确定之前执行分支预测器的目的是改善指令流水线。分支预测器在在许多现代流水线中实现高效性能微处理器架构,例如x86。

双向分支通常用条件跳转实现指令。条件跳转可以是“未采取”并继续用紧随其后的第一个代码分支执行在条件跳转之后,或者它可以“采取”并跳转到程序内存中第二个代码分支所在的不同位置存储。不知道是否会有条件跳转采取或不采取,直到条件已经计算和条件跳转已通过指令中的执行阶段管道(见图1)。

图1

基于所描述的场景,我编写了一个动画演示来展示在不同情况下如何在管道中执行指令。

  1. 没有分支预测器。

如果没有分支预测,处理器将不得不等待条件跳转指令已通过执行阶段之前下一条指令可以进入管道中的获取阶段。

该示例包含三条指令,第一条是条件跳转指令。后两条指令可以进入流水线,直到执行条件跳转指令。

没有分支预测器

完成3条指令需要9个时钟周期。

  1. 使用分支预测器,不要进行条件跳转。让我们假设预测是没有进行条件跳转。

在此处输入图片描述

完成3条指令需要7个时钟周期。

  1. 使用分支预测器并进行条件跳转。让我们假设预测是没有进行条件跳转。

在此处输入图片描述

完成3条指令需要9个时钟周期。

在分支错误预测的情况下浪费的时间等于从获取阶段到获取阶段的管道中的级数执行阶段。现代微处理器往往具有相当长的流水线,使得错误预测延迟在10到20个时钟之间因此,使管道更长会增加对更高级的分支预测器。

如您所见,似乎我们没有理由不使用分支预测器。

这是一个相当简单的演示,阐明了分支预测器的基本部分。如果这些GIF很烦人,请随时从答案中删除它们,访问者也可以从预测模型获得实时演示源代码

除了分支预测可能会减慢您的速度之外,排序数组还有另一个优势:

你可以有一个停止条件,而不仅仅是检查值,这样你只循环相关数据,忽略其余的。
分支预测只会错过一次。

 // sort backwards (higher values first), may be in some other part of the codestd::sort(data, data + arraySize, std::greater<int>());
for (unsigned c = 0; c < arraySize; ++c) {if (data[c] < 128) {break;}sum += data[c];}

由于一种称为分支预测的现象,排序数组的处理速度比未排序数组快。

分支预测器是一种数字电路(在计算机体系结构中),试图预测分支的走向,改善指令流水线中的流程。电路/计算机预测下一步并执行它。

做出错误的预测会导致返回上一步,并执行另一个预测。假设预测是正确的,代码将继续下一步。错误的预测导致重复相同的步骤,直到正确的预测发生。

你的问题的答案很简单。

在未排序的数组中,计算机进行多次预测,导致错误的可能性增加。然而,在排序数组中,计算机进行更少的预测,减少了错误的机会。做更多的预测需要更多的时间。

排序数组:直线

____________________________________________________________________________________- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未排序数组:曲线路

______   ________|     |__|

分支预测:猜测/预测哪条路是直的,并在不检查的情况下跟随它

___________________________________________ Straight road|_________________________________________|Longer road

虽然两条路都到达同一个目的地,但直路较短,另一条较长。如果你错误地选择了另一条路,就没有回头路了,所以如果你选择了更长的路,你会浪费一些额外的时间。这与计算机中发生的情况相似,我希望这有助于你更好地理解。


我还想引用评论中的@Simon_Weaver

它并没有做出更少的预测——它做出了更少的不正确的预测。

在ARM上,不需要分支,因为每条指令都有一个4位条件字段,它(以零成本)测试处理器状态寄存器中可能出现的16种不同的条件中的任何一个,如果指令上的条件为假,则跳过该指令。这消除了对短分支的需要,并且该算法不会出现分支预测命中。因此,由于排序的额外开销,该算法的排序版本将比ARM上的未排序版本运行得慢。

在ARM汇编语言中,此算法的内部循环如下所示:

MOV R0, #0   // R0 = sum = 0MOV R1, #0   // R1 = c = 0ADR R2, data // R2 = addr of data array (put this instruction outside outer loop).inner_loop  // Inner loop branch labelLDRB R3, [R2, R1]   // R3 = data[c]CMP R3, #128        // compare R3 to 128ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!ADD R1, R1, #1      // c++CMP R1, #arraySize  // compare c to arraySizeBLT 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执行加法,然后根据结果是负、零、携带(对于无符号加法)还是过流(对于有符号加法)更新处理器状态寄存器中的NZCV标志。
  • ADDSGE R1, R2, R3仅在GE测试为真时执行加法,然后根据加法的结果更新状态位。

大多数处理器架构没有这种能力来指定是否应该为给定操作更新状态位,这可能需要编写额外的代码来保存和稍后恢复状态位,或者可能需要额外的分支,或者可能会限制处理器的无序执行效率:大多数CPU指令集架构在大多数指令之后强制更新状态位的副作用之一是更难梳理哪些指令可以并行运行而不相互干扰。更新状态位有副作用,因此对代码有线性化效应。对于汇编语言程序员和编译器来说,ARM能够混合和匹配任何指令的无分支条件测试以及在任何指令之后更新或不更新状态位的选项,这是非常强大的,并产生非常有效的代码。

当不需要分支时,就可以避免为原本会很短的分支冲洗流水线的时间成本,也可以避免许多形式的推测评估的设计复杂性。许多最近发现的处理器漏洞(Spectre等)的缓解措施最初天真的实施对性能的影响表明,现代处理器的性能有多依赖复杂的推测评估逻辑。由于流水线很短,分支的需求大大减少,ARM不需要像CISC处理器那样依赖推测评估。(当然,高端ARM实现确实包括推测评估,但这只是性能故事的一小部分。)

如果你想知道为什么ARM如此成功,那么这两种机制的卓越有效性和相互作用(与另一种机制相结合,可以让你以零额外成本向左或向右“桶移”任何算术运算符或偏移内存访问运算符的两个参数之一)就是故事的重要组成部分,因为它们是ARM架构效率的一些最大来源。1983年ARM ISA的原始设计者Steve Furber和Roger(现在的Sophie)Wilson的才华怎么强调都不为过。

其他答案认为需要对数据进行排序的假设是不正确的。

下面的代码不会对整个数组进行排序,而只对其中的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 arrayfor (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;}

这也“证明”了它与排序顺序等任何算法问题无关,它确实是分支预测。

Bjarne Stroustrup对这个问题的回答:

这听起来像是面试问题。是真的吗?你怎么知道?在不做一些测量的情况下回答有关效率的问题是一个坏主意,所以知道如何测量很重要。

所以,我尝试了一百万个整数的向量,得到了:

Already sorted    32995 millisecondsShuffled          125944 milliseconds
Already sorted    18610 millisecondsShuffled          133304 milliseconds
Already sorted    17942 millisecondsShuffled          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]) …”或等效的。对于测试总是为真的排序序列,而对于随机序列,选择的分支随机变化。

另一个原因是,当向量已经排序时,我们永远不需要将元素移动到正确的位置。这些小细节的影响是我们看到的五或六的因子。

快速排序(以及一般的排序)是一项复杂的研究,吸引了一些计算机科学领域最伟大的头脑。一个好的排序函数是选择一个好的算法和在其实现中关注硬件性能的结果。

如果您想编写高效的代码,您需要了解一些机器架构。

这个问题源于CPU上的分支预测模型。我建议阅读这篇论文:

通过多分支预测和分支地址缓存提高指令获取率(但是现在真正的CPU仍然不会在每个时钟周期内进行多次获取分支预测,除了Haswell和更高版本有效地展开其循环缓冲区中的微小循环。现代CPU可以预测多个未获取的分支,以利用它们在大型连续块中的获取。)

当您对元素进行排序时,分支预测可以轻松地正确预测,除了在边界处,让指令有效地流经CPU管道,而无需倒带并在错误预测时采用正确的路径。

快速简单理解的答案(阅读其他内容了解更多细节)

这个概念被称为分支预测

分支预测是一种优化技术,它在代码确定之前预测代码将走的路径。这很重要,因为在代码执行期间,机器会预取多个代码语句并将它们存储在管道中。

问题出现在条件分支中,其中有两个可能的路径或代码部分可以执行。

当预测为真时,优化技术就出现了。

当预测为假时,以简单的方式解释它,存储在管道中的代码语句被证明是错误的,实际代码必须完全重新加载,这会占用大量时间。

正如常识所表明的那样,对排序的东西的预测比对未排序的东西的预测要准确得多。

分支预测可视化:

已排序
sorted未排序未排序

这是一个分支预测失败。你不需要对数组进行排序,但你只需要用值128对其进行分区。排序是n*log(n),而分区只是线性的。基本上,它只是快速排序分区步骤的一次运行,支点选择为128。不幸的是,在C++只有nth_element函数,它按位置分区,而不是按值分区。

这个问题的答案是它自动向量化。像往常一样,编译器不会选择完美的策略。(尽管GCC可能是SSE2或SSE4的最佳选择。)