[C++] vector 는 2배씩 늘어나는게 맞을까?
개요
벡터는 용량이 부족하면 더 큰 용량을 할당한 뒤 그곳으로 복사를 한다고 다들 알고 있을 겁니다. 여기서 더 큰 용량 을 생각할 때 '벡터는 당연히 2배씩 용량 늘어나겠지' 싶었습니다.
그런데 일을하면서 사수분이 생겼고 이 사수분이 이런 논제를 하나 던져줬습니다. '진짜 2배씩 늘어나는지 찍어보셨나요?'. 이걸 듣고 핫차 싶어서 시간 날 때 바로 테스트를 해보기로 했습니다.
결론은 마냥 2배는 아니다.
그냥 간단하게 2, 4, 8...등으로 늘어날 수 있게 유도해 봤습니다. 코드는 아래 접은 글에 있습니다.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec;
cout << "===============\n";
cout << "vector size : " << vec.size() << '\n';
cout << "vector capacity : " << vec.capacity() << '\n';
//...
vec.push_back(0);
//...
cout << "===============\n";
cout << "vector size : " << vec.size() << '\n';
cout << "vector capacity : " << vec.capacity() << '\n';
//...
for(int i = 0; i < 2; i++)
vec.push_back(0);
//...
cout << "===============\n";
cout << "vector size : " << vec.size() << '\n';
cout << "vector capacity : " << vec.capacity() << '\n';
//...
for(int i = 0; i < 2; i++)
vec.push_back(0);
//...
cout << "===============\n";
cout << "vector size : " << vec.size() << '\n';
cout << "vector capacity : " << vec.capacity() << '\n';
//...
for(int i = 0; i < 4; i++)
vec.push_back(0);
//...
cout << "===============\n";
cout << "vector size : " << vec.size() << '\n';
cout << "vector capacity : " << vec.capacity() << '\n';
//...
for(int i = 0; i < 8; i++)
vec.push_back(0);
//...
cout << "===============\n";
cout << "vector size : " << vec.size() << '\n';
cout << "vector capacity : " << vec.capacity() << '\n';
}
일단 GCC 6.3.0 버전의 컴파일러가 있는 VS Code에서 실행해 봤습니다.
조금 재미없게도 2의 배수대로 늘어나는 모습을 볼 수 있었습니다. 여기서 '내 환경은 다 2배인가?' 했습니다.
그런데 Visual Studio의 C++14 버전 컴파일러 환경에서 하면 1, 3, 6, 9, 19... 등으로 뭔가 신기하게 늘어나는 모습을 볼 수 있습니다. 확실한 건 2의 배수로 증가하지 않는다는 걸 알 수 있습니다.
template <class... _Valty>
_CONSTEXPR20 pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) {
// reallocate and insert by perfectly forwarding _Val at _Whereptr
_Alty& _Al = _Getal();
auto& _My_data = _Mypair._Myval2;
pointer& _Myfirst = _My_data._Myfirst;
pointer& _Mylast = _My_data._Mylast;
_STL_INTERNAL_CHECK(_Mylast == _My_data._Myend); // check that we have no unused capacity
const auto _Whereoff = static_cast<size_type>(_Whereptr - _Myfirst);
const auto _Oldsize = static_cast<size_type>(_Mylast - _Myfirst);
if (_Oldsize == max_size()) {
_Xlength();
}
const size_type _Newsize = _Oldsize + 1;
const size_type _Newcapacity = _Calculate_growth(_Newsize);
const pointer _Newvec = _Al.allocate(_Newcapacity);
const pointer _Constructed_last = _Newvec + _Whereoff + 1;
pointer _Constructed_first = _Constructed_last;
_TRY_BEGIN
_Alty_traits::construct(_Al, _Unfancy(_Newvec + _Whereoff), _STD forward<_Valty>(_Val)...);
_Constructed_first = _Newvec + _Whereoff;
if (_Whereptr == _Mylast) { // at back, provide strong guarantee
if constexpr (is_nothrow_move_constructible_v<_Ty> || !is_copy_constructible_v<_Ty>) {
_Uninitialized_move(_Myfirst, _Mylast, _Newvec, _Al);
} else {
_Uninitialized_copy(_Myfirst, _Mylast, _Newvec, _Al);
}
} else { // provide basic guarantee
_Uninitialized_move(_Myfirst, _Whereptr, _Newvec, _Al);
_Constructed_first = _Newvec;
_Uninitialized_move(_Whereptr, _Mylast, _Newvec + _Whereoff + 1, _Al);
}
_CATCH_ALL
_Destroy_range(_Constructed_first, _Constructed_last, _Al);
_Al.deallocate(_Newvec, _Newcapacity);
_RERAISE;
_CATCH_END
_Change_array(_Newvec, _Newsize, _Newcapacity);
return _Newvec + _Whereoff;
}
VS 에서 C++17 기준으로 뽑아봤을 때 _NewCapacity는 (현재 사이즈 + 1)에서 _Calculate_growth를 호출한 형태입니다.
_CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
// given _Oldcapacity and _Newsize, calculate geometric growth
const size_type _Oldcapacity = capacity();
const auto _Max = max_size();
if (_Oldcapacity > _Max - _Oldcapacity / 2) {
return _Max; // geometric growth would overflow
}
const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
if (_Geometric < _Newsize) {
return _Newsize; // geometric growth would be insufficient
}
return _Geometric; // geometric growth is sufficient
}
해당 함수를 보면 인자로 들어온 _NewSize(이전 사이즈 + 1) 또는 이전 capacity에서 50% 증가 한 사이즈로 capacity를 잡는 것을 볼 수 있습니다. 아마 50% 증가인데 _NewSize와 비교하는 건 아무것도 없는, size, capacity 둘 다 0인 경우에 해당하는 것으로 보입니다.
때문에 마냥 2배로 늘어나는게 아니라 다양한 방식으로 늘어난다 나는걸 알 수 있습니다. 그나저나 이렇게 되면 나중에 reserve를 잘해야겠네요. 50% 늘어나는 거 잘못 잡으면 복사에 비용을 다 빼앗길 테니깐요.