icon안동민 개발노트

코드 최적화 기법

컴파일러 최적화 옵션 이해와 활용

 코드 최적화는 프로그램의 성능을 향상시키기 위해 코드를 개선하는 과정입니다.

 이 절에서는 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;
}

 최적화 힌트

  1. 병렬화를 적용해 보세요.
  2. 데이터 구조를 개선해 보세요. (예 : 공간 분할)
  3. 불필요한 계산을 줄여보세요.
  4. 캐시 친화적인 데이터 접근 방식을 사용해 보세요.

연습 문제

  1. 피보나치 수열을 계산하는 함수를 작성하고, 재귀, 동적 프로그래밍, 행렬 거듭제곱 방법을 사용하여 구현해보세요. 각 방법의 성능을 비교해보세요.
  2. 큰 텍스트 파일에서 가장 빈도가 높은 단어 10개를 찾는 프로그램을 작성하세요. 다양한 자료구조와 알고리즘을 사용하여 최적화해보세요.
  3. 멀티스레드 프로그램에서 발생할 수 있는 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)
이전으로다음으로