CPU 분기 예측: 코드 속 숨은 병목

스택오버플로에 조회수 300만 회가 넘는 유명한 답변이 있습니다. 질문은 이렇습니다. 정렬된 배열을 처리하는 것이 정렬되지 않은 배열보다 왜 빠를까? 코드는 동일합니다. if 문이 있는 루프일 뿐이죠. 차이는 입력 배열이 정렬되어 있는지뿐입니다. 정렬된 쪽이 6배 빠르게 돌아갑니다. 그 답은 CPU 분기 예측에 있으며, 이는 현대 컴퓨팅에서 가장 큰 영향을 주는 성능 요인 중 하나를 보여줍니다.

모든 if 문, 모든 루프 조건, 모든 switch 케이스가 코드 속 분기입니다. CPU는 초당 수십억 개의 분기를 만나고, 실제 결과를 알기 전에 각각의 결과를 미리 맞혀야 합니다. 예측이 맞으면 실행은 full 속도로 계속됩니다. 틀리면 CPU는 10~20 사이클치 작업을 버리고 처음부터 다시 시작합니다. 이 메커니즘을 이해하면 성능이 중요한 코드를 보는 시각이 달라집니다.

왜 CPU는 예측해야 할까

현대 CPU는 파이프라인 구조입니다. 한 명령어가 끝나기를 기다렸다가 다음 명령어를 시작하지 않습니다. 일반적인 CPU 파이프라인은 12~20단계로 깊습니다. 한 명령어가 실행되는 동안 그다음 15개 정도의 명령어는 이미 가져오기, 디코딩, 준비가 진행 중입니다. 이런 파이프라이닝 덕분에 각 명령어가 여러 사이클이 걸리더라도 CPU는 대략 사이클당 한 명령어를 처리할 수 있습니다.

하지만 CPU가 분기(if x > 0)를 만나면 문제가 생깁니다. 다음 명령어가 분기가 taken인지 not taken인지에 따라 달라지기 때문입니다. 비교 결과가 파이프라인을 타고 내려오는 데 몇 사이클이 걸려서, CPU는 그 전까지 결과를 알 수 없습니다. 선택지는 두 가지입니다. 파이프라인을 멈추고 기다리거나(15사이클 넘게 아무것도 하지 않고 낭비), 분기 방향을 추측하고 계속 작업하거나.

CPU는 항상 추측합니다. 분기 예측기가 방향을 정하면 CPU는 그 예측된 경로를 따라 명령어를 가져와 실행합니다. 예측이 맞으면 낭비되는 것은 없습니다. 틀리면 잘못 실행된 명령어를 플러시하고 결과를 버린 뒤 올바른 경로에서 다시 시작해야 합니다. 이른바 ‘파이프라인 플러시’는 최신 x86 CPU에서 대략 15~20 사이클이 듭니다. 명령어 15~20개분의 작업이 날아가는 셈입니다.

분기 예측기는 어떻게 동작할까

최신 분기 예측기는 놀라울 만큼 정교합니다. 각 분기 명령어의 과거 기록을 학습하는 패턴 매칭 하드웨어라고 보면 됩니다.

단순한 경우: 편향된 분기

많은 분기는 강하게 편향되어 있습니다. 거의 항상 같은 방향으로 가죠. 99.9%의 확률로 성공하는 에러 체크나, 999번은 참이고 한 번만 거짓이 되는 루프 조건 같은 것입니다. 분기 예측기는 이런 패턴을 빠르게 학습해서 거의 완벽한 정확도를 냅니다. 99%의 확률로 같은 방향을 가는 분기는 예측 실패율이 최대 1%입니다.

패턴 인식

최신 예측기는 단순한 편향 추적을 넘어섭니다. 반복되는 패턴을 인식하죠. 분기가 taken-taken-not-taken-taken-taken-not-taken... 처럼 주기 3의 패턴을 따르면, 예측기는 이 패턴을 학습해 정확히 맞힙니다. 인텔과 AMD의 최신 CPU가 쓰는 TAGE(TAgged GEometric history length) 예측기는 서로 다른 히스토리 길이를 가진 여러 테이블을 유지해서, 주기 2부터 수백까지의 패턴을 잡아냅니다.

