코드 최적화 기법
컴파일러 최적화 옵션 이해와 활용
코드 최적화는 프로그램의 성능을 향상시키기 위해 코드를 개선하는 과정입니다. 이 절에서는 C++에서 사용할 수 있는 다양한 최적화 기법을 자세히 살펴보고, 실습을 통해 이해를 깊이 있게 할 것입니다.
컴파일러는 강력한 최적화 기능을 제공합니다. 이를 적절히 활용하는 것이 중요합니다.
GCC / Clang 최적화 옵션
-O0: 최적화 없음 (디버깅용)-O1: 기본적인 최적화-O2: 더 강력한 최적화 (일반적으로 권장)-O3: 가장 강력한 최적화 (때때로 코드 크기 증가)-Os: 코드 크기 최적화-Ofast: 수학적 정확성을 희생하더라도 최대 성능 추구
MSVC 최적화 옵션
/Od: 최적화 비활성화/O1: 크기 최소화/O2: 속도 최대화 (권장)/Ox: 최대 최적화
실습 : 최적화 레벨에 따른 성능 비교
다음 코드를 사용하여 다양한 최적화 레벨의 효과를 비교해 봅시다.
#include <iostream>
#include <chrono>
#include <vector>
#include <cmath>
const int SIZE = 10000000;
double compute(const std::vector<double>& data) {
double result = 0.0;
for (const auto& val : data) {
result += std::sin(val) * std::cos(val);
}
return result;
}
int main() {
std::vector<double> data(SIZE);
for (int i = 0; i < SIZE; ++i) {
data[i] = i * 0.01;
}
auto start = std::chrono::high_resolution_clock::now();
double result = compute(data);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Result: " << result << std::endl;
std::cout << "Time taken: " << diff.count() << " seconds" << std::endl;
return 0;
}이 코드를 다양한 최적화 레벨로 컴파일하고 실행 시간을 비교해 보세요.
데이터 구조 선택과 최적화
적절한 데이터 구조 선택은 성능에 큰 영향을 미칩니다.
std::vector vs std::list
std::vector: 연속된 메모리, 빠른 임의 접근std::list: 연결 리스트, 빠른 삽입/삭제
std::unordered_map vs std::map
std::unordered_map: 해시 테이블, 평균 O(1) 접근std::map: 레드-블랙 트리, O(log n) 접근
실습 : 데이터 구조 성능 비교
다음 코드를 사용하여 다양한 데이터 구조의 성능을 비교해 봅시다.
#include <iostream>
#include <chrono>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <string>
const int SIZE = 1000000;
template<typename T>
void measure_insertion(T& container, const std::string& name) {
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
container.insert(container.end(), i);
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << name << " insertion time: " << diff.count() << " seconds" << std::endl;
}
template<typename T>
void measure_access(T& container, const std::string& name) {
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
auto it = std::find(container.begin(), container.end(), i);
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << name << " access time: " << diff.count() << " seconds" << std::endl;
}
int main() {
std::vector<int> vec;
std::list<int> lst;
std::map<int, int> map;
std::unordered_map<int, int> umap;
measure_insertion(vec, "Vector");
measure_insertion(lst, "List");
measure_access(vec, "Vector");
measure_access(lst, "List");
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
map[i] = i;
}
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Map insertion time: " << diff.count() << " seconds" << std::endl;
start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < SIZE; ++i) {
umap[i] = i;
}
end = std::chrono::high_resolution_clock::now();
diff = end - start;
std::cout << "Unordered Map insertion time: " << diff.count() << " seconds" << std::endl;
return 0;
}알고리즘 최적화
효율적인 알고리즘 선택은 성능 향상의 핵심입니다.
정렬 알고리즘 선택
std::sort: 일반적인 정렬std::partial_sort: 부분 정렬std::nth_element: n번째 원소 찾기std::stable_sort: 안정 정렬
검색 알고리즘
std::find: 선형 검색std::binary_search: 이진 검색 (정렬된 범위에서)std::lower_bound,std::upper_bound: 정렬된 범위에서 경계 찾기
실습 : 알고리즘 성능 비교
다음 코드를 사용하여 다양한 알고리즘의 성능을 비교해 봅시다.
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <random>
const int SIZE = 1000000;
std::vector<int> generate_random_vector(int size) {
std::vector<int> vec(size);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(1, size);
for (int& num : vec) {
num = dis(gen);
}
return vec;
}
template<typename Func>
void measure_time(Func f, const std::string& name) {
auto start = std::chrono::high_resolution_clock::now();
f();
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << name << " time: " << diff.count() << " seconds" << std::endl;
}
int main() {
std::vector<int> vec = generate_random_vector(SIZE);
std::vector<int> vec_copy = vec;
measure_time([&]() { std::sort(vec.begin(), vec.end()); }, "std::sort");
vec = vec_copy;
measure_time([&]() { std::partial_sort(vec.begin(), vec.begin() + SIZE/2, vec.end()); }, "std::partial_sort");
vec = vec_copy;
measure_time([&]() { std::nth_element(vec.begin(), vec.begin() + SIZE/2, vec.end()); }, "std::nth_element");
vec = vec_copy;
measure_time([&]() { std::stable_sort(vec.begin(), vec.end()); }, "std::stable_sort");
std::sort(vec.begin(), vec.end());
int target = vec[SIZE/2];
measure_time([&]() { std::find(vec.begin(), vec.end(), target); }, "std::find");
measure_time([&]() { std::binary_search(vec.begin(), vec.end(), target); }, "std::binary_search");
measure_time([&]() { std::lower_bound(vec.begin(), vec.end(), target); }, "std::lower_bound");
return 0;
}메모리 관리 최적화
효율적인 메모리 관리는 성능 향상에 중요합니다.
메모리 풀 사용
메모리 풀은 작은 객체들을 효율적으로 할당하고 해제하는 데 사용됩니다.
#include <cstddef>
#include <new>
class MemoryPool {
static constexpr size_t POOL_SIZE = 1024 * 1024; // 1MB
char* pool;
size_t used = 0;
public:
MemoryPool() : pool(new char[POOL_SIZE]) {}
~MemoryPool() { delete[] pool; }
void* allocate(size_t size) {
if (used + size > POOL_SIZE) throw std::bad_alloc();
void* result = pool + used;
used += size;
return result;
}
void deallocate(void* /*ptr*/, size_t /*size*/) {
// 이 간단한 예제에서는 개별 해제를 구현하지 않았습니다.
}
};
MemoryPool mempool;
struct MyStruct {
int data[25]; // 100 bytes
static void* operator new(size_t size) {
return mempool.allocate(size);
}
static void operator delete(void* ptr, size_t size) {
mempool.deallocate(ptr, size);
}
};스마트 포인터 활용
스마트 포인터를 사용하면 메모리 누수를 방지하고 자원 관리를 자동화할 수 있습니다.
#include <memory>
#include <vector>
class Resource {
public:
void use() { /* ... */ }
};
void process_resources(const std::vector<std::shared_ptr<Resource>>& resources) {
for (const auto& res : resources) {
res->use();
}
}
int main() {
std::vector<std::shared_ptr<Resource>> resources;
for (int i = 0; i < 10; ++i) {
resources.push_back(std::make_shared<Resource>());
}
process_resources(resources);
return 0;
}병렬화와 동시성
멀티코어 프로세서를 활용하여 성능을 향상시킬 수 있습니다.
std::async 사용
#include <iostream>
#include <future>
#include <vector>
#include <numeric>
template<typename Iterator>
int parallel_sum(Iterator begin, Iterator end) {
auto len = std::distance(begin, end);
if (len < 1000)
return std::accumulate(begin, end, 0);
Iterator mid = begin + len/2;
auto handle = std::async(std::launch::async,
parallel_sum<Iterator>, mid, end);
int sum = parallel_sum(begin, mid);
return sum + handle.get();
}
int main() {
std::vector<int> v(10000000, 1);
std::cout << "The sum is " << parallel_sum(v.begin(), v.end()) << '\n';
}std::thread 사용
#include <iostream>
#include <thread>
#include <vector>
#include <numeric>
void partial_sum(const std::vector<int>& v, int start, int end, int& result) {
result = std::accumulate(v.begin() + start, v.begin() + end, 0);
}
int main() {
std::vector<int> v(10000000, 1);
std::vector<int> partial_results(4);
std::vector<std::thread> threads;
for (int i = 0; i < 4; ++i) {
threads.emplace_back(partial_sum, std::ref(v), i * 2500000, (i + 1) * 2500000,
std::ref(partial_results[i]));
}
for (auto& t : threads) {
t.join();
}
int total_sum = std::accumulate(partial_results.begin(), partial_results.end(), 0);
std::cout << "The sum is " << total_sum << '\n';
}캐시 친화적 코드 작성
CPU 캐시를 효율적으로 활용하면 성능을 크게 향상시킬 수 있습니다.
데이터 지역성 향상
#include <chrono>
#include <iostream>
#include <vector>
const int SIZE = 10000;
void process_row_wise(std::vector<std::vector<int>>& matrix) {
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
matrix[i][j] *= 2;
}
}
}
void process_column_wise(std::vector<std::vector<int>>& matrix) {
for (int j = 0; j < SIZE; ++j) {
for (int i = 0; i < SIZE; ++i) {
matrix[i][j] *= 2;
}
}
}
int main() {
std::vector<std::vector<int>> matrix(SIZE, std::vector<int>(SIZE, 1));
auto start = std::chrono::high_resolution_clock::now();
process_row_wise(matrix);
auto end = std::chrono::high_resolution_clock::now();
std::cout << "Row-wise processing time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms\n";
start = std::chrono::high_resolution_clock::now();
process_column_wise(matrix);
end = std::chrono::high_resolution_clock::now();
std::cout << "Column-wise processing time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms\n";
return 0;
}False Sharing 방지
False sharing은 멀티스레드 프로그램에서 성능을 저하시킬 수 있는 요인입니다.
#include <chrono>
#include <iostream>
#include <thread>
#include <vector>
struct alignas(64) AlignedInt {
int value;
char padding[60]; // 캐시 라인 크기를 64바이트로 가정
};
void increment_normal(std::vector<int>& data, int thread_id, int num_threads) {
for (int i = thread_id; i < 1000000; i += num_threads) {
data[thread_id]++;
}
}
void increment_aligned(std::vector<AlignedInt>& data, int thread_id, int num_threads) {
for (int i = thread_id; i < 1000000; i += num_threads) {
data[thread_id].value++;
}
}
int main() {
const int num_threads = 4;
std::vector<int> normal_data(num_threads, 0);
std::vector<AlignedInt> aligned_data(num_threads, {0});
auto start = std::chrono::high_resolution_clock::now();
std::vector<std::thread> normal_threads;
for (int i = 0; i < num_threads; ++i) {
normal_threads.emplace_back(increment_normal, std::ref(normal_data), i, num_threads);
}
for (auto& t : normal_threads) {
t.join();
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << "Normal increment time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms\n";
start = std::chrono::high_resolution_clock::now();
std::vector<std::thread> aligned_threads;
for (int i = 0; i < num_threads; ++i) {
aligned_threads.emplace_back(increment_aligned, std::ref(aligned_data), i, num_threads);
}
for (auto& t : aligned_threads) {
t.join();
}
end = std::chrono::high_resolution_clock::now();
std::cout << "Aligned increment time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms\n";
return 0;
}컴파일 시간 최적화
템플릿 메타프로그래밍을 활용하여 컴파일 시간에 계산을 수행할 수 있습니다.
#include <iostream>
// 컴파일 시간 팩토리얼 계산
template<unsigned int N>
struct Factorial {
static constexpr unsigned int value = N * Factorial<N - 1>::value;
};
template<>
struct Factorial<0> {
static constexpr unsigned int value = 1;
};
// 런타임 팩토리얼 계산
unsigned int runtime_factorial(unsigned int n) {
if (n == 0) return 1;
return n * runtime_factorial(n - 1);
}
int main() {
std::cout << "Compile-time factorial of 5: " << Factorial<5>::value << std::endl;
std::cout << "Run-time factorial of 5: " << runtime_factorial(5) << std::endl;
return 0;
}실습 : 종합 최적화 예제
다음은 여러 최적화 기법을 적용할 수 있는 종합 예제입니다. 이 코드를 최적화해 보세요.
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
};
double distance(const Point& p1, const Point& p2) {
double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
return std::sqrt(dx*dx + dy*dy);
}
std::vector<Point> generate_points(int n) {
std::vector<Point> points;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> dis(-1000.0, 1000.0);
for (int i = 0; i < n; ++i) {
points.push_back(Point(dis(gen), dis(gen)));
}
return points;
}
double find_closest_pair(const std::vector<Point>& points) {
double min_distance = std::numeric_limits<double>::max();
for (size_t i = 0; i < points.size(); ++i) {
for (size_t j = i + 1; j < points.size(); ++j) {
double d = distance(points[i], points[j]);
if (d < min_distance) {
min_distance = d;
}
}
}
return min_distance;
}
int main() {
const int N = 10000;
auto points = generate_points(N);
auto start = std::chrono::high_resolution_clock::now();
double closest = find_closest_pair(points);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end - start;
std::cout << "Closest pair distance: " << closest << std::endl;
std::cout << "Time taken: " << diff.count() << " seconds" << std::endl;
return 0;
}최적화 힌트
- 병렬화를 적용해 보세요.
- 데이터 구조를 개선해 보세요. (예 : 공간 분할)
- 불필요한 계산을 줄여보세요.
- 캐시 친화적인 데이터 접근 방식을 사용해 보세요.
연습 문제
- 피보나치 수열을 계산하는 함수를 작성하고, 재귀, 동적 프로그래밍, 행렬 거듭제곱 방법을 사용하여 구현해보세요. 각 방법의 성능을 비교해보세요.
- 큰 텍스트 파일에서 가장 빈도가 높은 단어 10개를 찾는 프로그램을 작성하세요. 다양한 자료구조와 알고리즘을 사용하여 최적화해보세요.
- 멀티스레드 프로그램에서 발생할 수 있는 race condition을 시연하는 코드를 작성하고, 이를 해결하기 위한 여러 동기화 기법(뮤텍스, 원자적 연산 등)을 적용해보세요. 각 방법의 장단점을 비교해보세요.
참고 자료
- "Optimizing C++" by Kurt Guntheroth
- "C++ High Performance" by Viktor Sehr and Björn Andrist
- "Effective Modern C++" by Scott Meyers
- "C++ Concurrency in Action" by Anthony Williams
- Intel's Guide to Vectorization
- Agner Fog's optimization resources
- CppCon talks on YouTube (search for "CppCon optimization")
- "The Art of Computer Programming, Volume 1" by Donald Knuth (for algorithm analysis and optimization)