这是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
是关于分支预测的 是什么?
分支预测器是一种古老的改进性能的技术,在现代建筑中仍然具有相关性。 虽然简单的预测技术提供了快速的外观和电力效率,但它们受到高误用率的影响。 另一方面,复杂的分支预测 — — 无论是基于神经的预测还是两级分支预测的变体 — — 提供了更好的预测准确性,但是它们消耗的动力和复杂性也成倍增加。 此外,在复杂的预测技术中,预测分支所需的时间也非常长 — — 从2到5个周期不等 — — 这与实际分支的执行时间相当。 分支预测基本上是一个优化(最小化 ) 问题, 重点是实现尽可能最低的误用率、低电耗和最低资源低的复杂度。
确实有三种不同的分支:
附加条件的前进分支 - 根据运行时间条件, PC (程序反) 被修改为指示流中前方的地址 。
后向有条件的分支 - PC 被修改为指令流中的后向点。 分支基于某些条件, 例如当循环结尾的测试显示循环应该再次执行时, 将程序循环的起始处向后转至程序循环的起始处 。
无条件分支 - 包括跳跃、 程序电话和返回等没有特定条件的无条件跳跃指令。 例如, 无条件跳跃指令可能会以组合语言编码为简单的“ jmp ” , 且指令流必须立即被指向跳跃指令指向的目标位置, 而有条件跳跃可能以“ jmpne ” 编码为“ jmpne ” , 只有在对先前“ 比较” 指令中两个数值进行比较的结果显示数值不相等时, 才会改变教学流的方向 。 ( x86 结构使用的分段处理方案增加了额外的复杂性, 因为跳跃可以是“ 接近” (在一段内) , 也可以是“ far”(在段外) 。 每种类型对分支预测算法都有不同的效果 。
静态/动态分支预测:微处理器在第一次遇到有条件的分支时使用静态分支预测,在随后执行有条件的分支代码时使用动态分支预测。
参考文献:
预测处预测处(Ussing回背机器)
其他答复的假设是,一个人需要对数据进行分类是不正确的。
以下代码不排序整个阵列,但只排序其中的200个元素部分,因此运行速度最快。
只排序 k- 元素区域时, 以线性时间( O(n)) 完成预处理, 而不是以 O( n. log(n)) 时间来排序整个数组 。
#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;
}
这个“证明”也与任何算法问题无关, 比如排序顺序, 并且确实是分支预测。
这是肯定的!
部门预测使得逻辑运行速度放慢, 因为代码中的转换会发生! 就像你走一条直街或一条街, 转得很多,
If the array is sorted, your condition is false at the first step: data[c] >= 128, then becomes a true value for the whole way to the end of the street. That's how you get to the end of the logic faster. On the other hand, using an unsorted array, you need a lot of turning and processing which make your code run slower for sure...
看看我在下面为你们创造的图象,哪条街会更快完工?
调
因此,在程序上,分支预测导致过程的慢化...
最后,很高兴知道 我们有两种分支预测 每个分支将对你的代码产生不同的影响:
1. 静态
2. 动态
调
微处理器在第一次遇到有条件分支时使用静态分支预测,在随后执行有条件分支代码时则使用动态分支预测。为了有效编写代码以利用这些规则,在撰写 if-else 或 开关 语句时,先检查最常见的情况,然后逐步工作到最不常见的情况。循环不一定要求固定分支预测使用任何特殊的代码顺序,因为通常只使用循环迭代器的条件。
我用MATLAB 2011b 和我的MacBook Pro(Intel i7, 64位, 2.4 GHz) 尝试了以下MATLAB 代码的相同代码 :
% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);
%Sort the data
data1= sort(data); % data1= data when no sorting done
%Start a stopwatch timer to measure the execution time
tic;
for i=1:100000
for j=1:arraySize
if data1(j)>=128
sum=sum + data1(j);
end
end
end
toc;
ExeTimeWithSorting = toc - tic;
上述MATLAB代码的结果如下:
a: Elapsed time (without sorting) = 3479.880861 seconds.
b: Elapsed time (with sorting ) = 2377.873098 seconds.
校对:Soup
a: Elapsed time (without sorting) = 19.8761 sec.
b: Elapsed time (with sorting ) = 7.37778 sec.
基于这一点,看来MATLAB比C执行慢了175倍,没有分类,比C执行慢了350倍,换言之,(分支预测)MATLAB执行效果为1.46x,C执行效果为2.7x。
