std::vector의 최적화

Naezan·2024년 4월 20일

C++

목록 보기

3/5

std::vector

벡터는 동적배열(dynamic array) 컨테이너 클래스로 배열의 크기를 런타임에서 동적으로 조절할 수 있다는 장점이 있습니다.
그리고 기본적으로 배열의 각 요소가 메모리 상에 연속적으로 있고 random access(임의 접근또는 무작위 접근)을 지원하기 때문에, 임의의 위치에 있는 요소에 대해 operator[]를 이용하여 O(1)의 시간으로 액세스가 가능합니다.

vector 요소 추가

vector의 최적화는 요소를 추가하는 상황에서 발생합니다.

struct Elem
{
	Elem(int t) { cout << "Constructor" << endl; }
	Elem(const Elem& Copy) { cout << "Copy Constructor" << endl; }
	Elem(Elem&& Move) {cout << "Move Constructor" << endl; }
};

vector<Elem> vec;
vec.push_back(Elem(1));
vec.push_back(Elem(2));
vec.push_back(Elem(3));
vec.push_back(Elem(4));
vec.push_back(Elem(5));

위 코드는 vector의 가장 간단한 사용법입니다. Elem의 구조체를 vector의 push_back을 통해 한개씩 추가하고 있습니다.

위 코드를 실행하면 아래와 같은 결과가 나옵니다.

각각 생성자를 호출하고 있지만 요소를 추가하면서 이동생성자와 복사생성자가 불필요하게 호출되고 있습니다.

복사생성자에서 수행하는 복사는 메모리를 추가로 할당하고 할당된 메모리에 복사를 수행하기때문에 많이 호출할수록 성능에 안좋은 영향을 줄 수 있습니다.

왜 복사 생성자가 호출되는가?

복사생성자가 호출되는 이유는 생각보다 간단합니다.

push_back을 하는 내부 코드에서 현재 할당받은 메모리의 마지막 위치와 요소의 마지막 위치를 비교하여(정확히는 반복자의 end()처럼 마지막 요소의 뒤) 할당할 공간이 없으면 필요한 메모리 공간을 재할당한 뒤 복사생성자를 이용하여 복사를 수행하게 됩니다.

pointer& _Mylast = _My_data._Mylast;
if (_Mylast != _My_data._Myend) {
	// 다르다면 할당할 수 있는 공간이 있기 때문에 복사 생성X
	}
// 같다면 추가로 공간을 할당해야하기 때문에 복사 생성자 호출

그리고 재할당하는 공간의 크기는 capacity에 의해 결정되는데 capacity는 std::vector 내부 _Calculate_growth(const size_type _Newsize) 함수에 의해서 결정됩니다.

    _CONSTEXPR20 size_type _Calculate_growth(const size_type _Newsize) const {
        const size_type _Oldcapacity = capacity();

        if (_Oldcapacity > _Max - _Oldcapacity / 2) {
            return _Max; // _Max는 할당할 수 있는 최대크기
        }

		// 새롭게 만들 Capacity의 크기로 기존의 크기의 1.5배를 할당합니다.
        const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;
        if (_Geometric < _Newsize) {
            return _Newsize; // _Newsize는 현재 배열의 크기 + 1입니다.
            /*const size_type _Newsize = _Oldsize + 1;*/
        }

        return _Geometric;
    }

즉 호출할때마다 capacity가 부족하여 복사생성자가 호출되는 구조를 띄게 되는 상태가 되는 것입니다.

복사 생성자의 호출 막기

복사 생성자의 호출을 막으려면 capacity를 조절해야한다는 것을 알았습니다. 그렇기 때문에capacity를 조절해주는 reserve함수를 통해 미리 Elem의 메모리 공간을 할당해주면 됩니다.

	vector<Elem> vec;
	vec.reserve(5);
	vec.push_back(Elem(1));
	vec.push_back(Elem(2));
	vec.push_back(Elem(3));
	vec.push_back(Elem(4));
	vec.push_back(Elem(5));

reserve를 통해 vector가 사용할 메모리 공간을 미리 확보해놓기 때문에 추가적인 복사가 일어나지 않게 됩니다.

이동 생성자의 호출 막기

하지만 아직 뭔가 아쉽습니다. 복사생성자의 호출을 최소화했으나 push_back을 통한 이동 생성자가 호출되고 있습니다.

push_back

_CONSTEXPR20 void push_back(_Ty&& _Val) {
    // insert by moving into element at end, provide strong guarantee
    _Emplace_one_at_back(_STD move(_Val));
}

이동생성자가 호출되는 이유는 push_back은 내부에서 std::move를 통해 이동연산을 수행합니다.
그리고 이동된 값을 _Emplace_one_at_back를 통해 vector에 추가하게 됩니다.

_EXPORT_STD template <class _Ty>
_NODISCARD _MSVC_INTRINSIC constexpr remove_reference_t<_Ty>&& move(_Ty&& _Arg) noexcept {
    return static_cast<remove_reference_t<_Ty>&&>(_Arg);
}

std::move는 해당 값을 rvalue reference로 캐스팅해주는 단순한 연산입니다. 예시 코드에선 static_cast<Elem&&>(임시객체);와 동일하게 동작을 합니다.

또한 Elem()으로 생성된 객체는 xvalue(expiring value의 약자로 해당 값이 소멸될 것임을 나타내는 값입니다) 이기 때문에 xvalue는 std::move에 전달 시 rvalue reference의 형태로 전달됩니다.

emplace_back

이때 임시객체의 생성을 막고 생성자의 호출만으로 해결할 수 있는데, vector의 emplace_back을 이용하면됩니다.

	vector<Elem> vec;
	vec.reserve(5);
	vec.emplace_back(1);
	vec.emplace_back(2);
	vec.emplace_back(3);
	vec.emplace_back(4);
	vec.emplace_back(5);

push_back과 emplace_back은 내부에서 std::_Default_allocator_traits<std::allocator<Elem> >::construct<Elem,?> 형태의 함수를 호출하는데 이때 ?에 들어갈 값에 따라 생성자와 이동생성자의 호출이 분기됩니다.

push_back은 Elem의 값을 넣어주었기에 std::_Default_allocator_traits<std::allocator<Elem> >::construct<Elem,Elem> 이 호출되면서 이동 생성자가 호출되고 emplace_back은 1~5의 값을 넣어주었기에 std::_Default_allocator_traits<std::allocator<Elem> >::construct<Elem,int> 가 호출되면서 생성자가 호출되게 됩니다.
즉 emplace_back을 이용하면 생성자만 호출할 수 있는 것입니다.

마무리하며

vector의 최적화에 대해 공부하다보니 어셈블리어까지 하나하나 뜯어보면서 공부하게 되었습니다.
맨 처음에는 단순히 emplace_back만 호출하면 해결되겠지라고 생각하면서 시작했는데, 문득 이 문제의 원인이 궁금했고 그러다보니 더 깊게...더 깊게 들어가게 되었습니다.

이 글을 적으면서 vector, vector의 capacity처럼 단순한 개념부터 어셈블리어, std::move, std::forward, l&rvalue에 까지 다양한 지식을 배워야 했습니다.

당장은 비효율적인 공부일지라도 이렇게 공부하는게 재밌기도 합니다. 지식을 습득하는데 많은 시간이 걸렸지만 하나를 이해하기 위해서 다른 모든 내용을 다 공부하는 과정이 저를 몰입하게하고 빠져들게하는 것 같습니다.

피드백은 언제나 환영입니다! 긴 글 읽어주셔서 감사합니다.