PROSAGA码农传奇-netbeans-为什么处理排序数组比处理未排序数组更快？

0# Hey ou | 2019-08-31 10-32

1# 你咖喱人biss嗷 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    虽然这里的大多数答案都能很好地解释差异，但我想采取更简单的方法。
  
  
    数据集上最常见的操作，如数据的删除，添加和分组等
    的
      需要搜索数据集
    </强>
     （例如：要删除值，您必须先找到它）。
  
  
    有两种主要（基本）搜索算法。
  
  <OL>
    <LI>
      线性搜索
    </LI>
    <LI>
      二进制搜索
    </LI>
  </醇>
  
    该
    的
      线性搜索
    </强>
     适用于已排序和未排序的数据集，但它的作用
    的
      最坏情况的复杂性是O（n）
    </强>
     （最坏的情况是算法执行任务所需的最长时间。）
  
  
    而
    的
      二进制搜索
    </强>
     仅适用于已排序的数据集及其
    的
      最坏情况的复杂性是O（logN）
    </强>
    。
  
  
    <a href="https://i.stack.imgur.com/8xb3r.png" rel="nofollow noreferrer">
      <img src =“https://i.stack.imgur.com/8xb3r.png”alt =“在此处输入图片说明”/>
    </A>
  
  
    供参考：Log 2000 - ＆gt; 10.96
  
  
    所以在最坏的情况下参考，
    的
      
        我们有一个算法，它在2000毫秒内搜索一个查询，而算法在11毫秒内完成相同的算法
      
    </强>
    。
  
  
    在现实世界中，涉及100个TB数据并且每秒生成多个查询（只是说在StackOverflow上搜索问题），我们无法承担采用线性时间的方法。
  
  
    因此，必须对数据集或您的案例数组进行排序以使“
    的
      在最短时间内最好用
    </强>
    ”。
  
</DIV>

2# 时间 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    官方的答案是来自
  
  <OL>
    <LI>
      <a href="https://software.intel.com/en-us/articles/avoiding-the-cost-of-branch-misprediction" rel="noreferrer">
        英特尔 - 避免分支机构错误预测的成本
      </A>
    </LI>
    <LI>
      <a href="https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts" rel="noreferrer">
        英特尔 - 分支和循环重组以防止错误预测
      </A>
    </LI>
    <LI>
      <a href="https://scholar.google.com/scholar?q=branch%20prediction%20computer%20architecture&hl=da&as_sdt=0&as_vis=1&oi=scholart" rel="noreferrer">
        科学论文 - 分支预测计算机结构
      </A>
    </LI>
    <LI>
      书籍：J.L。Hennessy，D.A。 Patterson：计算机体系结构：定量方法
    </LI>
    <LI>
      科学出版物中的文章：T.Y。 Ye，Y.N。 Patt在分支预测上做了很多这些。
    </LI>
  </醇>
  
    你也可以从这个可爱的地方看到
    <a href="https://en.wikipedia.org/wiki/Branch_predictor#/media/File:Branch_prediction_2bit_saturating_counter-dia.svg" rel="noreferrer">
      图
    </A>
     为什么分支预测器会混淆。
  
  
    <a href="https://i.stack.imgur.com/pBMV2.png" rel="noreferrer">
      <img src =“https://i.stack.imgur.com/pBMV2.png”alt =“2位状态图”/>
    </A>
  
  
    原始代码中的每个元素都是随机值
  
   <pre>
 <code>
 data[c] = std::rand() % 256;

</code>
 </pre>
  
    所以预测变量将会改变
     <code>
 std::rand()
 </code>
     吹。
  
  
    另一方面，一旦它被排序，预测器将首先进入强烈未被采用的状态，并且当值变为高值时，预测器将在三次运行中通过从强烈不采取到强烈采取的一直改变。
  
  <HR />
</DIV>

3# 猫南北 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    如果您对可以对此代码进行的更多优化感到好奇，请考虑以下事项：
  
  
    从原始循环开始：
  
   <pre>
 <code>
 for (unsigned i = 0; i < 100000; ++i)
{
 for (unsigned j = 0; j < arraySize; ++j)
 {
 if (data[j] >= 128)
 sum += data[j];
 }
}

