코드 최적화 기법

성능 프로파일링 도구 소개에서 프로그램이 어디에서 시간을 쓰는지 찾았다면, 이제 그 병목을 고칠 차례입니다. 이 글은 여러 분야에 두루 쓰이는 최적화 기법을 컴파일러, 알고리즘과 자료구조, 캐시와 메모리 접근, 불필요한 계산과 할당, 병렬 처리의 순서로 정리합니다.

어떤 기법이든 효과는 프로그램과 입력, 환경에 따라 다르므로, 적용한 뒤에는 반드시 다시 측정합니다. 아래 그림처럼 먼저 정답의 기준을 정하고, 기준 성능을 측정하고, 병목의 종류를 나눈 뒤, 그에 맞는 변경 하나를 적용해 정확성과 성능을 함께 다시 확인합니다. 성능이 나빠졌다면 되돌리고 다음 가설로 넘어갑니다.

아래 그림은 측정한 병목의 종류에 따라 처음 시도할 변경을 고르는 기준입니다. 계산이 많다면 알고리즘과 중복 계산을, 캐시 미스가 많다면 데이터의 배치와 순회 순서를, 할당이 많다면 미리 확보하고 재사용하는 방법을, 기다리는 시간이 길다면 입출력과 잠금을 먼저 봅니다.

data.reserve(expected_count);

컴파일러 최적화

가장 먼저 할 일은 컴파일러의 최적화를 켜는 것입니다. GCC와 Clang에서는 -O2가 대부분의 경우 알맞은 선택이고, -O3는 더 적극적으로 최적화하지만 실행 파일이 커지고 항상 더 빠르지는 않습니다. MSVC에서는 /O2를 씁니다. GCC는 -O 옵션을 주지 않으면 -O0으로 컴파일하므로, 개발 환경 설정의 tasks.json처럼 -O 없이 만든 빌드도 디버깅용 -O0 빌드와 마찬가지로 최적화를 거의 하지 않습니다. 그래서 성능은 반드시 최적화를 켠 빌드로 측정합니다.

컴파일러는 이 옵션들로 인라인 함수에서 본 호출의 인라인 확장, 결과에 영향이 없는 코드의 제거, 반복문을 펼쳐 반복 횟수를 줄이는 루프 펼치기(loop unrolling), 여러 데이터를 한 명령어로 처리하는 벡터화(vectorization) 같은 최적화를 합니다. 링크 시간 최적화(LTO)를 켜는 -flto는 여러 소스 파일을 함께 보고 최적화해, 여러 파일에 걸친 인라인 확장도 가능하게 합니다.

-march=native는 지금 컴퓨터의 CPU가 지원하는 명령어를 모두 쓰게 해 더 빠를 수 있지만, 그렇게 만든 실행 파일은 그 명령어가 없는 다른 컴퓨터에서 실행되지 않을 수 있습니다. 부동 소수점 계산의 규칙을 느슨하게 하는 -ffast-math는 NaN과 무한대가 없다고 가정하고 계산 순서를 바꾸므로, 결과가 달라져도 되는지 확인한 뒤에만 씁니다.

더 깊이: -ffast-math가 실제로 켜는 것과 GCC 12의 -O2

-ffast-math는 옵션 하나처럼 보이지만 여러 옵션을 한꺼번에 켭니다. GCC 문서에 따르면 이 옵션은 -fno-math-errno, -funsafe-math-optimizations, -ffinite-math-only, -fno-rounding-math, -fno-signaling-nans, -fcx-limited-range, -fexcess-precision=fast를 설정합니다. 그 가운데 -ffinite-math-only는 인자와 결과가 NaN이나 무한대가 아니라고 가정하는 최적화를 허용하므로, NaN을 검사하는 코드가 기대대로 동작하지 않을 수 있습니다. GCC는 정확한 IEEE나 ISO 규칙에 기대는 프로그램의 결과를 틀리게 할 수 있다는 이유로, 이 옵션을 -Ofast 말고는 어떤 -O 수준에서도 켜지 않습니다.

