这是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
当对数组进行排序时,数据在 0 至 255 之间分布,因此,约前半段的迭代将不输入 " 如果 " 报表(如果在下文中共享语句)。
if (data[c] >= 128)
sum += data[c];
问题是: 是什么使上述语句在某些情况下无法执行, 如分类数据那样? 这里出现了“ 分支预测器 ” 。 分支预测器是一个数字电路, 试图猜出分支( 如当日电子结构 ) 将走哪条路, 然后再确定这一点。 分支预测器的目的是改善教学管道的流量 。 分支预测器在实现高效运行方面发挥着关键作用 !
让我们做一些板凳标记 来更好理解它
如果情况总是真实的,或者总是虚假的,处理器中的分支预测逻辑会抓住这个模式。 另一方面,如果情况无法预测,那么如果情况说明会更昂贵。
让我们用不同的条件来衡量这个循环的性能:
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
“坏”真实假象模式可以使虚报速度比“好”模式慢六倍! 当然,哪种模式是好的,哪一种模式不好,取决于汇编者产生的准确指示和具体的处理器。
因此,部门预测对业绩的影响是毫无疑问的!
官方的回答是来自
英特尔 -- -- 避免误用英特尔分公司的成本 -- -- 分公司和循环重组以防止误用科学论文 -- -- 分公司预测计算机建筑书籍:J.L. Hennessy, D.A. Patterson:计算机结构:定量方法 科学出版物中的文章:T.Y. Yeh, Y.N. Patt在分支预测方面做了许多这些。
你也可以从这张可爱的图表中看到 树枝预测器为什么会被混淆。
调
原始代码中的每个元素都是随机值
data[c] = std::rand() % 256;
所以预测器会随着 : rand () 的打击而改变两边。
另一方面,一旦对预测进行分类, 预测器将首先进入一个 强烈未被采纳的状态, 当值变化到高值时, 预测器将分三步走, 从强烈未被采纳到强烈被采纳。
这是肯定的!
部门预测使得逻辑运行速度放慢, 因为代码中的转换会发生! 就像你走一条直街或一条街, 转得很多,
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 或 开关 语句时,先检查最常见的情况,然后逐步工作到最不常见的情况。循环不一定要求固定分支预测使用任何特殊的代码顺序,因为通常只使用循环迭代器的条件。
其他答复的假设是,一个人需要对数据进行分类是不正确的。
以下代码不排序整个阵列,但只排序其中的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;
}
这个“证明”也与任何算法问题无关, 比如排序顺序, 并且确实是分支预测。
