极客观点
项目管理
HarmonyOS
这是一段 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 秒。
（排序本身比遍历数组需要更多时间，因此如果我们需要为未知数组计算它，实际上不值得这样做。）
最初，我认为这可能只是语言或编译器异常，所以我尝试了 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)
{
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);
}
}
有类似但不太极端的结果。
我的第一个想法是排序将数据带入 缓存，但后来我认为这是多么愚蠢，因为数组刚刚生成。
- 到底是怎么回事？
- 为什么处理排序数组比处理未排序数组更快？
该代码总结了一些独立的术语，因此顺序无关紧要。
关于不同/更高版本的编译器和选项的相同效果的 相关/后续问答：
原文由 GManNickG 发布，翻译遵循 CC BY-SA 4.0 许可协议
java
你是 分支预测 失败的受害者。
什么是分支预测？
考虑一个铁路枢纽：
现在为了争论，假设这是在 1800 年代——在远距离或无线电通信之前。
你是一个路口的盲人操作员，你听到火车来了。你不知道它应该走哪条路。你停下火车问司机他们想要哪个方向。然后你适当地设置开关。
火车很重并且有很大的惯性，所以它们需要很长时间才能启动和减速。
有没有更好的办法？你猜火车会开往哪个方向！
如果你每次都猜对 了，火车就永远不用停下来。
如果你猜错的次数太频繁，火车将花费大量时间停止、倒车和重新启动。
考虑一个 if 语句： 在处理器级别，它是一个分支指令：
你是一个处理器，你看到一个分支。你不知道它会朝哪个方向发展。你做什么工作？您停止执行并等待前面的指令完成。然后你继续沿着正确的路径前进。
现代处理器很复杂并且有很长的流水线。这意味着他们需要永远“热身”和“减速”。
有没有更好的办法？你猜这个分支会往哪个方向走！
如果你每次都猜对 了，执行将永远不会停止。
如果您经常猜错，您会花费大量时间停止、回滚和重新启动。
这是分支预测。我承认这不是最好的类比，因为火车只能用旗帜指示方向。但是在计算机中，处理器直到最后一刻才知道分支将走向哪个方向。
您将如何策略性地猜测以最小化火车必须倒车并沿另一条路径行驶的次数？你看看过去的历史！如果火车 99% 的时间都是左转，那么你猜是左转。如果它交替，那么你交替你的猜测。如果它每 3 次去一个方向，你猜同样…
换句话说，您尝试识别一种模式并遵循它。 这或多或少是分支预测器的工作方式。
大多数应用程序都有良好的分支。因此，现代分支预测器通常会达到 >90% 的命中率。但是当面对无法识别的模式的不可预测的分支时，分支预测器实际上是无用的。
进一步阅读： 维基百科上的“分支预测器”文章。
正如上面所暗示的，罪魁祸首是这个 if 语句：
注意数据均匀分布在 0 到 255 之间。当对数据进行排序时，大约前一半的迭代不会进入 if 语句。之后，它们都将进入 if 语句。
这对分支预测器非常友好，因为分支连续多次朝同一个方向移动。即使是一个简单的饱和计数器也能正确预测分支，除了它切换方向后的几次迭代。
快速可视化：
但是，当数据完全随机时，分支预测器就变得毫无用处，因为它无法预测随机数据。因此可能会有大约 50% 的错误预测（不比随机猜测好）。
可以做什么？
如果编译器无法将分支优化为条件移动，如果您愿意牺牲可读性来换取性能，您可以尝试一些技巧。
代替：
和：
这消除了分支并用一些按位操作替换它。
（请注意，这个 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
观察：
一般的经验法则是避免关键循环中的数据相关分支（例如在此示例中）。
更新：
-O3或-ftree-vectorize在 x64 上的 GCC 4.6.1 能够生成有条件的移动，因此排序数据和未排序数据之间没有区别 - 两者都很快。（或者有点快：对于已经排序的情况，
cmov可能会更慢，特别是如果 GCC 将它放在关键路径上而不是仅仅add，尤其是在 Broadwell 之前的英特尔上cmov有 2 个周期延迟： gcc 优化标志 -O3 使代码比 -O2 慢）即使在
/Ox下，VC++ 2010 也无法为此分支生成条件移动。英特尔 C++ 编译器(ICC) 11 做了一些神奇的事情。它 交换了两个循环，从而将不可预测的分支提升到外循环。它不仅不受错误预测的影响，而且速度也是 VC++ 和 GCC 生成的速度的两倍！换句话说，ICC 利用测试循环击败了基准测试……
如果您为英特尔编译器提供无分支代码，它会直接对其进行矢量化……并且与分支（使用循环交换）一样快。
这表明即使是成熟的现代编译器在优化代码的能力上也会有很大的不同……