이 옵션은 링크할 때도 영향을 줍니다. -funsafe-math-optimizations를 링크 단계에 쓰면 부동 소수점 장치의 기본 제어 상태를 바꾸는 시작 파일이나 라이브러리가 함께 링크될 수 있어서, 그 옵션으로 컴파일하지 않은 코드의 계산까지 달라질 수 있습니다.

-O2가 하는 일도 버전에 따라 바뀝니다. GCC 12부터 -O2는 비용이 아주 적다고 판단되는 경우에 한해 벡터화를 하며, 이는 이전 버전에서 -O2 -ftree-vectorize -fvect-cost-model=very-cheap을 준 것과 같습니다. 그래서 같은 -O2 빌드라도 GCC 11과 12 이후에서 성능이 달라질 수 있으므로, 측정 기록에는 컴파일러의 버전도 함께 적습니다.

알고리즘과 자료구조

시간 복잡도가 다른 알고리즘은 입력이 커질수록 차이가 크게 벌어지므로, 다른 어떤 기법보다 효과가 큽니다. 다음 두 함수는 같은 값이 두 번 이상 있는지 확인합니다.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

bool hasDuplicateSlow(const std::vector<int>& v) {
    for (std::size_t i = 0; i < v.size(); ++i) {
        for (std::size_t j = i + 1; j < v.size(); ++j) {
            if (v[i] == v[j]) {
                return true;
            }
        }
    }
    return false;
}

bool hasDuplicateFast(std::vector<int> v) {
    std::sort(v.begin(), v.end());
    return std::adjacent_find(v.begin(), v.end()) != v.end();
}

int main() {
    std::vector<int> a{5, 3, 9, 3};
    std::vector<int> b{1, 2, 3};
    std::cout << std::boolalpha
              << hasDuplicateSlow(a) << ' ' << hasDuplicateFast(a) << ' '
              << hasDuplicateSlow(b) << ' ' << hasDuplicateFast(b) << '\n';
}

true true false false

두 함수는 같은 답을 내지만, 첫 함수는 모든 쌍을 비교해 원소 수의 제곱에 비례하는 시간이 들고, 둘째 함수는 정렬한 뒤 이웃한 원소만 비교해 n log n에 비례하는 시간이 듭니다. 원소가 백만 개라면 쌍의 비교는 약 5000억 번이지만, 정렬은 약 2000만 번의 비교로 끝납니다. 둘째 함수는 원본을 바꾸지 않으려고 vector를 값으로 받아 복사하는데, 이 복사 비용도 측정할 때 함께 포함됩니다.

자료구조도 컨테이너 개요에서 본 것처럼 주로 하는 연산에 맞게 고릅니다. 키로 자주 찾는다면 std::unordered_map의 평균 상수 시간이 유리하지만, 해시 계산 비용과 충돌이 몰리는 최악의 경우도 생각해야 합니다. 원소가 적거나 순회가 많다면 이론상 느린 std::vector가 실제로는 더 빠른 경우가 흔하므로, 시간 복잡도만으로 정하지 말고 측정합니다.

캐시와 메모리 접근

CPU는 메모리에서 데이터를 가져올 때 주변의 데이터도 한꺼번에 캐시(cache)로 가져옵니다. 그래서 메모리에 이어진 데이터를 순서대로 읽으면 대부분 캐시에서 바로 읽히지만, 여기저기 흩어진 데이터를 읽으면 매번 느린 메모리까지 가야 합니다. 원소가 이어져 있는 std::vector를 순회하는 것이 노드가 흩어져 있는 std::list보다 빠른 큰 이유입니다. 이웃한 데이터를 함께 가져오는 것이 왜 효과가 있는지는 컴퓨터구조 교재의 메모리 계층과 주기억장치에서 지역성(locality)으로 설명합니다.

