这是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);
// 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(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';
std::cout << "sum = " << sum << '\n';
}
没有 std: sort( 数据, 数据+数组Size); 代码在 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);
}
}
其结果类似,但不太极端。
我的第一个想法是排序 将数据带入缓存, 但这是愚蠢的,因为数组 刚刚生成。
为什么处理一个分类阵列的速度要快于处理一个未分类阵列的速度?
守则正在总结一些独立的术语,因此命令不应重要。
与不同的/后来的汇编者和备选办法具有相同效果:
为什么处理一个未排列的阵列的速度与处理一个用现代 x86-64 叮当的排序阵列的速度相同? gcc 优化标记 -O3 使代码慢于 -O2
分流收益!
重要的是要理解分支错误控制不会减慢程序。 错误预测的成本就好像不存在分支预测,而你等待着对表达方式的评价来决定运行的代码(下段有进一步的解释 ) 。
if (expression)
{
// Run 1
} else {
// Run 2
}
当出现 if-else \ 切换语句时, 表达式必须被评估以确定要执行哪个区块。 在编译者生成的组装代码中, 插入有条件的分支指令 。
分支指令可导致计算机开始执行不同的指令序列,从而偏离其默认的按顺序执行指令的行为(即如果表达式是虚假的,程序会跳过区块的代码),这取决于某些条件,即我们情况下的表达式评价。
尽管如此, 编译者试图预测结果, 然后再对结果进行实际评估。 它会从区块中获取指示, 如果表达方式是真实的, 那么就太好了! 我们得到了时间来评估它, 并在代码中取得了进步; 如果不是那样, 我们运行错误的代码, 管道就会被冲洗, 正确的区块会运行 。
可视化:
假设你需要选择路线1或路线2, 等待你的伴侣检查地图, 你已经停留在 ##,等待, 或者你可以选择路线1, 如果你运气好(路线1是正确的路线), 那么伟大的你不必等待你的伴侣检查地图(你省下时间让他检查地图), 否则你就会转回去。
尽管冲水管道的速度超快,但如今赌博是值得的。 预测分类数据或缓慢变化的数据总是比预测快速变化容易,也好于预测快速变化。
O Route 1 /-------------------------------
/|\ /
| ---------##/
/ \ \
\
Route 2 \--------------------------------
官方的回答是来自
英特尔 -- -- 避免误用英特尔分公司的成本 -- -- 分公司和循环重组以防止误用科学论文 -- -- 分公司预测计算机建筑书籍:J.L. Hennessy, D.A. Patterson:计算机结构:定量方法 科学出版物中的文章:T.Y. Yeh, Y.N. Patt在分支预测方面做了许多这些。
你也可以从这张可爱的图表中看到 树枝预测器为什么会被混淆。
调
原始代码中的每个元素都是随机值
data[c] = std::rand() % 256;
所以预测器会随着 : rand () 的打击而改变两边。
另一方面,一旦对预测进行分类, 预测器将首先进入一个 强烈未被采纳的状态, 当值变化到高值时, 预测器将分三步走, 从强烈未被采纳到强烈被采纳。
正如其他人已经提到的那样,神秘背后的是部门预测员。
我不是要补充一些东西,而是要用另一种方式解释这个概念。维基文字有一个简明的介绍,里面有文字和图表。我确实喜欢下面的解释,下面用一个图表来用直觉来描述处的预言。
在计算机结构中,分支预测器是一种数字电路,它试图猜测分支(如如果是当时的else结构)将以何种方式进行,然后才能确定这一点。分支预测器的目的是改善教学管道的流量。分支预测器在很多现代管道式微处理器结构(如x86)中实现高有效性能方面发挥着关键作用。双向分支通常是通过有条件的跳跃指令来实施。有条件跳跃可以是“不采取”的,也可以是有条件跳跃后立即实施的代码的第一个分支,或者可以是“获取”的,然后跳到存储第二分支的程序内存中的不同位置。在计算条件和有条件跳动通过指令管道的执行阶段之前,无法确定是否进行有条件跳动(见图1)。
调
根据所述情况,我写了动画演示,以显示在不同情况下如何在管道中执行指示。
没有部门预言家。
没有分支预测,处理器必须等到有条件跳跃指令通过执行阶段后,下一个指令才能进入管道的接货阶段。
该示例包含三个指令, 第一个是有条件跳跃指令。 后两个指令可以进入管道, 直到有条件跳跃指令执行为止 。
调
完成3项指示需要9小时周期。
使用预测器,不要采取有条件的跳跃。让我们假设预测不会采取有条件的跳跃。
调
完成3项指示需要7小时周期。
我们假设预测不会采取有条件的跳跃
调
完成3项指示需要9小时周期。
在分支误用的情况下,浪费的时间相当于从取货阶段到执行阶段的输油管阶段的数量。 现代微处理器往往有相当长的输油管,因此误用延迟时间在10到20小时之间。 结果,输油管更长时间增加了对更先进的分支预测器的需求。
如你所见,我们似乎没有理由不使用 部门预言家。
这是一个很简单的演示, 澄清了分支预测器的基本部分。 如果这些 gifs 令人烦恼, 请随意将其从答案中删除, 访问者也可以从 PredictorDemo 获得现场演示源代码 。
Bjarne Stroustrup对此问题的答复:
这听起来像面试问题。是真的吗?你怎么知道?回答效率问题而不首先做一些测量是不明智的,所以知道如何衡量是很重要的。
于是,我用百万整数的矢量尝试过,然后得到:
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(以及一般分类)是一项复杂的研究,吸引了计算机科学中最伟大的一些思想。 一种良好的功能是选择良好的算法和关注硬件的运行效果的结果。
如果您想要写入高效代码, 您需要了解一些关于机器结构的知识 。