</code>
 </pre>
  
    通过循环交换，我们可以安全地将此循环更改为：
  
   <pre>
 <code>
 for (unsigned j = 0; j < arraySize; ++j)
{
 for (unsigned i = 0; i < 100000; ++i)
 {
 if (data[j] >= 128)
 sum += data[j];
 }
}

</code>
 </pre>
  
    然后，你可以看到
     <code>
 if
 </code>
     条件在整个执行过程中是不变的
     <code>
 i
 </code>
     循环，所以你可以提升
     <code>
 if
 </code>
     出：
  
   <pre>
 <code>
 for (unsigned j = 0; j < arraySize; ++j)
{
 if (data[j] >= 128)
 {
 for (unsigned i = 0; i < 100000; ++i)
 {
 sum += data[j];
 }
 }
}

</code>
 </pre>
  
    然后，您会看到内部循环可以折叠成一个单独的表达式，假设浮点模型允许它（例如，/ fp：fast被抛出）
  
   <pre>
 <code>
 for (unsigned j = 0; j < arraySize; ++j)
{
 if (data[j] >= 128)
 {
 sum += data[j] * 100000;
 }
}

</code>
 </pre>
  
    那个比以前快了100,000倍
  
</DIV>

4# 一号位 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    这是关于分支预测。它是什么？
  
  <UL>
    <LI>
      
        分支预测器是古老的性能改进技术之一，它仍然与现代建筑相关。虽然简单的预测技术提供快速查找和功率效率，但是它们具有高的误预测率。
      
    </LI>
    <LI>
      
        另一方面，复杂的分支预测 - 基于神经或两级分支预测的变体 - 提供更好的预测准确性，但是它们消耗更多的功率和复杂性以指数方式增加。
      
    </LI>
    <LI>
      
        除此之外，在复杂的预测技术中，预测分支所花费的时间本身非常高 - 从2到5个周期的变化 - 与实际分支的执行时间相当。
      
    </LI>
    <LI>
      
        分支预测本质上是一种优化（最小化）问题，其中重点在于以最少的资源实现最低可能的未命中率，低功耗和低复杂度。
      
    </LI>
  </UL>
  
    确实有三种不同的分支：
  
  
    的
      转发条件分支
    </强>
      - 基于运行时条件，PC（程序计数器）被改变为指向指令流中的前向地址。
  
  
    的
      向后条件分支
    </强>
      - PC在指令流中更改为指向后方。分支基于某些条件，例如，当循环结束时的测试表明循环应该再次执行时，向后分支到程序循环的开头。
  
  
    的
      无条件分支
    </强>
      - 这包括跳转，过程调用和没有特定条件的返回。例如，无条件跳转指令可能用汇编语言编码为简单的“jmp”，并且指令流必须立即定向到跳转指令指向的目标位置，而条件跳转可能被编码为“jmpne”仅当先前“比较”指令中两个值的比较结果显示值不相等时，才会重定向指令流。 （x86体系结构使用的分段寻址方案增加了额外的复杂性，因为跳转可以是“近”（在一个段内）或“远”（在段外）。每种类型对分支预测算法都有不同的影响。）
  
  
    的
      静态/动态分支预测
    </强>
    ：微处理器在第一次遇到条件分支时使用静态分支预测，并且动态分支预测用于条件分支代码的后续执行。
  
  
    参考文献：
  
  <UL>
    <LI>
      
        
          <a href="https://en.wikipedia.org/wiki/Branch_predictor" rel="noreferrer">
            分支预测器
          </A>
        
      
    </LI>
    <LI>
      
        
          <a href="http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm" rel="noreferrer">
            自我描绘的证明
          </A>
        
      
    </LI>
    <LI>
      
        
          <a href="https://courses.cs.washington.edu/courses/csep548/06au/lectures/branchPred.pdf" rel="noreferrer">
            分支预测评论
          </A>
        
      
    </LI>
    <LI>
      
        
          <a href="https://web.njit.edu/~rlopes/Mod5.3.pdf" rel="noreferrer">
            分支预测
          </A>
        
      
    </LI>
  </UL>