다차원 배열에서 본 것처럼 2차원 배열은 행 우선으로 저장되므로, 바깥 루프가 행을, 안쪽 루프가 열을 돌아야 메모리를 순서대로 읽습니다. 바깥 루프가 열을 돌면 결과는 같지만 한 칸씩 건너뛰며 읽어 캐시를 잘 쓰지 못하고, 배열이 클수록 눈에 띄게 느려질 수 있습니다.

여러 스레드가 서로 다른 변수를 쓰더라도, 그 변수들이 같은 캐시 라인(cache line)에 있으면 한 스레드가 쓸 때마다 다른 스레드의 캐시가 무효가 되어 느려집니다. 이를 거짓 공유(false sharing)라고 하며, 스레드마다 쓰는 데이터를 C++17의 std::hardware_destructive_interference_size만큼 떨어뜨려 배치해 피할 수 있습니다. 읽기만 하는 데이터는 같은 캐시 라인에 있어도 이런 문제가 생기지 않습니다. 한 코어의 쓰기가 다른 코어의 캐시 라인을 왜 무효로 만드는지는 컴퓨터구조 교재의 공유 메모리·NUMA·일관성에서 캐시 일관성과 함께 다룹니다.

불필요한 계산 줄이기

반복문 안에서 매번 같은 값을 계산한다면, 반복문 밖으로 옮겨 한 번만 계산할 수 있습니다. 이를 루프 불변 코드 이동(loop invariant code motion)이라고 하며, 컴파일러가 스스로 하기도 하지만 함수 호출처럼 컴파일러가 안전한지 알 수 없는 경우에는 직접 옮겨야 합니다.

#include <iostream>
#include <vector>

int measuredValue(int param, int& calls) {
    ++calls;
    return param * 2;
}

std::vector<int> before(int n, int param, int& calls) {
    std::vector<int> result(n);
    for (int i = 0; i < n; ++i) {
        result[i] = i * measuredValue(param, calls);
    }
    return result;
}

std::vector<int> after(int n, int param, int& calls) {
    std::vector<int> result(n);
    if (n > 0) {
        const int fixed = measuredValue(param, calls);
        for (int i = 0; i < n; ++i) {
            result[i] = i * fixed;
        }
    }
    return result;
}

int main() {
    int aCalls = 0;
    int bCalls = 0;
    const auto a = before(3, 5, aCalls);
    const auto b = after(3, 5, bCalls);
    std::cout << std::boolalpha << (a == b) << " : " << aCalls << " / " << bCalls << '\n';
    for (int x : b) {
        std::cout << x << ' ';
    }
    std::cout << '\n';

    aCalls = 0;
    bCalls = 0;
    before(0, 5, aCalls);
    after(0, 5, bCalls);
    std::cout << aCalls << " / " << bCalls << '\n';
}

true : 3 / 1
0 10 20
0 / 0

measuredValue는 같은 인자에 늘 같은 값을 돌려주므로, 한 번만 계산해도 결과 배열은 같고 호출은 세 번에서 한 번으로 줄어듭니다. after가 n > 0일 때만 계산하는 것은, 원래 코드에서 n이 0이면 함수가 한 번도 호출되지 않았던 동작을 그대로 지키기 위해서입니다. 이 옮기기가 올바른 것은 함수에 다른 효과가 없을 때뿐이며, 호출마다 반드시 기록을 남기는 함수라면 결과 배열이 같아도 옮기면 안 됩니다. 또 호출 수가 3분의 1이 되었다고 실행 시간이 3분의 1이 되는 것은 아니므로, 다시 측정합니다.

큰 객체는 참조자에서 본 것처럼 const 참조로 넘겨 복사를 피하고, 넘겨줄 값은 move 의미론과 rvalue 참조의 std::move로 옮깁니다. 함수가 지역 객체를 값으로 돌려주는 것은 복사 생략 덕분에 대개 비용이 없으므로, 성능을 위해 출력 매개변수로 바꿀 필요는 없습니다.

메모리 할당 줄이기

