프로그램 성능 최적화

5.1최적화 컴파일러의 능력과 한계

먼저 인정할 것. gcc -O2는 똑똑하다. 상수 접기(constant folding), 공통 부분식 제거(CSE), 죽은 코드 제거(DCE), 강도 약화(strength reduction) 같은 고전적 변환은 컴파일러가 알아서 해준다. 그래서 우리가 손으로 x*2를 x << 1로 고치는 건 대부분 헛수고고, 오히려 가독성만 떨어뜨린다.

문제는 컴파일러가 모든 변환을 안전하게만 한다는 점이다. 한 톨이라도 의미가 바뀔 가능성이 있으면, 컴파일러는 손을 뗀다. 두 가지 대표적 함정을 보자.

메모리 앨리어싱 (memory aliasing)

두 개의 포인터가 사실은 같은 곳을 가리키는 상황. 컴파일러는 혹시 그럴 수도 있으니까 보수적으로 행동한다.

aliasing 위험으로 컴파일러가 최적화를 포기하는 사례// xp와 yp가 같은 주소를 가리킬 수도 있다고 가정하면
// 컴파일러는 *xp를 두 번 읽을 수밖에 없다
void twiddle1(long *xp, long *yp) {
    *xp += *yp;
    *xp += *yp;
}

// 사람이 보면 명백히 더 빠른 형태
void twiddle2(long *xp, long *yp) {
    *xp += 2 * (*yp);   // xp를 한 번만 읽고 한 번만 쓴다
}

twiddle1(p, p)처럼 호출하면 두 함수의 결과가 달라진다. 그래서 twiddle1은 twiddle2로 자동 변환되지 않는다. C에서는 restrict 키워드로 "겹치지 않는다"를 약속할 수 있고, 그러면 컴파일러가 더 과감해진다.

함수의 부수 효과 (side effects)

함수가 전역 상태를 건드릴 가능성이 있으면 컴파일러는 호출을 합치거나 제거하지 못한다. 예를 들어 f()가 매번 다른 값을 반환하거나 카운터를 증가시킨다면, f() + f() + f() + f()를 4 * f()로 바꿀 수 없다.

최적화 레벨

5.2프로그램 성능 표현

성능을 어떻게 잴까? "초당 몇 번 돌았다"는 머신마다 다르고, 클럭 주파수에 휘둘린다. 이 장에서 쓰는 단위는 CPE (Cycles Per Element)다. 입력 원소 하나를 처리하는 데 평균 몇 사이클이 들었느냐를 보는 것.

프로그램이 n개의 원소를 처리하는 데 걸리는 사이클 수를 T(n)이라 하자. 보통 T(n) = a + b·n 꼴이 된다. a는 함수 진입/종료 같은 고정 비용, b는 원소당 비용(=CPE)이다. n이 커질수록 a는 묻힌다.

// 예: n=1000일 때 12,500 사이클이 걸렸다면
// CPE는 약 12.5 cycles/element
// 동일한 함수가 같은 머신에서 8,000 사이클이면 CPE = 8.0

이 장에서 우리는 베이스라인 약 22 CPE(부동소수점 곱셈)에서 출발해서, 몇 가지 변환을 거쳐 0.5 CPE 근처까지 내려간다. 40배 이상 빨라지는 셈이다.

5.3프로그램 예제

이 장의 마스코트는 벡터의 모든 원소를 하나로 결합하는 함수다. 합산일 수도 있고 곱셈일 수도 있다. 같은 코드 골격을 두고 데이터 타입(int, float, double)과 연산(+, *)을 바꿔가며 측정한다.

베이스라인: 가장 평범한 결합 함수typedef long data_t;          // int일 수도, double일 수도
#define IDENT 0                // + 연산의 항등원. *이면 1
#define OP +                   // 결합 연산자

typedef struct {
    long len;
    data_t *data;
} vec_rec, *vec_ptr;