상관관계가 있는 분기

가장 발전된 예측기는 분기들 사이의 상관관계도 학습합니다. 분기 A가 taken이면 (코드상 뒤에 있는) 분기 B는 항상 not taken이라는 관계가 있다면, 예측기는 이 관계를 학습할 수 있습니다. 이를 ‘2단계 적응형 예측(two-level adaptive prediction)’이라 부르며, 다음과 같은 코드 패턴을 처리합니다.

// These branches are correlated
if (x > 0) {      // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) {     // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracy

정렬 배열 미스터리 풀기

처음의 스택오버플로 질문으로 돌아가 봅시다. 문제의 코드는 이렇게 생겼습니다.

int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128)    // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cycles

데이터가 정렬되어 있으면 분기는 완벽하게 예측 가능합니다. 배열 앞 절반은 not taken, 뒤 절반은 taken입니다. 예측기는 각 구간을 금방 학습하고, 전환 지점 한 곳에서만 틀립니다. 데이터가 무작위면 분기는 사실상 동전 던지기입니다. 예측기는 50% 이상 맞출 수 없고, 반복의 절반이 파이프라인 플러시로 15 사이클씩 날아갑니다.

10만 번 반복에 약 50% 예측 실패율이면 50,000번의 실패 × 15 사이클 = 750,000 사이클이 낭비됩니다. 3GHz CPU에서는 약 0.25밀리초입니다. 이 단순한 루프의 전체 실행 시간에서 꽤 큰 비중입니다.

CPU는 분기를 얼마나 기억할 수 있을까

분기 예측기의 저장 공간은 한정되어 있습니다. 예측기는 분기 대상 버퍼(BTB, Branch Target Buffer)와 관련 히스토리 테이블이라는 구조로 유한한 수의 분기 위치를 추적합니다. 최신 CPU는 수만 개의 분기 위치를 추적할 수 있지만, 큰 코드베이스는 이를 넘어설 수 있습니다.

서로 다른 두 분기 명령어가 같은 예측기 엔트리에 매핑되면(BTB는 명령어 주소의 해시로 인덱싱되므로) 서로의 예측을 방해합니다. 일반적인 코드에서는 드문 일이지만, 아주 큰 함수나 작은 함수가 많이 분기를 포함하는 경우에는 문제가 됩니다.

Daniel Lemire는 여러 CPU의 분기 예측기 용량을 측정한 훌륭한 연구를 발표했습니다. 결과에 따르면 최신 인텔 CPU(Alder Lake 이후)는 약 200개 분기 깊이까지의 히스토리를 효과적으로 예측할 수 있습니다. 즉 현재 분기를 예측할 때 최근 약 200개 분기의 결과를 고려한다는 뜻입니다. AMD CPU도 비슷한 수준입니다. ARM 칩은 편차가 더 크고, 애플 M 시리즈는 특히 강력한 분기 예측기를 갖추고 있습니다.

분기 예측 친화적인 코드 작성법

대부분의 코드에서는 분기 예측이 중요하지 않습니다. 예측기가 충분히 똑똑하고, 분기가 핫 루프 안에 있지도 않으니까요. 하지만 내부 루프, 데이터 처리 파이프라인, 파서, 코덱처럼 성능이 중요한 경로를 최적화할 때는 분기 동작이 실행 시간을 지배할 수 있습니다.

분기를 산술 연산으로 바꾸기

가장 빠른 분기는 존재하지 않는 분기입니다. 많은 조건문은 분기 없는 산술 연산으로 바꿀 수 있습니다.

// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo;  // CMOV
return t < hi ? t : hi;   // CMOV
}