new와 delete, 그리고 그것을 쓰는 컨테이너의 할당에는 할당자를 관리하는 비용이 듭니다. 원소 수를 미리 안다면 std::vector의 reserve(n)으로 공간을 한 번에 확보해, 원소를 추가하는 동안 재할당과 원소 이동이 반복되지 않게 합니다. 반복문 안에서 임시 std::string이나 std::vector를 매번 만들고 버린다면, 반복문 밖에 하나 만들어 두고 clear()해서 다시 쓰면 할당을 줄일 수 있습니다.

작은 객체를 아주 많이 만들고 지우는 프로그램은 미리 큰 덩어리를 할당해 두고 그 안에서 나누어 쓰는 메모리 풀(memory pool)을 쓰기도 합니다. 이런 기법은 코드를 복잡하게 만들므로, 프로파일러가 할당이 실제 병목이라고 보여 줄 때만 씁니다.

병렬 처리

계산을 독립된 조각으로 나눌 수 있다면 스레드 생성과 관리에서 본 스레드나 std::async로 여러 코어에서 동시에 처리할 수 있습니다. C++17부터는 std::sort(std::execution::par, v.begin(), v.end())처럼 알고리즘에 실행 정책을 넘겨 병렬로 실행하게 할 수도 있으며, GCC의 표준 라이브러리는 이를 위해 Intel TBB 라이브러리를 함께 링크해야 할 수 있습니다.

병렬 처리로 빨라지는 것은 나눌 수 있는 부분뿐입니다. 전체 100밀리초 가운데 40밀리초를 쓰는 함수를 20밀리초로 줄이면, 나머지 60밀리초는 그대로이므로 전체는 80밀리초가 되어 20% 빨라질 뿐입니다. 그래서 한 부분을 두 배 빠르게 해도 전체가 두 배가 되지는 않으며, 스레드를 만들고 결과를 모으는 비용과 동기화 비용도 함께 따져야 합니다.

정리

• 최적화는 정답의 기준을 정하고 기준 성능을 측정한 뒤, 병목에 맞는 변경 하나를 적용해 정확성과 성능을 함께 다시 확인하는 반복입니다.
• 먼저 -O2 같은 컴파일러 최적화를 켜고, 성능은 반드시 최적화한 빌드로 측정합니다.
• 알고리즘의 시간 복잡도를 줄이는 것이 가장 효과가 크며, 자료구조는 주로 하는 연산과 측정으로 고릅니다.
• 이어진 메모리를 순서대로 읽으면 캐시를 잘 쓰며, 스레드마다 쓰는 데이터는 거짓 공유를 피해 떨어뜨립니다.
• 반복마다 같은 계산은 밖으로 옮기되, 함수에 다른 효과가 없을 때만 옮기고 원래의 호출 조건을 지킵니다.
• reserve와 재사용으로 할당을 줄이고, 병렬 처리는 나눌 수 있는 부분만 빠르게 한다는 점을 계산에 넣습니다.

연습 문제

1. 루프 밖으로 옮기기

loop_invariant.cpp에서 n을 4, param을 2로 호출하면 두 배열과 두 함수의 호출 수는 무엇인가요? measuredValue가 호출될 때마다 반드시 감사 기록을 남겨야 하는 함수라면, 결과 배열이 같으니 옮겨도 되나요?

2. 한 부분만 빨라졌을 때

전체 100밀리초 가운데 40밀리초를 쓰는 함수를 10밀리초로 줄이면, 나머지가 그대로일 때 전체 시간과 개선율은 얼마인가요?

3. 먼저 시도할 변경

프로파일링 결과 실행 시간의 대부분이 반복문 안의 result.push_back(x)에서 일어나는 재할당에 쓰였고, 반복 횟수는 반복문에 들어가기 전에 알 수 있습니다. 먼저 시도할 변경은 무엇인가요?

다음 글 디버거 사용법에서는 프로그램이 잘못된 결과를 내거나 멈출 때, 중단점과 단계 실행, 변수 확인으로 원인을 찾는 디버거의 사용법을 다룹니다.