为什么处理排序后的数组比未排序的数组更快？
这是一段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)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
std::sort(data, data + arraySize); ，代码在11.54秒内运行。 起初，我认为这可能只是一种语言或编译器异常。 所以我尝试了Java。
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)
{
// Primary loop
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
有点类似但不太极端的结果。
我的第一个想法是排序将数据带入缓存，但后来我认为这是因为数组刚刚生成而变得非常愚蠢。
你是分支预测失败的受害者。
什么是分支预测？
考虑铁路枢纽：
Mecanismo的图像，通过维基共享资源。 在CC-By-SA 3.0许可下使用。
现在为了争辩，假设这是在19世纪 - 在长途或无线电通信之前。
你是一个交叉口的运营商，你会听到火车驶过。 你不知道它应该走哪条路。 你停下火车去询问司机他们想要的方向。 然后你适当地设置开关。
火车很重，且有很多惯性。 所以他们需要永远的启动并放慢速度。
有没有更好的办法？ 你猜猜火车会去哪个方向！
如果你猜对了 ，火车永远不会停下来。
如果您经常猜错 ，火车会花费大量时间停止，备份和重新启动。
考虑一条if语句：在处理器级别，它是一条分支指令：
你是一个处理器，你看到一个分支。 你不知道它会走哪条路。 你是做什么？ 您停止执行并等到前面的指示完成。 然后你继续正确的道路。
现代处理器很复杂，并且管道很长。 所以他们永远都要“热身”和“放慢速度”。
有没有更好的办法？ 你猜猜分支会走哪个方向！
如果你每次都猜对 ，执行永远不会停止。
如果您经常猜错 ，您会花费大量时间拖延，回滚并重新启动。
这是分支预测。 我承认这不是最好的比喻，因为火车可以用一面旗帜标出方向。 但在计算机中，处理器不知道分支将走向哪个方向，直到最后一刻。
那么，你如何策略性地猜测，以尽量减少火车必须备份并沿着另一条路走下去的次数？ 你看过去的历史！ 如果火车在99％的时间里离开，那么你猜就走了。 如果它交替出现，那么你就交替你的猜测。 如果它每3次走一次，你就会猜到相同的...
换句话说，你试图找出一个模式并遵循它。 这或多或少是分支预测器的工作原理。
大多数应用程序具有良好的分支。 所以现代分支预测器通常会达到> 90％的命中率。 但是当面对不可识别的模式的不可预知的分支时，分支预测器实际上是无用的。
进一步阅读：维基百科上的“分支预测”文章。
正如上文所暗示的，罪魁祸首是这个if语句：
if (data[c] >= 128)
sum += data[c];
请注意，数据均匀分布在0和255之间。数据排序时，大致前半部分迭代不会进入if语句。 之后，他们将全部进入if语句。
这对于分支预测器非常友好，因为分支连续多次走向相同的方向。 即使是简单的饱和计数器也能正确预测分支，除了切换方向后的少数迭代。
快速可视化：
T = branch taken
N = 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, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)
那么可以做些什么？
如果编译器无法将分支优化为条件转移，那么如果您愿意为了提高性能而牺牲可读性，则可以尝试一些黑客行为。
更换：
if (data[c] >= 128)
sum += data[c];
有：
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
这消除了分支并用一些按位操作代替它。
（请注意，这种破解不等同于原始的if语句，但在这种情况下，它对于data[]所有输入值都是有效的。）
基准：Core i7 920 @ 3.5 GHz
C ++ - Visual Studio 2010 - x64发布
// Branch - Random
seconds = 11.777
// Branch - Sorted
seconds = 2.352
// Branchless - Random
seconds = 2.564
// Branchless - Sorted
seconds = 2.587
Java - Netbeans 7.1.1 JDK 7 - x64
// Branch - Random
seconds = 10.93293813
// Branch - Sorted
seconds = 5.643797077
// Branchless - Random
seconds = 3.113581453
// Branchless - Sorted
seconds = 3.186068823
观察：
一般的经验法则是在关键循环中避免与数据相关的分支。 （比如在这个例子中）
更新：
在x64上使用-O3或-ftree-vectorize GCC 4.6.1能够生成条件移动。 所以排序和未排序的数据没有区别 - 两者都很快。
即使在/Ox下，VC ++ 2010也无法为该分支生成条件移动。
英特尔编译器11做了奇迹般的事情。 它交换两个环路，从而将不可预知的分支提升到外部环路。 因此，它不仅可以避免错误预测，而且还可以快于VC ++和GCC可以生成的速度！ 换句话说，ICC利用测试循环来击败基准...
如果您为英特尔编译器提供无分支代码，则只需将它向外化即可......并且与分支一样快（使用循环交换）。
这表明即使成熟的现代编译器在优化代码的能力方面也可能会有很大差异。
分支预测。
与排序后的数组，条件data[c] >= 128是第一false对值的条纹，然后变成true的所有后来值。 这很容易预测。 使用未排序的阵列，您需要支付分支成本。
数据排序后性能大幅提高的原因是分支预测罚分被删除，正如Mysticial的回答中所解释的那样。
现在，如果我们看一下代码
if (data[c] >= 128)
sum += data[c];
我们可以发现这个特定的if... else...分支的含义是在条件满足时添加一些东西。 这种类型的分支可以很容易地转换为条件移动语句，该语句将被编译为x86系统中的条件移动指令： cmovl 。 该分支以及因此潜在分支预测罚分被移除。
在C （ C++ ，直接编译（没有任何优化）到x86的条件移动指令的语句是三元运算符... ? ... : ... ... ? ... : ... 所以我们把上面的语句改写成一个等价的语句：
sum += data[c] >=128 ? data[c] : 0;
在保持可读性的同时，我们可以检查加速因子。
在Intel Core i7-2600K @ 3.4 GHz和Visual Studio 2010发布模式下，基准测试（格式从Mysticial复制）：
86
// Branch - Random
seconds = 8.885
// Branch - Sorted
seconds = 1.528
// Branchless - Random
seconds = 3.716
// Branchless - Sorted
seconds = 3.71
64位
// Branch - Random
seconds = 11.302
// Branch - Sorted
seconds = 1.830
// Branchless - Random
seconds = 2.736
// Branchless - Sorted
seconds = 2.737
结果在多个测试中是稳健的。 当分支结果不可预知时，我们得到了很大的加速，但是当它是可预测的时候，我们会受到一点影响。 实际上，使用条件移动时，无论数据模式如何，性能都是相同的。
现在让我们仔细研究它们生成的x86汇编。 为了简单起见，我们使用了两个函数max1和max2 。
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
由于使用指令cmovge max2使用的代码少cmovge 。 但真正的收益是， max2不涉及分支跳转， jmp ，如果预测结果不正确，将会有显着的性能损失。
那么为什么有条件的移动表现更好呢？
在典型的x86处理器中，指令的执行分为几个阶段。 粗略地说，我们有不同的硬件来处理不同的阶段。 所以我们不必等待一条指令完成才能开始一条新指令。 这被称为流水线 。
在分支情况下，下面的指令由前一个指令决定，所以我们不能进行流水线操作。 我们必须等待或预测。
在有条件移动的情况下，执行条件移动指令被分成几个阶段，但像Fetch和Decode这样的早期阶段不依赖于前一条指令的结果; 只有后面的阶段需要结果。 因此，我们等待一个指令执行时间的一小部分。 这就是为什么当预测很容易时，条件移动版本比分支慢。
“计算机系统：程序员的观点”一书的第二版详细解释了这一点。 您可以参阅第3.6.6节“条件传送指令”，第4章处理器架构的全部内容，以及第5.11.2节“分支预测和错误预测处罚的特殊处理”。
有时，一些现代编译器可以优化我们的代码以获得更好的性能，有时某些编译器不能（所讨论的代码使用Visual Studio的本机编译器）。 了解不可预知的分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以致编译器无法自动优化它们时编写更好的性能的代码。
链接地址: http://www.djcxy.com/p/1.html上一篇: Why is it faster to process a sorted array than an unsorted array?
下一篇: 没有了