현대 컴파일러는 단순한 조건문을 분기 없이 처리하는 CMOV(조건부 이동) 명령어로 잘 바꿉니다. 하지만 항상 가능하지는 않습니다. 특히 분기에 부작용이 있거나 ‘then’ 경로가 비쌀 때는 어렵습니다. 컴파일러가 최적 코드를 만들지 못하는 핫 루프에서는 명시적인 분기 없는 패턴이 도움이 됩니다.

처리 전에 정렬하기

분기로 데이터를 필터링할 생각이라면, 먼저 정렬해서 분기를 완벽하게 예측 가능하게 만들 수 있습니다. 정렬은 O(n log n) 오버헤드가 있어 직관에 반하는 것처럼 들리지만, 처리 루프가 많이 돌거나 분기 예측 실패 비용이 큰 대용량 데이터에서는 그 비용을 충분히 상쇄합니다.

룩업 테이블 사용하기

케이스가 많은 복잡한 조건 로직(switch 문)은 테이블 조회로 대체할 수 있습니다. 비교 연쇄 대신 배열을 인덱스로 찾아가는 방식입니다. 배열 접근이 캐시 미스를 일으킬 수 있지만, 보통 예측에 실패한 분기가 줄줄이 이어지는 것보다는 저렴합니다.

// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}

컴파일러에 힌트 주기

GCC와 Clang은 __builtin_expect를 지원해서 어느 분기 방향이 더 자주 일어나는지 컴파일러에 알려줄 수 있습니다. 이것이 CPU의 분기 예측기를 직접 제어하지는 않습니다(예측기는 런타임에 학습하니까요). 대신 컴파일러가 코드를 배치하는 방식에 영향을 줍니다. 자주 실행되는 경로를 점프 없이 일직선으로 배치하면 명령어 캐시 효과 덕분에 더 빨라집니다.

// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}

분기 동작 측정하기

하드웨어 성능 카운터를 사용하면 분기 예측 성능을 직접 측정할 수 있습니다. 리눅스에서는 perf stat으로 어떤 프로그램이든 예측 실패율을 확인할 수 있습니다.

# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256  branches          # 892.7M/sec
3,271,842  branch-misses     # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.

마이크로 벤치마크라면 Google Benchmark 같은 도구로 반복당 branch-misses를 추적할 수 있습니다. 코드 변경이 분기 동작을 개선했는지 정밀하게 알려줍니다. 다른 시스템 활동의 노이즈가 섞이는 벽시계 시간보다 훨씬 실용적인 지표입니다.

언제 신경 써야 하고, 언제 신경 쓰지 말아야 할까

분기 예측 최적화가 의미 있는 범위는 좁지만 중요합니다. 대량의 데이터를 처리하는 타이트한 내부 루프가 그렇습니다. 파서, 압축기, 이미지 처리, 수치 계산, 데이터베이스 쿼리 평가 등에서는 분기 동작이 실행 시간을 지배합니다.

그 밖의 대부분, 즉 비즈니스 로직, API 핸들러, CRUD 연산에서는 분기 예측이 무관합니다. 웹 서버의 요청 라우터에 있는 분기는 병목이 아닙니다. HTTP 요청마다 한 번 실행되는 코드를 읽기 좋은 if/else 체인에서 알아보기 힘든 분기 없는 산술 코드로 고칠 이유는 없습니다. 이론상 문제가 있을 것 같은 곳이 아니라, 프로파일러가 가리키는 곳을 최적화하세요.

분기 예측을 이해하는 진짜 가치는 수동 최적화에 있지 않습니다. 코드가 왜 그런 성능을 내는지 이해하는 데 있습니다. 프로파일러가 단순한 if 문이 있는 루프가 예상보다 느리다고 보여줄 때, 분기 예측 실패가 원인인 경우가 많습니다. 입력 데이터를 정렬했더니 처리가 마법처럼 빨라질 때, 그 이유가 분기 예측입니다. 이 사고 모델이 있으면 그렇지 않았다면 미스터리였을 성능 문제도 진단할 수 있습니다.