// dest에 v의 모든 원소를 OP로 결합한 결과를 쓴다
void combine1(vec_ptr v, data_t *dest) {
    long i;
    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

이 코드는 모범적인 것 같지만 비효율의 종합 선물세트다. 매 반복마다 (1) vec_length를 호출하고, (2) get_vec_element로 경계 검사를 하고, (3) *dest를 메모리에서 읽고 다시 쓴다. 이걸 하나씩 걷어낼 차례다.

(숫자는 Intel Haswell 기준 대략값. 머신에 따라 다르지만 상대적 경향은 비슷하다.)

5.4루프 비효율 제거

combine1의 첫 번째 죄목: 루프 조건에서 매번 vec_length(v)를 호출. 벡터 길이가 루프 안에서 바뀌지 않는데도 매 반복마다 함수를 부른다. 이걸 루프 불변 코드 외부 이동(loop-invariant code motion)이라고 한다.

void combine2(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_length(v);   // 루프 밖으로 끌어냄
    *dest = IDENT;
    for (i = 0; i < length; i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

그렇다고 모든 함수 호출을 무작정 끄집어낼 수 있는 건 아니다. 해당 함수가 순수(pure)해야 한다 — 같은 인자에 같은 결과를 내고, 외부 상태를 건드리지 않아야 한다.

5.5프로시저 호출 줄이기

get_vec_element는 매 호출마다 인덱스가 유효한지 검사한다. 안전하지만, 우리는 이미 루프 조건에서 i < length로 똑같은 검사를 하고 있다. 이중 검사다. 벡터 내부 배열에 대한 직접 포인터를 한 번만 얻어 두면 깔끔해진다.

data_t *get_vec_start(vec_ptr v) {
    return v->data;
}

void combine3(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);   // 직접 포인터 한 번만
    *dest = IDENT;
    for (i = 0; i < length; i++) {
        *dest = *dest OP data[i];      // 함수 호출 없이 바로 인덱싱
    }
}

함수 호출 자체의 오버헤드(레지스터 저장, 점프, 복귀)는 한 번에 몇 사이클 정도지만, 루프 안에서 매 반복마다 이뤄지면 합산이 무시 못 한다. 결정적으로, 함수 호출이 사라지면 컴파일러가 루프 본문을 더 적극적으로 변환할 수 있게 된다.

5.6불필요한 메모리 참조 제거

combine3의 본문 한 줄을 다시 보자.

*dest = *dest OP data[i];

이 줄이 컴파일되면, 매 반복마다 (1) *dest를 메모리에서 로드 → (2) 연산 → (3) *dest에 다시 스토어가 된다. 누산값이 메모리를 왕복하는 셈이다. 왜 컴파일러가 누산값을 레지스터에 들고 있지 않을까? 앨리어싱 우려 때문이다. 만약 dest가 data[i]가 가리키는 곳과 겹친다면, 우리가 *dest에 쓴 값이 다음 data[i+1] 읽기에 영향을 줄 수 있다. 컴파일러는 그 가능성을 배제할 수 없으므로, 매번 메모리를 통해 동기화한다.

해결책은 간단하다. 로컬 임시 변수로 누산하고, 끝나고 한 번만 *dest에 쓴다.

메모리 왕복 제거void combine4(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_length(v);
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;          // 누산기를 레지스터에 둔다
    for (i = 0; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;                 // 마지막에 한 번만 저장
}

이 변환만으로 정수 덧셈/곱셈, 부동소수점 덧셈은 CPE가 거의 절반으로 떨어진다. 실수 곱셈 같은 긴 지연(latency) 연산은 다른 병목이 있어서 효과가 다르게 나타난다.

5.7현대 프로세서 이해하기

여기서부터는 코드를 더 빠르게 만들려면 CPU가 어떻게 도는지 알아야 한다. 90년대까지의 CPU는 한 사이클에 한 명령씩 처리했지만, 지금은 그렇지 않다.

5.7.1전반적 동작

현대 x86-64 프로세서는 슈퍼스칼라(super-scalar)이고 비순차 실행(out-of-order execution, OoO)한다. 두 단어가 길어서 무서워 보이지만, 의미는 단순하다.

• 슈퍼스칼라: 한 사이클에 여러 개의 명령을 동시에 발행한다(issue). Haswell은 사이클당 최대 4개.
• 비순차 실행: 코드에 적힌 순서가 아니라 입력이 준비된 순서로 명령을 실행한다. 단, 결과는 원래 순서대로 보이도록 정리한다(retirement).

프론트엔드는 명령어를 디코딩해서 마이크로 연산(μops)으로 쪼갠다. 예를 들어 addq (%rax), %rdx는 "메모리에서 로드"와 "정수 덧셈" 두 개의 μop으로 나뉜다. 이 μop들은 예약 스테이션(reservation station)에 대기하다가, 자기 입력이 준비되면 가용한 기능 단위(functional unit)로 보내진다.

결과적으로, 코드의 명령 순서는 단지 의존 관계의 단서일 뿐이다. 진짜로 중요한 건 데이터 의존성 그래프다.

5.7.2기능 단위 성능

각 연산의 비용은 두 숫자로 표현된다.

• 지연(latency): 연산 시작부터 결과가 나올 때까지 걸리는 사이클.
• 발행 시간(issue time): 같은 종류의 연산을 얼마나 자주 발행할 수 있는가. 0.5는 사이클당 두 개를 시작할 수 있다는 뜻.
• 용량(capacity): 해당 기능 단위가 몇 개 있는가.

(Haswell 마이크로아키텍처 기준 근사값. 정확한 수치는 각 세대마다 다름.)

주목할 점. 부동소수점 곱셈의 발행 시간이 0.5라는 건 2개의 곱셈 단위가 파이프라이닝되어 있어 매 사이클 한 개씩(혹은 사이클당 두 개씩) 새 곱셈을 시작할 수 있다는 의미다. 결과는 5사이클 뒤에 나오지만, 그 5사이클 동안에도 다른 곱셈 5개가 동시에 진행 중일 수 있다. 이게 병렬성의 잠재력이다 — 우리 코드가 그 잠재력을 살리느냐가 관건.

5.7.3프로세서 동작의 추상 모델

루프의 한 반복을 데이터 흐름 그래프(data-flow graph)로 그려보자. 노드는 연산, 간선은 "이 결과가 저쪽 입력으로 들어간다"는 의존이다. combine4의 곱셈 버전 한 반복은 이렇게 생겼다.

load data[i] ──┐
               ├──→ mul ──→ (다음 반복의 acc)
   acc ────────┘

load와 mul이 한 반복의 비용. 그런데 mul의 결과가 다음 반복의 acc가 되므로, 반복들이 한 줄로 줄지어 의존한다. 이걸 임계 경로(critical path)라 부른다. 임계 경로의 총 길이가 곧 실행 시간의 하한선이다.

실수 곱셈의 지연이 5사이클이라면, 단일 누산기로는 한 반복당 최소 5사이클이다. CPE 5.0이 한계. 그 아래로 내려가려면 임계 경로를 분리해야 한다 — 그게 다중 누산기와 재결합이다.

5.8루프 언롤링 (Loop Unrolling)

반복마다 인덱스 증가, 종료 조건 비교, 분기가 들어간다. 이 오버헤드를 줄이려면 한 반복에서 여러 원소를 처리하면 된다. 4-way 언롤링 예시:

4-way 루프 언롤링void combine5(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_length(v);
    long limit = length - 3;          // 4개씩 처리하다 모자라면 잔여 처리
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    // 본 루프: 한 반복에 4개씩
    for (i = 0; i < limit; i += 4) {
        acc = ((acc OP data[i]) OP data[i+1])
              OP data[i+2] OP data[i+3];
    }
    // 잔여 처리
    for (; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

루프 제어 비용이 줄고, 컴파일러가 메모리 로드를 미리 발행할 여지도 늘어난다. 하지만 임계 경로는 그대로다. acc가 4번의 OP를 직렬로 거치기 때문이다. 실수 곱셈 같은 long-latency 연산에서는 CPE가 거의 안 줄어든다.

정수 덧셈은 발행 시간(0.5)이 워낙 짧아서 루프 오버헤드가 보였던 거고, 곱셈류는 그 자체가 길어서 오버헤드가 묻혀 있었던 셈이다.

5.9병렬성 향상

진짜 게임은 임계 경로를 자르는 데 있다. 두 가지 기법.

5.9.1다중 누산기 (Multiple Accumulators)

결합법칙이 성립하는 연산이라면 누산을 둘로 쪼갤 수 있다. 짝수 인덱스는 acc0에, 홀수 인덱스는 acc1에. 마지막에 둘을 합친다.

2×2 언롤 + 다중 누산기void combine6(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data = get_vec_start(v);
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;

    for (i = 0; i < limit; i += 2) {
        acc0 = acc0 OP data[i];      // 짝수 누산기
        acc1 = acc1 OP data[i+1];    // 홀수 누산기 — 의존 사슬이 다르다!
    }
    for (; i < length; i++) {
        acc0 = acc0 OP data[i];
    }
    *dest = acc0 OP acc1;            // 마지막에 합친다
}

acc0과 acc1은 서로 의존하지 않으므로 두 사슬이 병렬로 진행된다. 실수 곱셈 한 사이클당 두 개를 발행할 수 있는 머신에서, 임계 경로는 절반이 된다 — CPE 5.0 → 2.5 정도.

그럼 누산기를 더 늘리면? 일정 지점까지는 더 좋아진다. 하지만 한계가 있다.

• 해당 연산의 기능 단위 개수 × 1/지연이 이론적 최대 처리율이다. 실수 곱셈은 단위 2개, 지연 5 → 사이클당 2/5 = 0.4 처리. 즉 CPE의 하한은 약 0.5.
• 누산기가 많아지면 레지스터를 점점 더 잡아먹는다. x86-64는 16개의 GP 레지스터, 16개의 XMM/YMM. 너무 많으면 레지스터 스필링이 발생한다(5.11.1).

5.9.2재결합 변환 (Reassociation Transformation)

같은 4개를 한 번에 처리하더라도, 괄호를 어떻게 묶느냐로 의존 사슬이 달라진다.

// (A) 직선 사슬: ((acc OP x0) OP x1) OP x2) OP x3
//     acc → +x0 → +x1 → +x2 → +x3 (depth 4)

// (B) 재결합:    acc OP ((x0 OP x1) OP (x2 OP x3))
//     (x0+x1)와 (x2+x3)는 acc와 무관하게 미리 계산 가능
//     acc 사슬은 1단만 늘어난다

(A)는 임계 경로가 4단, (B)는 1단. (B) 쪽이 임계 경로가 짧다. 정수에서는 결합법칙이 정확히 성립하므로 컴파일러도 가끔 이 변환을 한다. 부동소수점은 다른 얘기다.

실전에서는 다중 누산기와 재결합을 함께 쓰는 경우가 많다. 둘 다 임계 경로를 줄이는 같은 가족의 기법이다.

5.10결합 코드 최적화 결과 요약

지금까지 베이스라인부터 다중 누산기까지 가져온 변환을 한 표로. 같은 머신, 같은 데이터.

(숫자는 책 본문에서 인용한 Haswell 측정치 근사값.)

흥미로운 점은 combine6 (10×10)이 일부 항목에서 이론적 하한을 살짝 밑돌거나 맞닿는다는 것이다. 반대로 정수 덧셈은 발행 시간 0.5 한계를 넘기지 못한다. 최적화는 하한을 향해 다가가는 게임이다.

5.11일부 한계 요인

5.11.1레지스터 스필링 (Register Spilling)

누산기를 20개로 늘리면 어떨까? x86-64의 정수 레지스터는 16개, XMM/YMM도 16개. 활동 변수가 너무 많으면 컴파일러가 일부를 스택에 쏟아낸다(spill). 매 반복마다 스택을 통해 메모리 R/W가 일어나면, 우리가 5.6에서 그토록 피했던 메모리 왕복이 부활한다.

# 누산기가 너무 많아 스필이 발생한 경우 (개념적)
movsd  acc8, -16(%rsp)   # 스택에서 로드
mulsd  data[i+8], acc8   # 곱셈
movsd  acc8, -16(%rsp)   # 다시 스택으로 저장

결국 누산기 수에는 스위트 스폿이 있다. 보통 4~10개 사이. 그 이상은 오히려 손해. 머신마다, 데이터 타입마다 최적값이 다르므로 측정해서 찾는 수밖에 없다.

5.11.2분기 예측과 잘못된 예측 패널티

파이프라인은 명령을 미리 가져와 디코딩한다. 분기를 만나면 어디로 갈지 모르므로 분기 예측기(branch predictor)가 도박을 한다. 맞으면 그대로 진행, 틀리면 파이프라인을 비우고 다시 채운다 — Haswell 기준 약 15~20 사이클의 패널티.

예측기는 패턴을 잘 잡는다. 루프 종료 조건처럼 거의 항상 한 방향인 분기, 특정 if문이 입력에 따라 규칙적으로 바뀌는 패턴 등은 95~99% 적중한다. 문제는 데이터에 의존하면서 무작위적인 분기다.

유명한 정렬 vs 무작위 데이터 비교// 0~255 사이의 값을 가진 배열에서 128 이상만 합산
long sum = 0;
for (int i = 0; i < n; i++) {
    if (data[i] >= 128) {           // ← 데이터에 따라 분기
        sum += data[i];
    }
}

같은 코드가 정렬된 배열에서는 무작위 배열보다 5~6배 빠르다. 정렬되어 있으면 분기는 "전부 false → 어느 시점부터 전부 true"가 되어 예측기가 거의 완벽하게 맞힌다. 무작위면 매번 50% 확률로 빗나가서 파이프라인이 끊임없이 비워진다.

대처법.

• 분기 자체를 없애기: cmov(조건부 이동) 명령을 쓰는 형태로 코드를 재작성. (data[i] >= 128) ? data[i] : 0 같은 삼항식이 종종 cmov로 컴파일된다.
• 분기 없는 비트 마스킹: sum += data[i] & -(data[i] >= 128) 같은 트릭. 가독성은 떨어진다.
• 예측기 친화적으로 데이터 정렬: 가능하면 정렬해서 처리.
• __builtin_expect(GCC): 자주 가는 방향을 컴파일러에 알려준다. 코드 레이아웃 최적화에 도움.

5.12메모리 성능 이해하기

지금까지 우리가 잰 CPE는 데이터가 L1 캐시에 다 들어가는 작은 배열에서의 수치다. 실제 워크로드는 캐시를 벗어나 메모리까지 가는 일이 많고, 거기서는 또 다른 게임이 펼쳐진다. 6장에서 다룰 캐시 얘기는 잠시 미뤄두고, 여기서는 로드/스토어 자체의 마이크로아키텍처만 본다.

5.12.1로드 성능

Haswell의 로드 유닛은 2개. 사이클당 2개의 로드를 발행할 수 있다. 지연은 L1 히트 시 4~5사이클. 그러나 비순차 실행 덕에, 결과를 바로 쓰지 않는 한 이 지연은 잘 가려진다.

그럼 로드가 병목이 되는 경우는? 포인터 추적(pointer chasing)이 대표적이다. 연결 리스트 순회처럼 다음 주소가 직전 로드 결과에 의존하면, 로드가 직렬화된다.

// 매 반복의 next 주소가 직전 로드 결과에 의존
// → 로드 지연이 그대로 임계 경로
while (p) {
    sum += p->val;
    p = p->next;
}

반대로 배열 순회처럼 다음 주소가 인덱스로 결정되면, CPU가 미리 여러 로드를 발행할 수 있어 지연이 거의 보이지 않는다. 자료구조 선택이 곧 성능이라는 명제는 여기서 기인한다.

5.12.2스토어 성능 (Store-to-Load Forwarding)

스토어는 좀 다르다. CPU는 스토어를 스토어 버퍼(store buffer)에 일단 모은 뒤, 나중에 메모리/캐시에 반영한다. 이 사이에 같은 주소를 읽는 로드가 들어오면, 메모리까지 가지 않고 스토어 버퍼에서 직접 값을 받아간다 — store-to-load forwarding.

문제는 이 포워딩이 의존 관계를 만든다는 것. 로드는 스토어가 끝나야 시작할 수 있다. 다음 코드가 대표적인 함정이다.

조건부 의존: 데이터에 따라 임계 경로가 달라진다// src와 dst가 같은 배열을 가리킬 수도 있는 함수
void copy_array(long *src, long *dst, long n) {
    for (long i = 0; i < n; i++) {
        dst[i] = src[i];          // dst에 쓴 값을 다음에 src로 다시 읽을 수도
    }
}

src == dst이면 매 반복에서 dst[i]로 쓴 값이 곧이어 src[i+1] 같은 주소로 읽힐 수 있다(인덱스가 겹치면). 그러면 스토어→로드 의존이 생겨서 파이프라인이 직렬화된다. CPU는 보수적으로, 같은 주소가 아닌 게 확실해질 때까지 포워딩 메커니즘에서 대기시킨다.

앨리어싱이 없다는 걸 컴파일러에 알려주는 게 restrict 키워드의 역할이다. memcpy가 그렇게 빠른 이유 중 하나도 "겹치지 않는다"는 가정 때문이다. (겹칠 수 있을 때는 memmove를 써야 한다.)

5.13실세계: 성능 향상 기법 일반 원칙

한 발 떨어져서 정리하자. 이 장에서 본 변환은 다 같은 노래의 변주다.

1. 측정 먼저. 어떤 변환을 적용하기 전에 베이스라인을 잡고, 후보를 적용한 뒤 같은 환경에서 다시 잰다. 측정 없이 짐작으로 손대면 거의 항상 망친다.
2. 알고리즘 변경 > 미시 최적화. O(n²)를 O(n log n)으로 바꾸는 게 4-way 언롤보다 99% 더 큰 효과를 낸다. 마이크로 최적화는 알고리즘이 이미 최선일 때 의미 있다.
3. 핫스폿에 집중. Amdahl의 법칙: 실행 시간의 5%인 코드를 100배 빨라지게 해도 전체 속도는 5%만 줄어든다. 프로파일러로 시간 잡아먹는 곳을 먼저 찾는다.
4. 의존 사슬 끊기. 슈퍼스칼라 + OoO를 살리려면 데이터 흐름 그래프의 임계 경로를 줄여야 한다. 다중 누산기, 재결합, SIMD 모두 같은 목표.
5. 메모리 패턴이 곧 성능. 캐시·프리페치·앨리어싱·스토어 포워딩 모두 메모리 접근 패턴에 묶여 있다. 6장에서 깊이 본다.
6. 가독성 비용 의식. 손 최적화한 코드는 유지보수가 어렵다. 그만한 가치가 있는 핫 코드에만, 주석을 충분히 달고 적용한다.

5.14성능 병목 식별

5.14.1프로그램 프로파일링

프로파일러는 "어디서 시간이 가장 많이 가는가"를 알려준다. 두 가지 방식이 있다.

• 인스트루먼테이션(instrumentation): 컴파일 시점에 함수 진입/종료를 측정하는 코드를 끼워 넣는다. 정확하지만 오버헤드가 크다. gcc -pg + gprof가 대표.
• 샘플링(sampling): 일정 주기로 프로그램 카운터를 들여다보고, 어느 함수에 있었는지 기록한다. 통계적이지만 오버헤드가 거의 없다. Linux perf가 표준.

gprof 워크플로# 1) 프로파일링 정보를 포함해 컴파일
gcc -O2 -pg -o prog prog.c

# 2) 평소처럼 실행 (gmon.out이 생성됨)
./prog input.txt

# 3) 보고서 보기
gprof prog gmon.out > report.txt

perf로 더 풍부한 정보# 시간만이 아니라 캐시 미스, 분기 미스 같은 하드웨어 카운터까지
perf stat -e cycles,instructions,cache-misses,branch-misses ./prog

# 핫 함수 + 핫 라인 식별
perf record -g ./prog
perf report

5.14.2프로파일러 가이드 최적화

프로파일러 결과는 종종 직관과 다르다. "이 함수가 느릴 줄 알았는데 멀쩡하고, 신경 안 쓰던 함수가 총 시간의 60%를 먹고 있더라"는 일이 흔하다. 그래서 측정 → 가설 → 변환 → 재측정의 루프를 돈다.

한 단계 더 나아간 기법이 PGO(Profile-Guided Optimization)다. 프로그램을 한번 평소처럼 돌려서 분기 빈도/호출 빈도를 측정한 뒤, 그 정보를 바탕으로 다시 컴파일한다. 컴파일러는 이 데이터를 활용해 인라이닝 결정, 코드 레이아웃, 분기 예측 힌트를 더 잘 골라낸다. 대형 프로젝트에서 5~15% 정도 성능 향상이 흔하다.

# gcc PGO 워크플로 (개념)
gcc -O2 -fprofile-generate -o prog prog.c
./prog typical-workload.txt        # 프로파일 수집
gcc -O2 -fprofile-use     -o prog prog.c

5.15요약

• 컴파일러는 안전을 우선시한다. 메모리 앨리어싱·부수 효과 가능성이 있으면 보수적으로 동작한다. 사람이 그 빈틈을 메운다.
• CPE는 머신과 데이터 크기에 비교적 강건한 성능 단위다. 같은 단위로 측정해야 비교가 의미 있다.
• 흔한 베이스라인 함정은 (1) 루프 조건의 비싼 호출, (2) 매 반복의 함수 호출, (3) 누산값의 메모리 왕복 — 셋 다 한 번씩 걷어내면 CPE가 절반에서 1/3로 떨어진다.
• 현대 프로세서는 슈퍼스칼라 + OoO다. 코드의 명령 순서가 아니라 데이터 흐름 그래프의 임계 경로가 진짜 시간이다.
• 루프 언롤링은 제어 오버헤드를 줄이지만, 그것만으로는 임계 경로를 줄이지 못한다. 다중 누산기와 재결합이 임계 경로를 끊는 도구.
• 너무 많은 누산기는 레지스터 스필링으로 역효과. 4~10개 정도가 보통의 스위트 스폿.
• 분기 예측 미스는 비싸다(15~20 사이클). 데이터 의존적이고 무작위적인 분기는 cmov, 비트 마스킹, 데이터 정렬로 다스린다.
• 메모리에서는 로드의 직렬화(포인터 추적)와 store-to-load forwarding이 미시 병목을 만든다.
• 정수 결합법칙은 안전하지만, 부동소수점 재결합은 결과를 바꿀 수 있다. 정확성이 중요한 코드에서는 -Ofast나 손 재결합을 신중하게.
• 실제 작업 순서는 알고리즘 → 핫스폿 식별 → 마이크로 최적화. 프로파일러를 친구로 두자.

void to_upper(char *s) {
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] >= 'a' && s[i] <= 'z')
            s[i] -= ('a' - 'A');
    }
}

// (i) 직선 누산
double sum_i(double *a, long n) {
    double s = 0.0;
    for (long i = 0; i < n; i++) s += a[i];
    return s;
}

// (ii) 4개의 누산기 + 재결합
double sum_ii(double *a, long n) {
    double s0=0, s1=0, s2=0, s3=0;
    long i;
    for (i = 0; i < n - 3; i += 4) {
        s0 += a[i];   s1 += a[i+1];
        s2 += a[i+2]; s3 += a[i+3];
    }
    for (; i < n; i++) s0 += a[i];
    return (s0 + s1) + (s2 + s3);
}

long product(long *a, long n) {
    long acc0 = 1, acc1 = 1, acc2 = 1;
    long i;
    for (i = 0; i < n - 2; i += 3) {
        acc0 *= a[i];
        acc1 *= a[i+1];
        acc2 *= a[i+2];
    }
    for (; i < n; i++) acc0 *= a[i];
    return (acc0 * acc1) * acc2;
}