</DIV>

5# 威斯特 | 2019-08-31 10-32

6# 纾潆锦袖迷子 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    当数据被排序时性能显着提高的原因在于去除了分支预测惩罚，如精美地解释的那样
    <a href="https://stackoverflow.com/users/922184/mysticial">
      Mysticial
    </A>
    的答案。
  
  
    现在，如果我们看一下代码
  
   <pre>
 <code>
 if (data[c] >= 128)
 sum += data[c];

</code>
 </pre>
  
    我们可以发现这个特殊的含义
     <code>
 if... else...
 </code>
     branch是在条件满足时添加内容。这种类型的分支可以很容易地转换成
    的
      有条件的举动
    </强>
     语句，将被编译成条件移动指令：
     <code>
 cmovl
 </code>
    ，在
     <code>
 x86
 </code>
     系统。分支以及因此潜在的分支预测惩罚被移除。
  
  
    在
     <code>
 C
 </code>
    因此
     <code>
 C++
 </code>
    ，语句，它将直接编译（没有任何优化）到条件移动指令中
     <code>
 x86
 </code>
    ，是三元运算符
     <code>
 ... ? ... : ...
 </code>
    。所以我们将上面的语句重写为等价的语句：
  
   <pre>
 <code>
 sum += data[c] >=128 ? data[c] : 0;

</code>
 </pre>
  
    在保持可读性的同时，我们可以检查加速因子。
  
  
    在英特尔
    <a href="http://en.wikipedia.org/wiki/Intel_Core#Core_i7" rel="noreferrer">
      核心i7
    </A>
    -2600K @ 3.4 GHz和Visual Studio 2010发布模式，基准是（从Mysticial复制的格式）：
  
  
    的
      86
    </强>
  
   <pre>
 <code>
 // Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

</code>
 </pre>
  
    的
      64位
    </强>
  
   <pre>
 <code>
 // Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

</code>
 </pre>
  
    结果在多个测试中是稳健的。当分支结果不可预测时，我们得到了很大的加速，但是当它是可预测的时候我们会受到一点点的影响。事实上，在使用条件移动时，无论数据模式如何，性能都是相同的。
  
  
    现在让我们通过调查来仔细观察
     <code>
 x86
 </code>
     他们生成的装配。为简单起见，我们使用两个函数
     <code>
 max1
 </code>
     和
     <code>
 max2
 </code>
    。
  
  
     <code>
 max1
 </code>
     使用条件分支
     <code>
 if... else ...
 </code>
    ：
  
   <pre>
 <code>
 int max1(int a, int b) {
 if (a > b)
 return a;
 else
 return b;
}

</code>
 </pre>
  
     <code>
 max2
 </code>
     使用三元运算符
     <code>
 ... ? ... : ...
 </code>
    ：
  
   <pre>
 <code>
 int max2(int a, int b) {
 return a > b ? a : b;
}

</code>
 </pre>
  
    在x86-64机器上，
     <code>
 GCC -S
 </code>
     生成下面的程序集。
  
   <pre>
 <code>
 :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

