这是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秒内运行
(分类本身需要的时间比这个通过数组的时间要长, 所以如果我们需要计算未知数组, 它实际上不值得做 。)
起初,我以为这只是一种语言或编译器异常, 所以我尝试了爪哇:
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);
}
}
其结果类似,但不太极端。
我第一种想法是 分类能把数据带进缓存缓存,但那是愚蠢的 因为阵列是刚刚产生的。
- 这是怎么回事?
- 为什么处理一个分类阵列的速度要快于处理一个未排序阵列的速度?
守则正在总结一些独立的术语,因此命令不应重要。
相关/后续行动不同/以后的编译者和选项的相同效果:
巴恩·斯特鲁斯特鲁斯特鲁普的回答对此问题:
这听起来像面试问题。是真的吗?你怎么知道?回答效率问题而不首先做一些测量是不明智的,所以知道如何衡量是很重要的。
于是,我用百万整数的矢量尝试过,然后得到:
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(以及一般分类)是一项复杂的研究,吸引了计算机科学中最伟大的一些思想。 一种良好的功能是选择良好的算法和关注硬件的运行效果的结果。
如果您想要写入高效代码, 您需要了解一些关于机器结构的知识 。
当对数组进行排序时,数据在 0 到 255 之间分布, 大约在迭代的前半部不会输入if- 声明if报表如下。 )
if (data[c] >= 128)
sum += data[c];
The question is: What makes the above statement not execute in certain cases as in case of sorted data? Here comes the "branch predictor". A branch predictor is a digital circuit that tries to guess which way a branch (e.g. an 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
“A “坏“真实的假造模式可以使if- 计算速度比“或”慢6倍。良好当然,哪一种模式是好的,哪一种模式是坏的,取决于汇编者的确切指示和具体处理者。
因此,部门预测对业绩的影响是毫无疑问的!
如果您对这个代码可以做的更多优化感到好奇, 请考虑 :
以原始循环开始 :
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;
}
}
这比以前快了十万倍
分流收益!
重要的是要理解分支错误控制不会减慢程序。 错误预测的成本就好像不存在分支预测,而你等待着对表达方式的评价来决定运行的代码(下段有进一步的解释 ) 。
if (expression)
{
// Run 1
} else {
// Run 2
}
每当有if-else \ switch语句中,必须评价表达式,以决定应执行哪个区块。在编译器生成的组装代码中,有条件分支分支分支插入说明。
分支指令可导致计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即如果表达式为虚假,程序跳过代码)if(根据某些条件,即我们案件的表达方式评价)
尽管如此,汇编者试图在对结果进行实际评估之前预测结果。if如果表达式是真实的,那么就太好了!我们得到了评估它所需的时间,并在代码中取得了进展;如果不是,我们运行错误的代码,管道被冲洗,正确的模块被运行。
可视化:
假设你需要选择路线1或路线2, 等待你的伴侣检查地图, 你已经停留在 ##,等待, 或者你可以选择路线1, 如果你运气好(路线1是正确的路线), 那么伟大的你不必等待你的伴侣检查地图(你省下时间让他检查地图), 否则你就会转回去。
尽管冲水管道的速度超快,但如今赌博是值得的。 预测分类数据或缓慢变化的数据总是比预测快速变化容易,也好于预测快速变化。
O Route 1 /-------------------------------
/|\ /
| ---------##/
/ \ \
\
Route 2 \--------------------------------
在同一行中(我认为没有任何答案强调这一点),最好提到有时(特别是在软件中,在软件中,性能很重要——如Linux内核),如果声明如下,你可以找到一些:
if (likely( everything_is_ok ))
{
/* Do something */
}
或类似:
if (unlikely(very_improbable_condition))
{
/* Do something */
}
两者likely()和unlikely()事实上,它们是通过使用诸如海合会(海合会)等东西来界定的宏观。__builtin_expect帮助编译者插入预测代码以有利于条件, 同时考虑到用户提供的信息 。 海合会支持其他能改变运行程序行为或发布低级别指令的内建元素, 如清除缓存等 。文献文件穿过海合会现有的建筑
通常这种优化主要在硬实时应用程序或内嵌系统中找到,在这些系统中,执行时间很重要且至关重要。例如,如果您正在检查某些错误条件,而错误条件只发生1/10000 000次,那么为什么不通知编译者?这样,默认情况下,分支预测会假设该条件是假的。
在分类的情况下,你可以做的比依靠成功的分支预测或任何无分支比较的把戏:完全删除分支。
事实上,阵阵列被分割在一个毗连区内,data < 128以data >= 128。因此,您应该用 a 来找到分区点脑细胞细胞研究(使用Lg(arraySize) = 15比较),然后从该点做一个直线积累。
类似的东西( 未检查 )
int i= 0, j, k= arraySize;
while (i < k)
{
j= (i + k) >> 1;
if (data[j] >= 128)
k= j;
else
i= 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;(假设分布真正统一,预计价值为191.5的16384个样本):-)
