vector 初始化与否导致的巨大性能差异
共 607字，需浏览 2分钟
·
2022-06-08 15:19
最近在优化引擎代码，在优化的过程中发现一个很奇怪的问题，一个简单的对象，存放在std::vector<> v中，如果v定义的时候为每个元素指定初值，那么后面对v中每个元素的写就飞快；相反的，如果v定义的时候，不指定初始值，那么后面对v中元素写操作的时候，就花费大约前一种2-3倍的时间。
今天，借助此文，分享下原因的排查过程。
问题
为了能够快速说明问题，直接上代码吧，如下：
#include
#include
#include
#include
int const num = 1000000000;
struct AdItem
{
AdItem() {}
AdItem(int x, int y, int z)
{
x_ = x; y_ = y; z_ = z;
}
int x_;
int y_;
int z_;
};
void time_report(const std::function<void()> &f1, const std::function<void()> &f2) {
auto start = std::chrono::high_resolution_clock::now();
f1();
auto end = std::chrono::high_resolution_clock::now();
std::cout << "allocation done in " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "ms" << std::endl;
start = std::chrono::high_resolution_clock::now();
f2();
end = std::chrono::high_resolution_clock::now();
std::cout << "assignment done in " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "ms" << std::endl;
}
void uninitialized_performance() {
std::vectorv;
time_report([&v]() { v.reserve(num); },
[&v]() {
for (int i = 0; i < num; ++i) {
v[i] = {i + 2, i + 4, i + 6};
} });
}
void initialized_performance() {
std::vectorv;
time_report([&v]() { v.assign(num, AdItem{0, 0, 0}); },
[&v]() {
for (int i = 0; i < num; ++i) {
v[i] = {i + 2, i + 4, i + 6};
} });
}
int main()
{
uninitialized_performance();
initialized_performance();
return 0;
}
程序输出如下：
allocation done in 0ms
assignment done in 59ms
allocation done in 46ms
assignment done in 27ms
无论使用-g -O2 -O3都是一样的效果，执行多次结果仍然一样。
CPU Cache
CPU缓存（CPU Cache）位于CPU与内存之间的临时存储器，它的容量比内存小但交换速度快。在缓存中的数据是内存中的一小部分，但这一小部分是短时间内CPU即将访问的，当CPU调用大量数据时，就可避开内存直接从缓存中调用，从而加快读取速度。
在CPU中加入缓存是一种高效的解决方案，这样整个内存储器（缓存+内存）就变成了既有缓存的高速度，又有内存的大容量的存储系统了。缓存对CPU的性能影响很大，主要是因为CPU的数据交换顺序和CPU与缓存间的带宽引起的。
看到结果以后，第一反应是CPU Cache导致，因为占用的内存大小一样，所以怀疑在第二次访问的时候，因为CPU Cache中已经有缓存，所以直接使用。
为了确认是否是因为CPU Cache而导致的性能差异，所以将测试分成两个独立的程序进行，即分别执行uninitialized_performance()和initialized_performance()函数，结果与之前的一致，所以排除CPU Cache的原因。
perf工具
perf是用来进行软件性能分析的工具,可以利用PMU、tracepoint和内核中的特殊计数器来进行性能统计，用来分析内核和应用程序的性能。
使用perf stat uninitialized_performance结果如下：
Performance counter stats for 'uninitialized_performance':
47.923956 task-clock (msec) # 0.985 CPUs utilized
6 context-switches # 0.125 K/sec
0 cpu-migrations # 0.000 K/sec
1,007 page-faults # 0.021 M/sec
99,354,240 cycles # 2.073 GHz (83.33%)
72,689,011 stalled-cycles-frontend # 73.16% frontend cycles idle (83.46%)
48,738,086 stalled-cycles-backend # 49.05% backend cycles idle (66.66%)
98,377,529 instructions # 0.99 insn per cycle
# 0.74 stalled cycles per insn (83.32%)
11,399,060 branches # 237.857 M/sec (83.39%)
19,617 branch-misses # 0.17% of all branches (83.16%)
使用perf stat initialized_performance结果如下：
76.092443 task-clock (msec) # 0.991 CPUs utilized
6 context-switches # 0.079 K/sec
0 cpu-migrations # 0.000 K/sec
1,007 page-faults # 0.013 M/sec
157,742,162 cycles # 2.073 GHz (82.94%)
110,940,710 stalled-cycles-frontend # 70.33% frontend cycles idle (82.96%)
72,531,622 stalled-cycles-backend # 45.98% backend cycles idle (65.92%)
178,142,743 instructions # 1.13 insn per cycle
# 0.62 stalled cycles per insn (82.99%)
31,488,875 branches # 413.824 M/sec (84.01%)
24,309 branch-misses # 0.08% of all branches (84.17%)
因为perf只能得到整个程序执行期间的变化，而我们实际上需要的是核心部分，看来通过perf得到有用的信息，只能另寻他法。
源码跟踪
截止到现在，上述方案都没能解答本次问题的疑问，只能祭出屠龙刀，看源码了。
未初始化版调用信息如下：
-> std::vectorstd::allocator >::vector
--> std::vectorstd::allocator >::_M_default_initialize
---> std::__uninitialized_default_n_aunsigned long, AdItem>
----> std::__uninitialized_default_nunsigned long>
-----> std::__uninitialized_default_n_1<false>::__uninit_default_nunsigned long>
------> std::_Construct(std::__addressof(*__cur))
初始化版调用信息如下：
-> std::vector >::vector
--> std::vector >::_M_fill_initialize
---> std::__uninitialized_fill_n_a
----> std::uninitialized_fill_n
-----> std::__uninitialized_fill_n<false>::__uninit_fill_n
------> std::_Construct(std::__addressof(*__cur), __x)
从上述函数调用信息可以看出，初始化版本和都调用了std::_Construct函数，而该函数通过其名称就能看到，是调用了构造函数对内存块进行构造(底层是用placement new实现)，得不到我们有用的信息。
汇编
下面我们从汇编角度来看下(为了篇幅，去掉了无关紧要的部分以及相同的部分)。
未初始化版本：
uninitialized_performance():
mov QWORD PTR [rsp+104], OFFSET FLAT:std::_Function_handler::_M_invoke(std::_Any_data const&)
mov QWORD PTR [rsp+80], rax
mov QWORD PTR [rsp+96], OFFSET FLAT:std::_Function_base::_Base_manager::_M_manager(std::_Any_data&, std::_Any_data const&, std::_Manager_operation)
mov QWORD PTR [rsp+48], rax
mov QWORD PTR [rsp+72], OFFSET FLAT:std::_Function_handler::_M_invoke(std::_Any_data const&)
mov QWORD PTR [rsp+64], OFFSET FLAT:std::_Function_base::_Base_manager::_M_manager(std::_Any_data&, std::_Any_data const&, std::_Manager_operation)
初始化版本：
initialized_performance():
mov QWORD PTR [rsp+64], rsp
mov QWORD PTR [rsp+88], OFFSET FLAT:std::_Function_handler::_M_invoke(std::_Any_data const&)
mov QWORD PTR [rsp+80], OFFSET FLAT:std::_Function_base::_Base_manager::_M_manager(std::_Any_data&, std::_Any_data const&, std::_Manager_operation)
mov QWORD PTR [rsp+32], rsp
mov QWORD PTR [rsp+56], OFFSET FLAT:std::_Function_handler::_M_invoke(std::_Any_data const&)
mov QWORD PTR [rsp+48], OFFSET FLAT:std::_Function_base::_Base_manager::_M_manager(std::_Any_data&, std::_Any_data const&, std::_Manager_operation)
从上述汇编结果没看到有什么区别，所以排除了语言层面的区别了，尝试从其它方面进行分析。
lazy allocation
既然源码和汇编都看不出来区别，那么只能从另外一个方向来进行考虑，那就是内存分配，有没有可能虽然是都调用了new进行内存分配，但是实际上并没有分配呢？
记得之前看过一些文章，说是操作系统有个lazy allocation（延迟分配）机制，即用户调用API进行内存分配的时候，操作系统并不会直接分配给用户这么多内存，而是直到用户真的访问了申请的page时产生一个page falut，然后将这个page真的分配给用户，并重新执行产生page fault的语句。
我们使用以下例子进行验证：
#include
struct X {
int x_[1 << 24];
};
int main() {
auto x = new X;
sleep(100);
return 0;
}
然后通过htop -p xxx命令查看信息，如下：
然后，我们尝试将代码进行修改如下：
#include
#include
struct X {
int x_[1 << 24];
};
int main() {
auto x = new X;
memset(x->x_, 0, sizeof(x->x_)); // 增加了该句，仅仅为了访问
sleep(100);
return 0;
}
如下所示：
通过上述htop的输出信息的RES块可以看出，第二次调用分配了足够的虚拟内存，这就验证了我们这次的结论，即使使用了new，在真正使用之前是没有被真正的分配虚拟内存。
Lazy allocation simply means not allocating a resource until it is actually needed. This is common with singleton objects, but strictly speaking, any time a resource is allocated as late as possible, you have an example of lazy allocation.
By delaying allocation of a resource until you actually need it, you can decrease startup time, and even eliminate the allocation entirely if you never actually use the object. In contrast, you could pre-allocate a resource you expect to need later, which can make later execution more efficient at the expense of startup time, and also avoids the possibility of the allocation failing later in program execution.
现在，我们从lazy allocation角度来分析该问题。对于未初始化的vector，该vector申请了一大块内存，operator new只是返回了虚拟地址(此时并未将物理地址与其关联)，当具体访问数据(for循环)的时候，操作系统才会将虚拟地址与物理地址进行关联。
而在构造时给初值，算是访问大块连续逻辑空间，操作系统会将虚拟地址与物理地址相关联，这样在后面访问的时候，因为已经访问了一次了，所以会很快。
在源码一节中，我们提到未初始化版本和初始化版本最终分别调用了std::_Construct(std::__addressof(*__cur))和_Construct(std::__addressof(*__cur), __x)，下面是其具体实现。
未初始化版本：
template<typename _T1, typename... _Args>
inline void
_Construct(_T1* __p, _Args&&... __args) {
::new(static_cast<void*>(__p)) _T1(std::forward<_Args>(__args)...);
}
初始化版本如下：
inline void
_Construct(_T1* __p, const _T2& __value) {
::new(static_cast<void*>(__p)) _T1(__value);
}
std::_Construct是在std::vector<>定义中进行调用的，也就是说都访问了对应的地址，但是为什么区别这么大呢？后面，对示例代码进行了修改：
AdItem() {
x_ = 0; y_ = 0; z_ = 0;
} AdItem() = default;lazy allocation引起的性能差异。结语
开发过程，就是一个不断采坑的过程，从一个坑到另一个坑，技术才能成长。
- EOF -