</code>
 </pre>
  
     <code>
 max2
 </code>
     由于使用指令，使用的代码少得多
     <code>
 cmovge
 </code>
    。但真正的好处是
     <code>
 max2
 </code>
     不涉及分支跳跃，
     <code>
 jmp
 </code>
    如果预测结果不正确，将会对性能造成重大影响。
  
  
    那么为什么有条件的移动表现更好？
  
  
    在一个典型的
     <code>
 x86
 </code>
     处理器，指令的执行分为几个阶段。粗略地说，我们有不同的硬件来处理不同的阶段。因此，我们不必等待一条指令完成开始新指令。这就是所谓的
    的
      <a href="http://en.wikipedia.org/wiki/Pipeline_%28computing%29" rel="noreferrer">
        流水线
      </A>
    </强>
    。
  
  
    在分支情况下，以下指令由前一个指令确定，因此我们不能进行流水线操作。我们必须等待或预测。
  
  
    在条件移动的情况下，执行条件移动指令分为几个阶段，但早期阶段如
     <code>
 Fetch
 </code>
     和
     <code>
 Decode
 </code>
     不依赖于前一条指令的结果;只有后期才需要结果。因此，我们等待一个指令执行时间的一小部分。这就是为什么当预测很容易时，条件移动版本比分支慢。
  
  
    这本书
    
      <a href="https://rads.stackoverflow.com/amzn/click/com/0136108040" rel="noreferrer">
        计算机系统：程序员的观点，第二版
      </A>
    
     详细解释了这一点。您可以查看第3.6.6节
    
      有条件的移动指令
    
    ，整个第4章
    
      处理器架构
    
    和第5.11.2节的特殊处理
    
      分支预测与错误预测处罚
    
    。
  
  
    有时，一些现代编译器可以优化我们的代码以便以更好的性能进行汇编，有时一些编译器不能（有问题的代码使用Visual Studio的本机编译器）。在不可预测的情况下了解分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化时更好地编写代码。
  
</DIV>

7# 小狮子 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    需要对数据进行排序的其他答案的假设是不正确的。
  
  
    以下代码不对整个数组进行排序，而是仅对其中的200个元素进行排序，从而运行得最快。
  
  
    仅对k元素部分进行排序以线性时间完成预处理而不是
     <code>
 n.log(n)
 </code>
    。
  
   <pre>
 <code>
 #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 array
 for (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;
}

</code>
 </pre>
  
    这也“证明”它与任何算法问题无关，例如排序顺序，它确实是分支预测。
  
</DIV>

8# 纾潆锦袖迷子 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    正如其他人已经提到的那样，神秘背后的是什么
    <a href="https://en.wikipedia.org/wiki/Branch_predictor" rel="noreferrer">
      分支预测器
    </A>
    。
  
  
    我不是想添加一些东西，而是以另一种方式解释这个概念。
维基上有一个简明的介绍，其中包含文本和图表。
我喜欢下面的解释，它使用图表直观地阐述了分支预测器。
  
  <BLOCKQUOTE>
    
      在计算机体系结构中，分支预测器是a
  试图猜测分支的方式的数字电路（例如
  if-then-else结构）将在此之前确定。该
  分支预测器的目的是改善流量
  指令管道。分支预测因子在其中起着关键作用
  在许多现代流水线中实现高效性能
  微处理器架构，如x86。
    
    
      双向分支通常使用条件跳转来实现
  指令。条件跳转可以“不采用”并继续
  使用紧随其后的第一个代码分支执行
  条件跳转后，或者可以“采取”并跳转到
  程序存储器中不同的位置，代码的第二个分支是
  存储。目前尚不清楚是否会有条件跳跃
  在计算条件之前采取或不采取
  条件跳转已经过了指令中的执行阶段
  管道（见图1）。
    
  </BLOCKQUOTE>
  
    <a href="https://i.stack.imgur.com/unxnb.png" rel="noreferrer">
      <img src =“https://i.stack.imgur.com/unxnb.png”alt =“figure 1”/>
    </A>
  
  
    基于所描述的场景，我编写了一个动画演示，以显示在不同情况下如何在管道中执行指令。
  
  <OL>
    <LI>
      没有分支预测器。
    </LI>
  </醇>
  <BLOCKQUOTE>
    
      如果没有分支预测，处理器将不得不等到
  条件跳转指令已经过了执行阶段
  下一条指令可以进入管道中的获取阶段。
    
  </BLOCKQUOTE>
  
    该示例包含三个指令，第一个是条件跳转指令。后两条指令可以进入流水线，直到执行条件跳转指令。
  
  
    <a href="https://i.stack.imgur.com/GMFQ6.gif" rel="noreferrer">
      <img src =“https://i.stack.imgur.com/GMFQ6.gif”alt =“没有分支预测器”/>
    </A>
  
  
    完成3条指令需要9个时钟周期。
  
  <ol start =“2”>
    <LI>
      使用分支预测器，不要进行条件跳转。我们假设预测是
      的
        不
      </强>
       采取有条件的跳跃。
    </LI>
  </醇>
  
    <a href="https://i.stack.imgur.com/Ms5p1.gif" rel="noreferrer">
      <img src =“https://i.stack.imgur.com/Ms5p1.gif”alt =“在此处输入图片说明”/>
    </A>
  
  
    完成3条指令需要7个时钟周期。
  
  <ol start =“3”>
    <LI>
      使用分支预测器并进行条件跳转。我们假设预测是
      的
        不
      </强>
       采取有条件的跳跃。
    </LI>
  </醇>
  
    <a href="https://i.stack.imgur.com/HIpG3.gif" rel="noreferrer">
      <img src =“https://i.stack.imgur.com/HIpG3.gif”alt =“在此处输入图片说明”/>
    </A>
  
  
    完成3条指令需要9个时钟周期。
  
  <BLOCKQUOTE>
    
      在分支错误预测的情况下浪费的时间等于
  从提取阶段到管道的管道中的阶段数
  执行阶段。现代微处理器往往需要很长时间
  管道使错误预测延迟在10到20个时钟之间
  周期。因此，延长管道时间增加了对a的需求
  更高级的分支预测器。
    
  </BLOCKQUOTE>
  
    如您所见，似乎我们没有理由不使用Branch Predictor。
  
  
    这是一个非常简单的演示，阐明了分支预测器的基本部分。如果这些GIF很烦人，请随时将它们从答案中删除，访问者也可以从中获取演示
    <a href="https://github.com/Gearon/BPViewer.git" rel="noreferrer">
      混帐
    </A>
  
