References
- Ch 9, The Art of Writing Efficient Programs
Contents
- Move Semantics
- RVO (Return Value Optimization), Named RVO (NRVO)
- How to Avoid (Unnecessary) Copying
- Unnecessary Memory Allocations
- Memory Management in Concurrent Programs
- Optimization of Conditional Execution
이번 포스팅에서는 C++에서 고효율의 코드를 작성하는 방법에 대해서 살펴보고, 수행하고자 하는 작업을 명확하게 표현하는 코드를 작성하는 것에 대해서 살펴본다.
포스팅에서 사용된 전체 코드는 링크에서 확인할 수 있다.
Unnecessary Copying
객체에 대한 불필요한 복사는 C++을 비효율적으로 만드는 첫 번째 문제이며, 이는 발생하기는 쉬우나 발견하기는 어려울 수 있다. 아래 코드를 살펴보자.
std::vector<int> v = make_v(... args ...);
do_work(v);위 코드에서 벡터 v의 복사가 몇 번 발생 횟수는 make_v() 함수와 do_work() 함수의 세부 구현과 컴파일러 최적화에 따라서 다를 것이다. 몇 가지 예제를 통해 이 미묘한 차이를 살펴보자.
Copying and Argument Passing
do_work()의 구현 예제부터 살펴보자. 사실, 선언이 가장 중요하므로 함수 내부 구현은 생략하도록 한다.
먼저 함수가 인수를 레퍼런스로 전달 받는 경우에는 const 여부와 상관없이 복사본이 생성되지 않는다.
void do_work(std::vector<int>& vr) {
... vr is a reference to v ...
}만약 함수가 pass-by-value(값으로 전달)을 사용하면 복사가 반드시 발생하게 된다.
void do_work(std::vector<int> vc) {
... vc is a copy of v ...
}벡터를 복사하는 것은 벡터의 크기가 클 때 아주 큰 비용이 드는 작업이다. 수행하고자 하는 작업 자체가 벡터의 복사본이 필요없는 경우에는 매우 비효율적이게 된다 (예를 들어, 벡터의 있는 모든 요소의 합을 구하는 작업). 복사본이 생성되는지 여부를 알려주지 않기 때문에 복사본을 만드는 결정은 기능을 구현하는 자에게 책임이 있으며, 이는 요구 사항과 알고리즘을 고려하고 난 후에 결정될 수 있다. 모든 요소의 합을 구하는 작업의 경우에는 다음과 같이 (const) reference로 벡터를 전달하는 것이 좋다.
void do_work(std::vector<int> const& v) {
int sum = 0;
for (int x : v) sum += x;
... use sum ...
}
C++11에서는 불필요한 복사를 일부분 제거하기 위해 이동 의미론(move semantics)을 도입했다. 함수의 인수가 rvalue(우측값)이라면 이를 변경하는 것을 포함하여 원하는 방식으로 사용할 수 있다. 이를 활용하는 일반적인 방법은 rvalue reference를 사용하여 오버로딩하는 것이다.
void do_work(std::vector<int>&& v) {
... can alter v data ...
}
do_work(std::vector<int>(...)); // rvalue위 함수에 rvalue 벡터를 전달하면 이름이 지정되지 않은 임수 값을 사용하게 된다. 벡터에는 이동 생성자(move constructor)가 있어서 함수로 전달되는 인수는 복사되지 않고 단지 이동되어 함수 내부에서 사용된다.
Copying as An Implementation Technique
간단한 코드를 통해 복사와 관련된 두 가지 구현의 성능을 벤치마크를 통해 비교해보자.
예를 들어, 정렬된 순서로 벡터를 출력하는 아래 함수를 고려해보자.
template<typename T>
void print_sorted1(std::vector<T> v) {
std::sort(v.begin(), v.end());
// disable the actual printing since we are not interested in benchmarking the I/O
if (rand() < 0) for (T x: v) std::cout << x << std::endl;
}위 구현의 경우에는 인자로 전달된 벡터가 복사되어 함수 내부에서 사용된다. 이렇게 구현하는 이유는 아마도 원본 컨테이너를 수정해서는 안되기 때문에 이러한 복사본이 필요하다고 생각할 수 있다. 하지만, T 타입이 단순 정수와 같은 타입이 아니고, 아주 큰 객체라면 벡터를 복사하는데 많은 메모리가 필요하고, 복사하는데 많은 시간이 소요될 수 있다. 따라서, 이보다 더 효율적인 구현은 포인터 벡터를 생성하여 정렬하는 것이 될 수 있다.
template<typename T>
void print_sorted2(std::vector<T> const& v) {
std::vector<T const*> vp;
vp.reserve(v.size());
for (T const& x : v) vp.push_back(&x);
std::sort(vp.begin(), vp.end(), [](T const* a, T const* b) {
return *a < *b;
});
// disable the actual printing since we are not interested in benchmarking the I/O
if (rand() < 0) for (T const* x: vp) std::cout << *x << std::endl;
}두 함수의 성능을 벤치마크로 측정해보자. 참고로, 벤치마크를 통해서 I/O 출력에 대한 성능을 측정하는 것이 아닌 복사 성능을 측정하는 것이 목적이므로 rand()을 통해서 컴파일러가 알아차리지 못하도록 출력하는 척만 하도록 구현되어 있다.
두 벤치마크 구현은 다음과 같다.
void BM_sort_cpy(benchmark::State& state) {
size_t const N = state.range(0);
std::vector<int> v0(N);
for (int& x : v0) x = rand();
std::vector<int> v(N);
for (auto _ : state) {
v = v0;
print_sorted1(v);
}
state.SetItemsProcessed(state.iterations() * N);
}
void BM_sort_ptr(benchmark::State& state) {
size_t const N = state.range(0);
std::vector<int> v0(N);
for (int& x : v0) x = rand();
std::vector<int> v(N);
for (auto _ : state) {
v = v0;
print_sorted2(v);
}
state.SetItemsProcessed(state.iterations() * N);
}
결과는 조금 특이했다. 당연히 포인터를 사용한 함수의 성능이 더 좋을 것으로 예상했지만, 포인터 주소를 할당하는 것보다 복사하는 것이 성능이 더 좋게 측정된다.
Copying to Store Data
구현으로 인해 객체 복사가 필요한 또 다른 특별한 경우가 있는데, 다음 내용들을 통해서 이를 살펴보자.
C++에서는 클래스 생성자에서 데이터의 복사본을 저장하는 경우가 자주 발생하므로, 생성자의 lifetime을 초과하는 long-term copy가 필요하다. 아래 코드를 고려해보자.
struct C {
std::vector<int> v_;
C(std::vector<int> ??? v) { ... v_ is a copy of v ... }
}
위 코드에서는 복사하려는 의도가 있다. 하지만, 중간 복사본을 여러 개 만들거나 불필요한 복사본은 비효율적이므로 const reference로 객체를 가져와서 클래스 내부에 복사본을 만드는 것이 일반적이다.
struct C {
std::vector<int> v_;
C(std::vector<int>& v) : v_(v) { ... v_ is a copy of v ... }
}만약 생성자의 인자가 lvalue라면, 위 구현은 효율적일 수 있다. 만약 인자가 rvalue(temporary)라면 이를 클래스로 이동시켜 복사본을 전혀 만들지 않는 것이 좋다.
struct C {
std::vector<int> v_;
C(std::vector<int>& v) : v_(v) { ... }
C(std::vector<int>&& v) : v_(std::move(v)) { ... }
}단점은 생성자를 두 개 구현해야 한다는 것이다. 만약 생성자가 여러 개의 인자를 받고, 각 인수를 복사하거나 이동해야 한다면 그 수는 더 늘어나게 된다. 예를 들어, 3개의 매개변수를 받는 생성자를 모두 처리하려면 6개의 생성자 오버로드가 필요하다.
이러한 문제의 대안은 모든 매개변수를 값으로 전달하면 매개변수에서 이동시키는 것이다.
struct C {
std::vector<int> v_;
C(std::vector<int> v) : v_(std::move(v)) {
... do not use v here!!! ...
}
}위 생성자에서 매개변수 v는 이동된 상태의 객체이므로 생성자의 본문에서 절대 사용되어서는 안된다. 인수가 lvalue인 경우, 매개변수 v를 위해 복사본이 만들어진 다음 클래스로 이동된다. 이러한 패턴은 객체를 이동하는데 비용이 적게 드는 경우에 효과적이다. 그러나 객체를 이동하는데 비용이 크거나 이동 생성자가 없다면, 결국 두 개의 복사본이 생성된다.
Copying of Return Values
지금까지는 데이터를 함수로 가져오는 문제에 중점을 두었는데, 결과를 반환해야 할 때도 복사가 발생할 수 있다.
처음 예제 코드의 make_v() 함수를 고려해보자.
std::vector<int> v = make_v(... args ...);위 코드는 결과 벡터인 v가 make_v() 함수에 의해 반환되는 다른 벡터로부터 생성된다는 것을 의미한다.
std::vector<int> make_v(... some args ...) {
std::vector<int> vtmp;
... add data to vtmp ...
return vtmp;
}이론적으로 위의 경우, 두 개 이상의 복사본을 만들 수 있다. 지역 변수 vtmp는 make_v() 함수의 (이름이 없는) 리턴값으로 복사되고, 이는 다시 최종 결과 벡터 v로 복사된다. 하지만 실제로 이런 일은 발생하지 않는다. 실제로는 make_v()의 (이름이 없는) 임시 리턴값이 복사되지 않고 최종 결과 벡터 v로 이동된다. 하지만, 대부분의 경우 이마저도 발생하지 않는다.
실제로 아래와 같이 구현한 클래스 C를 이용하여 make_v() 코드를 테스트해보면, 복사나 이동 생성자가 전혀 실행되지 않음을 알 수 있다.
#include <iostream>
using namespace std;
class C {
int i_ = 0;
public:
explicit C(int i) : i_(i) { cout << "C() @" << this << endl; }
C(const C& c) : i_(c.i_) { cout << "C(const C&) @" << this << endl; }
C(C&& c) : i_(c.i_) { cout << "C(C&&) @" << this << endl; }
~C() { cout << "~C() @" << this << endl; }
friend ostream& operator<<(ostream& out, const C& c) { out << c.i_; return out; }
};
C makeC(int i) { C ctmp(i); return ctmp; }
int main() {
C c = makeC(42);
cout << c << endl;
}
결과를 보다시피, 단 하나의 객체만 생성되고 파괴된 것을 알 수 있다. 이는 컴파일러 최적화의 결과이다. 여기서 사용되는 최적화는 Return Value Optimization (RVO)이다. 이 최적화 자체는 매우 간단하다. 컴파일러는 관련된 3개의 객체(지역 변수 ctmp, unnamed temp return value, final result c)가 모두 동일한 타입임을 확인하고, 관측 가능한 결과가 변경되지 않다고 판단한 뒤 세 변수 모두에 대해 동일한 메모리 위치를 사용한다. 함수를 호출하기 전에 컴파일러는 최종 결과 c가 생성될 메모리를 할당해야 하며, 이 메모리 주소는 컴파일러에 의해 함수에 전달되어 동일한 위치에 지역 변수 ctmp를 생성하는데 사용된다. 결과적으로 makeC() 함수가 끝나면 반환할 것이 전혀없으며 결과는 이미 있어야 할 곳에 존재하게 되는 것이다.
RVO는 단순해 보이지만 몇 가지 미묘한 부분이 있다.
먼저 이것은 최적화임을 기억해야 한다. 이는 컴파일러가 꼭 수행할 필요가 없다는 것을 의미한다. 그러나 매우 특별한 종류의 최적화이다. 일반적으로 컴파일러는 관측 가능한 동작을 변경하지 않는 한 프로그램에 원하는 모든 작업을 수행할 수 있다. 관측 가능한 동작에는 입출력 및 휘발성(volatile) 메모리 액세스가 포함된다. 하지만, 위 코드를 살펴보면 복사 생성자 출력과 복사본의 소멸자에 대한 출력이 제거되어 관측 가능한 동작의 변화가 발생했다는 것을 알 수 있다. 이는 RVO에 대한 한 가지 예외이다. 컴파일러는 이러한 함수에 관측 가능한 동작을 변경하는 부작용이 있더라도 생성자나 해당 소멸자 호출을 제거할 수 있다. 이 예외는 RVO에만 국한되지는 않으며, 일반적으로 복사를 수행하는 코드를 작성했다고 복사 및 이동 생성자가 호출될 것이라고 예상할 수 없다. 이를 copy elision (or move elision)이라고 한다.
두 번째, 객체에 복사 또는 이동 생성자가 없으면 위 코드는 컴파일되지 않는다는 점이다. 이는 최적화이며, 최적화를 하려면 먼저 코드를 컴파일해야 한다. 따라서, 컴파일이 되지 않으면 이러한 생성자에 대한 호출을 제거하는 최적화 단계에는 도달하지 못한다. 위 코드에서 복사 및 이동 생성자를 제거해보면 쉽게 확인할 수 있다.
class C {
int i_ = 0;
public:
explicit C(int i) : i_(i) { cout << "C() @" << this << endl; }
C(const C& c) = delete;
C(C&& c) = delete;
~C() { cout << "~C() @" << this << endl; }
friend ostream& operator<<(ostream& out, const C& c) { out << c.i_; return out; }
};
정확한 에러 메시지는 컴파일러와 C++ 버전에 따라 다르다. C++17에서는 위와 같이 출력된다.
하지만, 복사 및 이동 생성자가 제거되어도 프로그램이 컴파일되는 특별한 경우가 있다. makeC 함수를 아래와 같이 변경해보자.
C makeC(int i) { return C(i); }C++11이나 C++14에서는 에러가 발생하지만, C++17 이상에서는 이 코드로 변경하면 제대로 컴파일된다. 이전의 makeC()에서는 리턴되는 객체가 lvalue 였으며, 이름(ctmp)이 있었다. 이제는 이름이 없는 rvalue가 반환된다. 이러한 차이가 이 결과를 만든다. Named RVO (NRVO)는 C++17에서 여전히 최적화되지만, unnamed RVO는 C++17에서 더이상 copy elision으로 간주되지 않으며, 표준에 의해서 애초에 복사나 이동이 요청되지 않는다.
마지막으로 컴파일러가 함수를 컴파일하는 동안 리턴값이 어디에 있는지 알 수 있도록 함수를 인라인화해야 하는지 궁금할 수 있다. 간단한 테스트를 통해 이것이 사실이 아니라는 점을 확인할 수 있다. makeC() 함수가 별도의 컴파일 단위에 있더라도 RVO는 여전히 발생한다.
RVO를 사용하지 않고, 리턴값을 강제로 이동하도록 권장하는 찾을 수도 있다.
C makeC(int i) { C c(i); return std::move(c); }RVO가 발생하지 않으면 프로그램이 복사 작업으로 인한 성능 저하를 감수하는 반면, 이동 작업은 여전히 비용이 적게 든다는 주장이 있다. 하지만, 이는 틀렸다. 이를 이해하려면 바로 위의 에러 메시지를 살펴보면 된다. 컴파일러는 ctmp가 lvalue이므로 복사해야 함에도 이동 생성자가 삭제되었다고 출력하고 있다. 이는 컴파일러 버그가 아니며 표준에서 요구하는 사항을 반영하는 것이다. RVO가 가능하지만 이를 수행하지 않기로 결정한 상황에서 컴파일러는 먼저 결과를 반환하기 위한 이동 생성자를 찾아야 한다. 이동 생성자가 없으면 복사 생성자를 찾는다. 따라서, 명시적인 move를 작성할 이유가 없으며 컴파일러가 이를 수행해준다. 문제는 명시적인 move를 사용하면 RVO가 비활성화된다는 것이다. 위 코드는 move를 요청했으므로 move를 수행하게 된다. move에서 수행하는 작업은 거의 없지만, RVO는 수행하는 작업이 아예 없고 move는 절대 RVO보다 빠를 수가 없다.
Using Pointers to Avoid Copying
객체를 전달할 때 복사를 피하는 방법 중 하나는 포인터를 전달하는 것이다. 객체의 수명을 관리할 필요가 없다면 이것이 가장 쉬운 방법이다. 함수가 객체에 액세스해야 하지만 삭제할 필요가 없는 경우에는 참조로 전달하거나 raw pointer로 전달하는 것이 가장 좋은 방법이다 (이러한 맥락에서 참조는 null이 아닌 포인터일 뿐이다).
마찬가지로 포인터를 사용하여 함수에서 객체를 반환할 수 있지만, 이러한 경우에는 더 많은 주의가 필요하다. 먼저 객체를 힙에 할당해야 하며, 지역 변수에 대한 포인터가 참조를 반환하면 안된다.
C& makeC(int i) { C c(i); return c; } // never do this!또한, 호출자는 이제 객체를 삭제할 책임이 있으므로 함수의 모든 호출자는 객체가 어떻게 생성되었는지 알아야 한다. 여기서 가장 좋은 방법은 스마트 포인터를 반환하는 것이다.
std::unique_ptr<C> makeC(int i) { return std::make_unique<C>(i); }호출자가 객체의 수명을 관리하기 위해 shared pointer를 사용할 수 있는 경우에도 이러한 팩토리 함수는 unique pointer를 반환해야 한다. Unique pointer에서 shared pointer로 이동하는 것은 쉬우며 비용이 적다.
Shared pointer는 스마트 포인터에 의해 수명이 관리되는 객체를 전달하는 데 자주 사용된다. 객체의 소유권을 전달하려는 의도가 없다면, 이는 불필요하고 비효율적인 복사의 예이며, shared pointer를 복사하는 것은 비용이 크다. 따라서, shared pointer로 관리되는 객체가 있을 때, 소유권을 가져오지 않고 이 객체에 대해 동작하는 함수가 필요하다면 raw pointer를 사용하는게 좋다.
void do_work1(C* c);
void do_work2(const C* c);
std::shared_ptr<C> p { new C(...) };
do_work1(&*p);
do_work2(&*p);do_work1()과 do_work2()의 선언은 객체를 삭제하지 않고 사용만 한다는 프로그래머의 의도를 보여준다. 단, 두 함수 모두 nullptr로 호출되는 경우도 예상하여 예외 처리를 해주어야 한다. 이것이 싫다면 참조로 전달하면 된다.
How to Avoid Unnecessary Copying
의도하지 않은 복사를 줄이기 위해 할 수 있는 가장 중요한 것은 이동이 복사보다 적은 비용으로 구현될 수 있는 경우, 모든 데이터 타입을 이동 가능하도록 만드는 것이다. 다른 방법은 복사에 비용이 많이 드는 타입이 있다면 처음부터 복사할 수 없도록 만드는 것이다. 즉, 복사나 할당 연산을 삭제하는 것이다. 대신 클래스가 빠른 이동 연산을 지원하도록 제공한다. 이렇게 하면 의도적이든 아니든 복사가 방지된다. 의도적인 복사가 필요하다면 clone()과 같은 특수한 멤버 함수를 구현해주어도 된다. 이 방법을 사용하면 최소한 모든 복사가 코드 내에서 명시적으로 표시된다.
파라미터를 함수에 전달할 때 가능하면 참조나 포인터를 사용한다. 함수가 인자의 복사복을 만들어야 하는 경우, 값으로 전달하고 대신 파라미터로부터 이동하는 것을 고려하자. 다만 이는 이동이 가능한 타입에 대해서만 잘 동작한다.
함수 인자 전달에 대해 언급한 모든 내용은 임시 지역 변수에도 적용될 수 있다 (함수 매개변수도 기본적으로 function-scope의 임시 지역 변수이다). 복사본이 필요하지 않는 한 이는 참조이어야 한다. 하지만, 이는 기본 내장 타입에는 적용되지 않으며, 내장 타입에 한해서는 간접적으로 액세스하는 것보다 복사하는 것이 더 비용이 저렴하다. 템플릿 코드에서는 타입의 크기가 큰지 작은지 알 수 없으므로 참조를 사용하고 컴파일러 최적화에 의존하여 내장 타입에 불필요한 간접 액세스를 피해야 한다.
함수에서 값을 반환할 때, 가장 먼저 선호되는 것은 RVO와 copy elision에 의존하는 것이다. 컴파일러가 이 최적화를 수행하지 않고 문제가 되는 경우에만 대안을 고려해야 한다. 대안에는 출력 파라미터가 있는 함수를 사용하고, 동적으로 할당된 메모리에 결과를 구성하고 std::unique_ptr과 같은 스마트 포인터를 반환하는 팩토리 함수를 사용하는 것이다.
마지막으로 불필요한 복사에 주의하면서 알고리즘과 구현을 검토해야 한다. 잘못 의도된 복사는 의도하지 않은 복사만큼 성능에 좋지 않다.
Inefficient Memory Management
C++ 메모리 관리에 대한 내용은 그 자체로 책 한 권의 가치가 있으며, STL allocator 문제만을 다루는 논문만 수십 편이 있다. 이 포스팅에서는 성능에 가장 큰 영향을 미치는 몇 가지 문제에 대해서만 다룬다.
성능 측면에서 발생할 수 있는 메모리 관련 문제에는 두 가지 타입이 있다. 첫 번째 문제는 메모리를 너무 많이 사용하는 것이고, 두 번째는 프로그램이 memory-bound일 때 발생하는 문제이다. 두 번째 경우에는 프로그램의 실행 시간이 사용하는 메모리 크기에 직접적인 관련이 있으며, 메모리 사용을 줄이면 프로그램 실행 속도도 빨라진다.
Unnecessary Memory Allocations
메모리 사용과 관련된 가장 일반적인 성능 문제 중 하나는 불필요한 메모리 할당이다.
for ( ... many iterations ...) {
T* buffer = allocate(... size ...);
do_work(buffer); // Computations use memory
deallocate(buffer);
}잘 작성된 프로그램은 RAII 클래스를 통해 할당과 해제를 관리하겠지만, 코드 명확성을 위해 위 코드는 할당과 해제를 명시적으로 표현하고 있다. 할당은 일반적으로 STL 컨테이너와 같이 자체 메모리를 관리하는 객체 내부에 숨겨져 있다.
매우 간단한 벤치마크를 통해 위와 같은 코드가 성능에 미치는 영향을 확인할 수 있다.
constexpr size_t nr = 1UL << 20;
std::vector<size_t> vr {
[](size_t nr) {
std::vector<size_t> v;
v.reserve(nr);
srand(1);
for (size_t i = 0; i < nr; ++i) v[i] = rand();
return v;
}(nr)
};
void BM_make_str_new(benchmark::State& state) {
size_t const NMax = state.range(0);
size_t ir = 0;
for (auto _ : state) {
int const r = vr[ir++ % nr];
size_t const N = (r % NMax) + 1;
char* buf = new char[N];
if (r < 0) std::cout << buf;
delete[] buf;
}
state.SetItemsProcessed(state.iterations());
}위 벤치마크는 문자열을 초기화하는 작업에 대해서 성능을 측정하며, 매 반복마다 임의의 크기의 문자열 메모리를 할당하고 해제한다. 난수를 생성하는 것을 성능에 포함시키지 않기 위해 별도의 벡터를 설정하여 미리 난수를 계산해두고 있다.
이와 비교할 벤치마크로 최대 메모리 크기를 미리 알고 있고, 할당 및 해제를 루프 밖으로 뺀 벤치마크를 사용한다.
void BM_make_str_max(benchmark::State& state) {
size_t const NMax = state.range(0);
char* buf = new char[NMax];
size_t ir = 0;
for (auto _ : state) {
int const r = vr[ir++ % nr];
size_t const N = (r % NMax) + 1;
memset(buf, 0xab, N);
if (r < 0) std::cout << buf;
}
delete[] buf;
state.SetItemsProcessed(state.iterations());
}
성능은 OS와 시스템 라이브러리, 하드웨어에 따라 다르다. M1 Mac에서 최대 1KB의 임의 크기의 문자열을 사용했을 때 성능은 다음과 같다.
계산 중에 필요한 최대 메모리 양을 미리 알고 있는 경우, 이를 사전에 할당하고 각 반복마다 재사용하는 것이 좋다. 이러한 솔루션은 대부분의 컨테이너에도 일반화된다. 벡터 또는 덱의 경우, 반복을 시작하기 전에 메모리를 예약할 수 있고, 컨테이너 크기를 조정하더라도 메모리 용량(capacity)는 줄어들지 않는다는 사실을 활용할 수 있다.
최대 메모리 크기를 미리 알 수 없으면 솔루션은 조금 더 복잡해질 수 있지만, 이는 grow-only buffer를 사용하여 처리할 수 있다. 간단히 말해서 메모리 크기가 확장은 될 수 있지만 축소되지 않는 버퍼를 의미한다.
class Buffer
{
size_t size_;
std::unique_ptr<char[]> buf_;
public:
explicit Buffer(size_t n) : size_(n), buf_(new char[n]) {}
void resize(size_t n) {
if (n < size_) return;
char* new_buf = new char[n];
memcpy(new_buf, get(), size_);
buf_.reset(new_buf);
size_ = n;
}
char* get() { return &buf_[0]; }
};
벤치마크를 통해 이 버퍼에 대한 성능 또한 비교해보자.
void BM_make_str_buf(benchmark::State& state) {
size_t const NMax = state.range(0);
Buffer buf(1);
size_t ir = 0;
for (auto _ : state) {
int const r = vr[ir++ % nr];
size_t const N = (r % NMax) + 1;
buf.resize(N);
memset(buf.get(), 0xab, N);
if (r < 0) std::cout << buf.get();
}
state.SetItemsProcessed(state.iterations());
}
최대 메모리 크기를 알고 있는 벤치마크와 거의 동일한 성능을 보여준다. 이는 아마 첫 몇 번의 반복에서 큰 메모리를 할당받았을 가능성이 높기 때문이다. 대부분의 STL 컨테이너는 이러한 전략의 형태를 사용하고 있다.
결론은 OS와 가능한 한 적게 상호작용해야 한다는 것이다. 각 반복마다 메모리를 할당하고 해제하는 경우에는 반복의 바깥으로 단 한 번만 할당하도록 해야 한다 (동일한 크기로 할당하거나 최대 크기를 알고 있는 경우). 최대 크기를 모를 때는 메모리가 증가할 수는 있지만 감소되지는 않는 데이터 구조를 사용하는 것이 좋다.
Memory Management in Concurrent Programs
OS에서 제공하는 메모리 할당자는 많은 요구 사항의 밸런스를 맞추는 솔루션이다. 특정 시스템에는 오직 하나의 OS만 있지만 고유한 요구 사항과 메모리 패턴을 가진 다양한 프로그램들이 있다. 하지만, 어떤 사용 사례에서도 최상의 솔루션이 되는 경우는 거의 없다.
동시 프로그램에서는 메모리 할당이 더 비효율적이다. 주된 이유는 모든 메모리 할당자가 할당된 메모리와 해제된 메모리를 추적하기 위해 상당히 복잡한 내부 구조를 유지하기 때문이다. 고성능의 할당자에서의 메모리는 비슷한 크기의 할당을 그룹화하도록 세분화된다. 이는 복잡성을 희생하면서 성능을 향상시킨다. 결과적으로 여러 스레드가 동시에 메모리를 할당 및 해제하는 경우, 내부 데이터 관리는 락으로 보호되어야 한다. 이는 전체 프로그램에 대한 global lock이며 할당자가 자주 호출되는 경우에는 프로그램의 scaling을 제한할 수 있다.
이 문제에 대한 가장 일반적인 해결 방법은 malloc()의 대체 라이브러리인 TCMalloc과 같이 thread-local 캐시가 있는 할당자를 사용하는 것이다. 이러한 할당자는 각 스레드에 대해 일정량의 메모리를 예약한다. 스레드에서 메모리가 할당되어야 할 때 먼저 thread-local 메모리 영역에서 할당한다. 하나의 스레드에서만 상호작용하므로 락이 필요하지 않다. 할당할 메모리가 없는 경우에만 락을 사용하여 모든 스레드 간에 공유되는 메모리로부터 할당해야 한다.
이러한 thread-local 캐시에도 문제는 있다.
우선, 전체적으로 더 많은 메모리를 사용하는 경향이 있다. 한 스레드가 많은 메모리를 해제하고 다른 스레드가 많은 메모리를 할당하는 경우에서 최근 해제된 메모리는 다른 스레드에서 사용할 수 없게 된다. 이러한 메모리 낭비를 제한하기 위해 할당자는 일반적으로 스레드별 영역이 미리 정의된 제한 이상으로 커지는 것을 허용하지 않는다. 제한에 도달하면 thread-local 메모리가 모든 스레드 간에 공유되는 영역으로 반환된다 (이 작업에는 락이 필요).
두 번째 문제는 각 할당이 하나의 스레드에 의해 소유되는 경우, 즉, 동일한 스레드가 각 주소에서 메모리를 할당하고 해제하는 경우에 잘 동작한다는 것이다. 한 스레드가 일부 메모리를 할당했지만, 다른 스레드가 이 메모리를 해제해야 하는 경우에는 메모리를 한 스레드의 thread-local 영역에서 다른 스레드의 영역으로 전송해야 하기 때문에 이러한 cross-thread deallocation은 어렵다. 스레드 간 메모리 전송은 가능한 피해야 한다.
한 스레드에서 할당한 메모리를 다른 스레드에서 해제하기 위해 메모리를 전송하는 것이 아닌 단순히 다른 스레드에서 할당된 메모리를 사용하는 것은 어떨까? 이러한 메모리 액세스의 성능은 하드웨어 기능에 따라 크게 달라진다. CPU의 수가 적은 간단한 시스템의 경우, 이는 문제가 되지 않을 가능성이 높다. 그러나 대규모 시스템에서는 여러 개의 메모리 뱅크가 있고 CPU와 메모리 간의 연결은 대칭이 아니다. 각 메모리 뱅크는 특정 CPU에 더 가깝다. 이를 NUMA(non-uniform memory architecture)라고 한다.
메모리를 보다 효율적으로 사용하는 것은 보편적으로 순차 프로그램이나 동시 프로그램에서 모두 성능에 도움되므로 이에 주목하여 살펴보자.
Avoiding Memory Fragmentation
많은 프로그램에서의 한 가지 문제는 메모리 할당 시스템과 비효율적인 상호작용이다. 프로그램이 1KB 메모리를 할당해야 한다고 가정해보자. 이 메모리 덩어리(chunk)는 할당자가 사용하는 것으로 표시된 더 큰 메모리 영역의 주소를 호출자에게 반환한다. 이후 더 많은 메모리 할당이 발생하므로 1KB 덩어리 이후의 메모리도 사용하게 된다. 그런 다음, 프로그램이 첫 번째 할당을 해제하고 2KB 메모리를 즉시 요청하면, 1KB의 여유 덩어리가 있지만 이를 처리할 만큼 크지 않다. 다른 곳에 1KB만큼의 덩어리가 있을 수 있지만 연속된 2KB가 아닌 이상 별로 유용하지 않다.
이러한 상황을 memory fragmentation(메모리 단편화)라고 부른다. 시스템에는 프로그램이 반환한 여유 메모리 공간이 있지만 프로그램이 해제한 메모리가 작은 덩어리로 조각나기 때문에 다른 할당을 처리하기 위해 새로운 메모리를 사용해야 한다. 극단적인 경우, 이러한 단편화로 인해 시스템의 전체 메모리 용량이 실제로 소모되기 전에 메모리가 부족해질 수 있다. 표준 malloc()보다 이러한 단편화에 잘 대응하는 메모리 할당자가 있지만 메모리를 빠르게 전환하는 프로그램의 경우에는 더 극단적인 조치가 필요할 수 있다.
이를 해결하는 한 가지 방법 중 하나는 block allocator이다. 이 아이디어는 모든 메모리가 64KB와 같은 고정된 크기의 블록에 할당된다는 것이다. OS에서는 단일 블록을 한 번에 하나씩 할당해서는 안되고, 고정된 크기의 더 큰 청크(ex, 8MB)를 할당하고 이를 더 작은 블록으로 세분화해야 한다. 한 가지 크기의 블록만 할당하기 때문에 이 할당자(아래 그림의 primary allocator)는 매우 간단할 수 있고 효율적인 구현에 집중할 수 있다. 물론 코드 내 모든 곳에서 64KB 블록을 처리하고 싶지 않을 수 있다.
64KB 블록을 더 작은 할당으로 세분화하는 할당자, secondary allocator를 가질 수 있다. 특히 효율적인 할당자는 한 가지 크기에 대해 균일하게 할당하는 할당자이다. 예를 들어, 단일 64비트 정수에 메모리를 할당하려는 경우, 메모리 오버헤드 없이 할당할 수 있다. 블록에 메모리를 할당하고 이를 사용하여 요소에 저장하는 컨테이너를 가질 수도 있다. 벡터는 단일의 대규모 연속 할당이 필요하므로 여기에 해당하는 배열형 컨테이너로는 deque가 있다. 물론 node 컨테이너도 사용할 수 있다.
이러한 블록 할당의 주요 장점은 단편화가 발생하지 않는다는 것이다. malloc()의 모든 할당은 동일한 크기이므로 primary allocator의 모든 할당도 마찬가지다. 아래 그림처럼 메모리 블록이 할당자에게 반환될 때마다 다음 메모리 요청을 충족하여 재사용될 수 있다.
마지막 64KB 메모리 블록은 가장 최근에 사용된 메모리로부터 재사용될 가능성이 높으며 여전히 캐시에 있을 수 있다. 이를 재사용하면 캐시를 보다 효율적으로 사용할 수 있다.
물론 64KB 블록을 더 작은 크기로 세분화하는 할당자에서는 균일한 크기로 할당하는 것이 아닌 한 여전히 파편화에 취약하다.
블록 메모리 할당을 사용하기로 결정하면 프로그램 전체에 영향을 받을 가능성이 높다. 예를 들어, 각각이 64KB 블록의 일부를 사용하고 나머지는 사용되지 않은 상태로 두는 작은 데이커 구조를 할당하는 것은 엄청난 비용이 든다.
블록 크기 자체도 고정되어 있지 않으므로 잘 선택해야 한다. 일부 프로그램은 작은 데이터 구조를 많이 사용하므로 더 작은 블록을 사용하여 더 효율적일 수 있다.
Optimization of Conditional Execution
불필요한 계산과 메모리의 비효율적인 사용 외에 발생하기 쉬운 비효율적인 코드는 파이프라인이 잘 되지 않아 컴퓨팅 리소스의 상당 부분을 활용하지 못하는 코드이다. 아래 포스팅을 통해 CPU 아키텍처, 리소스 및 성능에서 파이프라인의 중요성을 살펴볼 수 있다.
Instruction-Level Parallelism (ILP)
Pipelining & Branch Optimizations
파이프라인을 가장 방해하는 요소는 일반적으로 conditional operation, 특히, 하드웨어 branch predictor가 예측하지 못하는 작업이다.
안타깝지만 조건부 코드를 최적화하는 것은 가장 어려운 최적화 중 하나이며, 이 최적화는 프로파일러를 통해 분기 예측 성능이 좋지 않은 경우에만 수행해야 한다. 좋은 프로그램은 일반적으로 0.1% 미만의 mispredicted branches를 갖는다. 1% 정도라도 꽤 큰 편이다. 또한, 기계어 코드를 살펴보지 않고 코드 최적화의 효과를 예측하는 것도 상당히 어렵다.
조건부 연산에서 예측이 잘 안된다고 리포트한다면, 어떤 조건이 잘못 예측되었는지 확인해야 한다. 예를 들어, 아래 코드를 살펴보자.
if (a[i] || b[i] || c[i]) { .. do something ... }이 코드는 전체 결과가 예측 가능하더라도 잘못 예측되는 분기가 생성될 수 있다. 이는 C++의 boolean logic 정의와 관련이 있다. || 연산자와 && 연산자는 단락이 된다. 결과가 알려질 때까지 표현식은 왼쪽에서 오른쪽으로 평가되며, 위 코드는 a[i]가 true인 경우 b[i] 및 c[i]에는 액세스해서 안된다. false인 경우에는 필요하다. 사실 이들이 부울 표현식일 필요는 없으며 다음과 같이 표현할 수도 있다.
if (a[i] + b[i] + c[i]) { ... do something ... }
이는 물론 문제가 있는 경우에만 수행해야 하는 최적화이다.
또 다른 예시를 살펴보자.
void f1(bool b, unsigned long x, unsigned long& s) {
if (b) s += x;
}
void f2(bool b, unsigned long x, unsigned long& s) {
s += b*x;
}f1()에서 b의 값은 예측할 수 없기 때문에 비효율적이다. 하지만 f2()와 같이 branch가 없도록 바꿀 수 있다. 이러한 성능은 간단한 벤치마크로 확인할 수 있다.
결과를 보다시피 브랜치가 없는 경우가 훨씬 더 빠르다.
이러한 유형의 최적화는 과도하게 사용하지 않는 것이 중요하며, 반드시 성능 측정을 통해서 결정되어야 한다. 또한, branch predictor는 매우 복잡하며 처리할 수 있는 것과 없는 것에 대한 우리의 예측이 잘못될 수 있다. 컴파일러 최적화로 인해 코드가 크게 변경될 수 있으므로 기계어를 검사하는 것도 중요하다. 또한, 분기가 잘못 예측되더라도 성능에 미치는 영향은 다양할 수 있으므로 측정을 통해 결정하는 것이 중요하다.
예를 들어, 아래와 같이 일반적인 코드를 수작업으로 최적화하는 것은 별로 소용이 없다.
int f(int x) { return (x > 0) ? x : 0; }위 코드는 조건부 코드처럼 보이며, x의 부호가 무작위라면 예측 불가능하다. 그러나 대부분의 컴파일러가 조건부 점프를 사용하여 이를 구현하므로 잘 예측할 가능성이 매우 높다. x86의 일부 컴파일러는 조건부 이동을 수행하는 CMOVE 명령어를 사용한다. 이를 사용하면 명령 순서는 완벽하게 선형적이 되어 순서가 미리 결정되어 있으므로 분기 예측이 필요가 없다.
'프로그래밍 > Optimizations' 카테고리의 다른 글
| Concurrent Data Structures (0) | 2024.02.03 |
|---|---|
| Lock-Based, Lock-Free, Wait-Free Program (0) | 2024.02.02 |
| Memory Model (Memory Order and Barrier) (0) | 2024.01.27 |
| Threads and Memory (0) | 2024.01.25 |
| Cache (0) | 2024.01.22 |
댓글