预先排序条件
假如有以下for循环，for内部有if-else分支判断
1
2
3
4
5
6
7
8
9
10
|
for(int i = 0; i < task_size; ++i)
{
if(tasks[i].condi > 128)
{
tasks[i].RunPro1();
}else
{
tasks[i].RunPro2();
}
}
|
其中判断条件也是一个数组，那么可以通过预先将判断条件进行排序，让进入循环前条件数组已经是一个有序的数组。有序的条件数组可以提高分支预测的准确率
1
2
3
4
5
6
7
8
9
10
11
|
std::sort(tasks_sorted.begin(), tasks_sorted.end(), [](const Task& t1, const Task& t2){ return t1.condi < t2.condi;});
for(int i = 0; i < task_size; ++i)
{
if(tasks_sorted[i].condi < 128)
{
tasks_sorted[i].RunPro2();
}else
{
tasks_sorted[i].RunPro1();
}
}
|
但此方法需要注意一个问题： 排序也是占用时间消耗的，所以需要判断循环内的处理是否比较复杂是否耗时长，足以抵消预先排序带来的消耗，如果排序耗时比for循环内部处理都要长了则无需考虑这个优化方法。
测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
/**
* @file loop_for01.cpp
* @author mango ([email protected])
* @brief 高性能优化-分支预测-for循环
* @version 0.1
* @date 2022-05-18
*
* @copyright Copyright (c) 2022
*
*/
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <thread>
#include <iostream>
struct Task
{
int condi;
std::vector<double> vec;
void RunPro1()
{
//复杂运算
std::sort(vec.begin(), vec.end());
};
void RunPro2()
{
std::cout << vec.size() << std::endl;
};
};
int main(int argc, char** argv)
{
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dist(0, 255);
std::uniform_real_distribution<double> dist2(10.0f, 1000.0);
const size_t task_size = 1e3;
std::vector<Task> tasks(task_size);
for(int i = 0; i < task_size; ++i)
{
tasks[i].condi = dist(gen);
for(int j = 0; j < 10000; j++)
{
tasks[i].vec.push_back(dist2(gen));
}
}
auto tasks_sorted = tasks;
auto t0 = std::chrono::system_clock::now();
std::sort(tasks_sorted.begin(), tasks_sorted.end(), [](const Task& t1, const Task& t2){ return t1.condi < t2.condi;});
auto t1 = std::chrono::system_clock::now();
for(int i = 0; i < task_size; ++i)
{
if(tasks_sorted[i].condi < 128)
{
tasks_sorted[i].RunPro2();
}else
{
tasks_sorted[i].RunPro1();
}
}
auto t2 = std::chrono::system_clock::now();
for(int i = 0; i < task_size; ++i)
{
if(tasks[i].condi > 128)
{
tasks[i].RunPro1();
}else
{
tasks[i].RunPro2();
}
}
auto t3 = std::chrono::system_clock::now();
auto dt1 = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
auto dt2 = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
auto dt3 = std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count();
std::cout << "sort cost "<< dt1 << " us"<< std::endl;
std::cout << "dt1 = "<< dt2 << " us"<< std::endl;
std::cout << "dt2 = "<< dt3 << " us"<< std::endl;
return 0;
}
|