</DIV>

9# CC-f | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    由于称为分支预测的现象，排序的阵列比未排序的阵列处理得更快。
  
  
    分支预测器是一种数字电路（在计算机体系结构中），试图预测分支将以哪种方式运行，从而改善指令流水线中的流量。电路/计算机预测下一步并执行它。
  
  
    做出错误的预测会导致返回上一步，并执行另一个预测。假设预测正确，代码将继续下一步。错误的预测导致重复相同的步骤，直到发生正确的预测。
  
  
    你的问题的答案很简单。
  
  
    在未排序的数组中，计算机会进行多次预测，从而导致错误发生的可能性增加。
然而，在排序中，计算机进行的预测更少，从而减少了出错的可能性。
进行更多预测需要更多时间。
  
  
    分类阵列：直道
  
   <pre>
 <code>
 ____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

</code>
 </pre>
  
    未排序的阵列：弯曲的道路
  
   <pre>
 <code>
 ______ ________
| |__|

</code>
 </pre>
  
    分支预测：猜测/预测哪条道路是直的并且在没有检查的情况下跟随它
  
   <pre>
 <code>
 ___________________________________________ Straight road
 |_________________________________________|Longer road

</code>
 </pre>
  
    虽然两条道路都到达同一目的地，但直道较短，而另一条较长。如果那时你错误地选择了另一个，那么就没有回头了，所以如果你选择更长的路，你会浪费一些额外的时间。这与计算机上发生的情况类似，我希望这有助于您更好地理解。
  
  <HR />
  
    我也想引用
    <a href="https://stackoverflow.com/users/16940/simon-weaver">
      @Simon_Weaver
    </A>
     来自评论：
  
  <BLOCKQUOTE>
    
      它没有做出更少的预测 - 它减少了不正确的预测。它仍然必须通过循环每次预测..
    
  </BLOCKQUOTE>
</DIV>

