为什么 std::vector::push_back 比手动实施慢得多？
why std::vector::push_back much slower than a manual implementation?
我想写一个trivial类型的动态数组（然后我可以用memcpy或sth来优化），但是当我将它的效率与std::vector进行比较时，我发现它的push_back功能是效率是 std::vector.
的两倍
太奇怪了，我阅读了MSVC STL的源代码来寻找原因，但没有成功。
我的代码：
template<typename T>
class Array {
static_assert((std::is_trivial_v<T>), "Array requires type to be trivial.");
T* m_p;
size_t m_cap, m_siz;
private:
void increase(size_t new_cap) {
ASSERT(new_cap > m_cap);
if (new_cap < m_cap + m_cap / 2)new_cap = m_cap + m_cap / 2;
T* new_p = (T*)realloc(m_p, sizeof(T) * new_cap);
ASSERT(new_p);
m_p = new_p;
m_cap = new_cap;
}
public:
Array() : m_siz(0), m_cap(0), m_p(nullptr) {}
~Array() { if (m_p)free(m_p); }
Array(const Array& x) {
m_cap = m_siz = x.m_siz;
m_p = (T*)malloc(sizeof(T) * m_siz);
memcpy(m_p, x.m_p, sizeof(T) * m_siz);
}
Array(Array&& x) {
m_cap = x.m_cap;
m_siz = x.m_siz;
m_p = x.m_p;
x.m_p = nullptr;
x.m_cap = x.m_siz = 0;
}
Array& operator=(const Array& x) {
m_cap = m_siz = x.m_siz;
m_p = (T*)malloc(sizeof(T) * m_siz);
memcpy(m_p, x.m_p, sizeof(T) * m_siz);
}
Array& operator=(Array&& x) {
m_cap = x.m_cap;
m_siz = x.m_siz;
m_p = x.m_p;
x.m_p = nullptr;
x.m_cap = x.m_siz = 0;
}
void push_back(const T& x) {
if (m_siz == m_cap)increase(m_cap + 1);
m_p[m_siz++] = x;
}
void reserve(size_t cap) {
if (cap > m_cap)
increase(cap);
}
void resize(size_t siz, const T& val = T{}) {
if (siz > m_siz) {
if (siz > m_cap)increase(siz);
for (size_t i = m_siz; i < siz; i++)
m_p[i] = val;
}
m_siz = siz;
}
void shrink_to_fit() {
m_p = realloc(m_p, m_siz * sizeof(T));
m_cap = m_siz;
}
T& operator[](size_t pos) { ASSERT(pos < m_siz); return m_p[pos]; }
const T& operator[](size_t pos) const { ASSERT(pos < m_siz); return m_p[pos]; }
size_t size()const { return m_siz; }
size_t capacity()const { return m_cap; }
void clear() { m_siz = 0; }
};
#define N 10000
#define M 100000
template<typename T>
int test() {
int t = clock();
T v;
v.reserve(M);
for (int t = 0; t < N; t++) {
for (int i = 0; i < M; i++)
v.push_back(i);
//v.resize(M);
//for (int i = 0; i < M; i++)
//v[i] = -i;
v.clear();
}
return clock() - t;
}
int main() {
int t1 = test<std::vector<int>>();
int t2 = test<Array<int>>();
printf("vector:%dms.\nArray:%dms.\n", t1, t2);
}
结果（VS2019版本）：
vector:1043ms.
Array:547ms.
这是 std::vector::pushback(MSVC) 的调用链：
void push_back(const _Ty& _Val) { // insert by moving into element at end, provide strong guarantee
emplace_back(_STD move(_Val));
}
template <class... _Valty>
decltype(auto) emplace_back(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
if (_Mylast != _My_data._Myend) {
return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
}
_Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
#if _HAS_CXX17
return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
(void) _Result;
#endif // _HAS_CXX17
}
template <class... _Valty>
decltype(auto) _Emplace_back_with_unused_capacity(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
_STL_INTERNAL_CHECK(_Mylast != _My_data._Myend); // check that we have unused capacity
_Alty_traits::construct(_Getal(), _Unfancy(_Mylast), _STD forward<_Valty>(_Val)...);
_Orphan_range(_Mylast, _Mylast);
_Ty& _Result = *_Mylast;
++_Mylast;
#if _HAS_CXX17
return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
(void) _Result;
#endif // _HAS_CXX17
}
经过内联和其他优化后，STL 代码似乎与我的代码没有太大区别。
谁能告诉我为什么我的 push_back 更有效率（或者为什么 STL 很慢）？
编辑：
不好意思，我的问题好像引起了误会
我知道 std::vector 是通用的，所以它可能比我做的更多。
但是在 int 类型的 push_back 中，我不认为 std::vector 做了什么特别的事情，所以为什么它很慢？
您的版本仅对普通可复制类型有效。
Because reallocation may involve bytewise copying (regardless of whether it's to expand or to contract), only the objects of TriviallyCopyable types are safe to access in the preserved part of the memory block after a call to realloc.
普通的std::vector比较要求很宽松，只有Destructible in general, and one of CopyInsertable or MoveInsertable对push_back.
由于内存中的不同布局，测量的差异完全有可能是偶然的。布局对性能有很大的影响，除了向量的实现之外，它还会受到很多因素的影响。
我 运行 你在另一个系统上的基准测试，你的矢量完成时间比标准矢量长 31%。不可否认，向量实现是不同的——libstdc++。但这并不意味着 libstdc++ 向量比你的向量快，而你的向量又比 MSVC 向量快。基准测试不够复杂，无法自信地确定这一点。
差异主要是由于 std::vector 版本中的代码生成不太受欢迎。如果我们比较生成的程序集（godbolt link），我们可以看到它。
你的循环（跳过重新分配部分）：
$LL4@test:
xor esi, esi
xor edi, edi
$LL7@test:
mov r15, rbx
cmp rdi, rbx
jne SHORT $LN27@test
<...skip...>
$LN27@test:
mov DWORD PTR [r14+rdi*4], esi
inc rdi
inc esi
cmp esi, 100000 ; 000186a0H
jl $LL7@test
sub r12, r13
jne $LL4@test
std::vector::push_back 循环（再次跳过重新分配部分）：
$LL4@test:
xor ebx, ebx
mov DWORD PTR i[rsp], ebx
$LL7@test:
cmp rcx, QWORD PTR v$[rsp+16]
je SHORT $LN26@test
mov DWORD PTR [rcx], ebx
mov rcx, QWORD PTR v$[rsp+8]
add rcx, 4
mov QWORD PTR v$[rsp+8], rcx
jmp SHORT $LN5@test
$LN26@test:
<...skip...>
$LN5@test:
inc ebx
mov DWORD PTR i[rsp], ebx
cmp ebx, 100000 ; 000186a0H
jl SHORT $LL7@test
mov rcx, QWORD PTR v$[rsp]
mov QWORD PTR v$[rsp+8], rcx
sub rdi, 1
jne SHORT $LL4@test
很明显，我们可以看到更多的代码（热路径中有 11 条指令与 8 条指令）和更多的内存间接寻址（5 条指令与 1 条指令）。所以它变慢也就不足为奇了。
更一般地说，更复杂的代码 == 更慢的代码。
两个版本能不能一样优化？我认为没有理由不这样做。 MSVC 19.28 做不到。
我想写一个trivial类型的动态数组（然后我可以用memcpy或sth来优化），但是当我将它的效率与std::vector进行比较时，我发现它的push_back功能是效率是 std::vector.
太奇怪了，我阅读了MSVC STL的源代码来寻找原因，但没有成功。
我的代码：
template<typename T>
class Array {
static_assert((std::is_trivial_v<T>), "Array requires type to be trivial.");
T* m_p;
size_t m_cap, m_siz;
private:
void increase(size_t new_cap) {
ASSERT(new_cap > m_cap);
if (new_cap < m_cap + m_cap / 2)new_cap = m_cap + m_cap / 2;
T* new_p = (T*)realloc(m_p, sizeof(T) * new_cap);
ASSERT(new_p);
m_p = new_p;
m_cap = new_cap;
}
public:
Array() : m_siz(0), m_cap(0), m_p(nullptr) {}
~Array() { if (m_p)free(m_p); }
Array(const Array& x) {
m_cap = m_siz = x.m_siz;
m_p = (T*)malloc(sizeof(T) * m_siz);
memcpy(m_p, x.m_p, sizeof(T) * m_siz);
}
Array(Array&& x) {
m_cap = x.m_cap;
m_siz = x.m_siz;
m_p = x.m_p;
x.m_p = nullptr;
x.m_cap = x.m_siz = 0;
}
Array& operator=(const Array& x) {
m_cap = m_siz = x.m_siz;
m_p = (T*)malloc(sizeof(T) * m_siz);
memcpy(m_p, x.m_p, sizeof(T) * m_siz);
}
Array& operator=(Array&& x) {
m_cap = x.m_cap;
m_siz = x.m_siz;
m_p = x.m_p;
x.m_p = nullptr;
x.m_cap = x.m_siz = 0;
}
void push_back(const T& x) {
if (m_siz == m_cap)increase(m_cap + 1);
m_p[m_siz++] = x;
}
void reserve(size_t cap) {
if (cap > m_cap)
increase(cap);
}
void resize(size_t siz, const T& val = T{}) {
if (siz > m_siz) {
if (siz > m_cap)increase(siz);
for (size_t i = m_siz; i < siz; i++)
m_p[i] = val;
}
m_siz = siz;
}
void shrink_to_fit() {
m_p = realloc(m_p, m_siz * sizeof(T));
m_cap = m_siz;
}
T& operator[](size_t pos) { ASSERT(pos < m_siz); return m_p[pos]; }
const T& operator[](size_t pos) const { ASSERT(pos < m_siz); return m_p[pos]; }
size_t size()const { return m_siz; }
size_t capacity()const { return m_cap; }
void clear() { m_siz = 0; }
};
#define N 10000
#define M 100000
template<typename T>
int test() {
int t = clock();
T v;
v.reserve(M);
for (int t = 0; t < N; t++) {
for (int i = 0; i < M; i++)
v.push_back(i);
//v.resize(M);
//for (int i = 0; i < M; i++)
//v[i] = -i;
v.clear();
}
return clock() - t;
}
int main() {
int t1 = test<std::vector<int>>();
int t2 = test<Array<int>>();
printf("vector:%dms.\nArray:%dms.\n", t1, t2);
}
结果（VS2019版本）：
vector:1043ms.
Array:547ms.
这是 std::vector::pushback(MSVC) 的调用链：
void push_back(const _Ty& _Val) { // insert by moving into element at end, provide strong guarantee
emplace_back(_STD move(_Val));
}
template <class... _Valty>
decltype(auto) emplace_back(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
if (_Mylast != _My_data._Myend) {
return _Emplace_back_with_unused_capacity(_STD forward<_Valty>(_Val)...);
}
_Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward<_Valty>(_Val)...);
#if _HAS_CXX17
return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
(void) _Result;
#endif // _HAS_CXX17
}
template <class... _Valty>
decltype(auto) _Emplace_back_with_unused_capacity(_Valty&&... _Val) {
// insert by perfectly forwarding into element at end, provide strong guarantee
auto& _My_data = _Mypair._Myval2;
pointer& _Mylast = _My_data._Mylast;
_STL_INTERNAL_CHECK(_Mylast != _My_data._Myend); // check that we have unused capacity
_Alty_traits::construct(_Getal(), _Unfancy(_Mylast), _STD forward<_Valty>(_Val)...);
_Orphan_range(_Mylast, _Mylast);
_Ty& _Result = *_Mylast;
++_Mylast;
#if _HAS_CXX17
return _Result;
#else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv
(void) _Result;
#endif // _HAS_CXX17
}
经过内联和其他优化后，STL 代码似乎与我的代码没有太大区别。
谁能告诉我为什么我的 push_back 更有效率（或者为什么 STL 很慢）？
编辑： 不好意思，我的问题好像引起了误会
我知道 std::vector 是通用的，所以它可能比我做的更多。
但是在 int 类型的 push_back 中，我不认为 std::vector 做了什么特别的事情，所以为什么它很慢？
您的版本仅对普通可复制类型有效。
Because reallocation may involve bytewise copying (regardless of whether it's to expand or to contract), only the objects of TriviallyCopyable types are safe to access in the preserved part of the memory block after a call to
realloc.
普通的std::vector比较要求很宽松，只有Destructible in general, and one of CopyInsertable or MoveInsertable对push_back.
由于内存中的不同布局，测量的差异完全有可能是偶然的。布局对性能有很大的影响，除了向量的实现之外，它还会受到很多因素的影响。
我 运行 你在另一个系统上的基准测试，你的矢量完成时间比标准矢量长 31%。不可否认，向量实现是不同的——libstdc++。但这并不意味着 libstdc++ 向量比你的向量快，而你的向量又比 MSVC 向量快。基准测试不够复杂，无法自信地确定这一点。
差异主要是由于 std::vector 版本中的代码生成不太受欢迎。如果我们比较生成的程序集（godbolt link），我们可以看到它。
你的循环（跳过重新分配部分）：
$LL4@test:
xor esi, esi
xor edi, edi
$LL7@test:
mov r15, rbx
cmp rdi, rbx
jne SHORT $LN27@test
<...skip...>
$LN27@test:
mov DWORD PTR [r14+rdi*4], esi
inc rdi
inc esi
cmp esi, 100000 ; 000186a0H
jl $LL7@test
sub r12, r13
jne $LL4@test
std::vector::push_back 循环（再次跳过重新分配部分）：
$LL4@test:
xor ebx, ebx
mov DWORD PTR i[rsp], ebx
$LL7@test:
cmp rcx, QWORD PTR v$[rsp+16]
je SHORT $LN26@test
mov DWORD PTR [rcx], ebx
mov rcx, QWORD PTR v$[rsp+8]
add rcx, 4
mov QWORD PTR v$[rsp+8], rcx
jmp SHORT $LN5@test
$LN26@test:
<...skip...>
$LN5@test:
inc ebx
mov DWORD PTR i[rsp], ebx
cmp ebx, 100000 ; 000186a0H
jl SHORT $LL7@test
mov rcx, QWORD PTR v$[rsp]
mov QWORD PTR v$[rsp+8], rcx
sub rdi, 1
jne SHORT $LL4@test
很明显，我们可以看到更多的代码（热路径中有 11 条指令与 8 条指令）和更多的内存间接寻址（5 条指令与 1 条指令）。所以它变慢也就不足为奇了。
更一般地说，更复杂的代码 == 更慢的代码。
两个版本能不能一样优化？我认为没有理由不这样做。 MSVC 19.28 做不到。