10# 特狼普 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    由于分支预测，上述行为正在发生。
  
  
    要理解分支预测，首先必须了解
    的
      指令流水线
    </强>
    ：
  
  
    任何指令都被分成一系列步骤，以便可以并行地同时执行不同的步骤。这种技术称为指令流水线，用于提高现代处理器的吞吐量。为了更好地理解这一点，请看这个
    <a href="https://en.wikipedia.org/wiki/Pipeline_(computing)#Concept_and_motivation" rel="noreferrer">
      维基百科上的例子
    </A>
    。
  
  
    通常，现代处理器具有相当长的流水线，但为了方便起见，我们仅考虑这4个步骤。
  
  <OL>
    <LI>
      IF - 从内存中获取指令
  
    </LI>
    <LI>
      ID - 解码指令
  
    </LI>
    <LI>
      EX - 执行指令
  
    </LI>
    <LI>
      WB - 写回CPU寄存器

</LI>
  </醇>
  
    的
      
        4级管道一般用于2条指令。
      
    </强>
    <img src =“https://i.stack.imgur.com/PqBBR.png”alt =“一般4阶段管道”/>
  
  
    回到上面的问题，让我们考虑以下说明：
  
   <pre>
 <code>
 A) if (data[c] >= 128)
 /\
 / \
 / \
 true / \ false
 / \
 / \
 / \
 / \
 B) sum += data[c]; C) for loop or print().

</code>
 </pre>
  
    如果没有分支预测，将发生以下情况：
  
  
    为了执行指令B或指令C，处理器必须等到指令A没有到达流水线中的EX阶段，因为转到指令B或指令C的决定取决于指令A的结果。所以管道会是这样的。
  
  
    的
      
        当if条件返回true时：
      
    </强>
    <img src =“https://i.stack.imgur.com/0H4gP.png”alt =“在此处输入图像说明”/>
  
  
    的
      
        当if条件返回false时：
      
    </强>
    <img src =“https://i.stack.imgur.com/APpca.png”alt =“在此处输入图片说明”/>
  
  
    作为等待指令A的结果的结果，在上述情况下花费的总CPU周期（没有分支预测;对于真和假）都是7。
  
  
    的
      那么什么是分支预测？
    </强>
  
  
    分支预测器将尝试猜测分支（if-then-else结构）将以何种方式确定之前。它不会等待指令A到达流水线的EX阶段，但它会猜测决定并转到该指令（在我们的例子中是B或C）。
  
  
    的
      
        如果猜测正确，管道看起来像这样：
      
    </强>
    <img src =“https://i.stack.imgur.com/ZYUbs.png”alt =“在此处输入图片说明”/>
  
  
    如果稍后检测到猜测错误则丢弃部分执行的指令，并且管道以正确的分支重新开始，从而引起延迟。
在分支错误预测的情况下浪费的时间等于从提取阶段到执行阶段的管道中的阶段的数量。现代微处理器往往具有相当长的流水线，因此误预测延迟在10到20个时钟周期之间。管道越长，对商品的需求就越大
    <a href="https://en.wikipedia.org/wiki/Branch_predictor" rel="noreferrer">
      分支预测器
    </A>
    。
  
  
    在OP的代码中，第一次有条件时，分支预测器没有任何基于预测的信息，所以第一次它会随机选择下一条指令。稍后在for循环中，它可以基于历史记录进行预测。
对于按升序排序的数组，有三种可能性：
  
  <OL>
    <LI>
       所有元素都小于128

</LI>
    <LI>
       所有元素都大于128

</LI>
    <LI>
       一些起始新元素小于128，后来大于128

</LI>
  </醇>
  
    让我们假设预测器将在第一次运行时始终采用真分支。
  
  
    因此，在第一种情况下，它始终采用真正的分支，因为历史上它的所有预测都是正确的。
在第二种情况下，最初它会预测错误，但经过几次迭代后，它会正确预测。
在第三种情况下，它将最初正确预测，直到元素小于128.之后它将失败一段时间并且当它看到历史中的分支预测失败时正确。
  
  
    在所有这些情况下，失败的数量会太少，因此，只需要几次就可以丢弃部分执行的指令并重新使用正确的分支，从而减少CPU周期。
  
  
    但是在随机未排序的数组的情况下，预测将需要丢弃部分执行的指令并且在大多数时间重新开始使用正确的分支，并且与排序的数组相比产生更多的CPU周期。
  
</DIV>

11# 丫头 | 2019-08-31 10-32

12# 真不错 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”>
  
    我刚刚读到了这个问题及其答案，我觉得答案遗失了。
  
  
    消除我发现在托管语言中工作特别好的分支预测的常用方法是查找表而不是使用分支（尽管在这种情况下我还没有测试过）。
  
  
    这种方法通常适用于：
  
  <OL>
    <LI>
      它是一个小桌子，可能会被缓存在处理器中，并且
    </LI>
    <LI>
      你在一个非常紧凑的循环中运行和/或处理器可以预加载数据。
    </LI>
  </醇>
  
    的
      背景和原因
    </强>
  
  
    从处理器的角度来看，你的记忆很慢。为了弥补速度的差异，处理器（L1 / L2缓存）中内置了几个缓存。所以想象一下，你正在进行漂亮的计算并弄清楚你需要一块内存。处理器将获得其“加载”操作并将内存加载到缓存中 - 然后使用缓存执行其余计算。因为内存相对较慢，这种“加载”会降低程序的速度。
  
  
    与分支预测一样，这在Pentium处理器中进行了优化：处理器预测它需要加载一段数据并尝试在操作实际到达缓存之前将其加载到缓存中。正如我们已经看到的那样，分支预测有时会出现严重错误 - 在最坏的情况下，您需要返回并实际等待内存负载，这将需要永远（
    的
      换句话说：失败的分支预测是坏的，分支预测失败后的内存负载是可怕的！
    </强>
    ）。
  
  
    幸运的是，如果内存访问模式是可预测的，处理器将把它加载到快速缓存中，一切都很顺利。
  
  
    我们需要知道的第一件事是什么
    
      小
    
    ？虽然较小通常更好，但经验法则是坚持大于＆lt; = 4096字节的查找表。作为上限：如果您的查找表大于64K，则可能值得重新考虑。
  
  
    的
      构建一个表
    </强>
  
  
    所以我们已经发现我们可以创建一个小表。接下来要做的是获得一个查找功能。查找函数通常是使用几个基本整数运算的小函数（和，或者，xor，shift，add，remove和multiply）。您希望通过查找功能将您的输入转换为表格中的某种“唯一键”，然后简单地为您提供您希望它完成的所有工作的答案。
  
  
    在这种情况下：＆gt; = 128表示我们可以保留该值，＆lt; 128意味着我们摆脱它。最简单的方法是使用'AND'：如果我们保留它，我们和7FFFFFFF;如果我们想要摆脱它，我们和它的0.注意另外128是2的幂 - 所以我们可以继续制作一个32768/128整数的表并填充一个零和很多7FFFFFFFF的。
  
  
    的
      托管语言
    </强>
  
  
    您可能想知道为什么这在托管语言中运行良好。毕竟，托管语言使用分支检查数组的边界，以确保您不会陷入困境......
  
  
    好吧，不完全...... :-)
  
  
    为管理语言删除此分支已经做了相当多的工作。例如：
  
   <pre class="lang-cs prettyprint-override">
 <code>
 for (int i = 0; i < array.Length; ++i)
{
 // Use array[i]
}

</code>
 </pre>
  
    在这种情况下，编译器显然不会遇到边界条件。至少Microsoft JIT编译器（但我希望Java做类似的事情）会注意到这一点，并完全删除检查。哇，这意味着没有分支。同样，它将处理其他明显的情况。
  
  
    如果您在托管语言中查找时遇到问题 - 关键是添加一个
     <code>
 & 0x[something]FFF
 </code>
     到您的查找功能，使边界检查可预测 - 并观察它更快。
  
  
    的
      这种情况的结果
    </强>
  
   <pre class="lang-cs prettyprint-override">
 <code>
 // Generate data
int 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;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
 // Primary loop
 for (int j = 0; j < arraySize; ++j)
 {
 /* Here you basically want to use simple operations - so no
 random 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();

</code>
 </pre>
</DIV>