switch문, 그냥 if-else 묶음 아니었어?
C나 C++ 코드에서 switch는 정말 자주 쓰죠. 그런데 이게 실제 기계어로 어떻게 바뀌는지 생각해본 적 있나요? "if-else를 줄줄이 늘어놓은 거겠지" 하고 넘기는 분이 많은데요. 실제로 컴파일러는 상황에 따라 완전히 다른 여러 전략 중 하나를 골라요. 이번에 GCC가 switch를 어떻게 로우어링(lowering)하는지 파고든 글이 나왔어요. 컴파일러가 얼마나 꼼꼼하게 일하는지 보여주는 좋은 예라서 쉽게 풀어볼게요.
로우어링이 뭐냐면, switch 같은 고수준 문법을 CPU가 실제로 할 수 있는 비교, 점프, 메모리 읽기 같은 저수준 동작으로 "낮춰서" 바꾸는 과정이에요. GCC에는 GIMPLE이라는 중간 표현 단계에서 이 일만 따로 맡는 최적화 단계(패스)가 있어요.
전략 1: 점프 테이블
case 값이 1, 2, 3, 4, 5처럼 촘촘하게 모여 있으면 컴파일러는 점프할 주소를 담은 배열을 하나 만들어요. 입력값에서 최솟값을 빼고, 범위 안에 드는지 한 번 확인한 다음, 배열에서 주소를 꺼내 바로 점프해요.
아파트 우편함을 떠올려보세요. 101호 편지를 찾으려고 우편함을 전부 열어볼 필요 없이 호수만 보고 바로 찾아가잖아요. case가 100개여도 사실상 비교 한 번으로 끝나니까 O(1)이에요.
대신 값이 1, 1000, 50000처럼 띄엄띄엄 있으면 배열에 빈칸이 잔뜩 생겨서 메모리가 낭비돼요. 그래서 GCC는 "case 개수에 비해 테이블이 몇 배까지 커져도 괜찮은가"를 기준으로 판단해요(--param jump-table-max-growth-ratio-for-speed 같은 옵션이 이 기준이에요). 또 case가 너무 적으면 테이블을 쓰는 비용이 더 크니까 그냥 비교문을 만들어요. 그 개수 기준이 case-values-threshold예요.
전략 2: 비트 테스트
이건 꽤 똑똑한 트릭이에요. 아래 코드를 볼게요.
switch (c) {
case ' ': case '\t': case '\n': case '\r':
return 1;
default:
return 0;
}
case는 여러 개지만 가는 곳은 하나예요. 이럴 때 GCC는 각 case 값을 비트 위치로 보고 마스크를 하나 만들어요. 마스크는 "이 위치의 비트가 켜져 있으면 해당 case"라고 표시해둔 숫자예요. 그다음 (1 << (c - 기준값)) & 마스크가 0이 아니면 그 case로 보내는 식이에요. 분기를 여러 번 하는 대신 시프트 한 번, AND 한 번으로 끝나요. 값의 범위가 레지스터 크기(64비트 등) 안에 들어오고, 갈 곳의 종류가 몇 개 안 될 때 이 방법을 써요.
전략 3: 이진 결정 트리
값이 흩어져 있어서 테이블도 비트 테스트도 맞지 않으면, 컴파일러는 if-else를 일렬이 아니라 트리 모양으로 배치해요. "x < 500인가?"로 반을 나누고, 나뉜 쪽을 다시 반으로 나누는 식이에요. 그러면 case가 n개일 때 비교 횟수가 대략 log n번이에요. 업다운 숫자 맞히기 게임에서 중간값부터 부르는 것과 같은 원리예요.
핵심은 섞어 쓰기
진짜 재밌는 부분은 GCC가 이 전략들을 switch 하나 안에서 섞어 쓴다는 거예요. case 값을 정렬한 뒤 덩어리(클러스터)로 나눠요. 예를 들어 "1~20은 촘촘하니까 점프 테이블", "이 몇 개는 가는 곳이 같으니까 비트 테스트", "나머지는 하나씩 비교" 하는 식이에요. 그리고 이 덩어리들 위에 이진 트리를 세워요. 덩어리를 최대한 적게, 효율적으로 나누는 데는 동적 계획법(DP) 기반 알고리즘을 쓰는데, LLVM도 비슷한 방식을 써요.
여기에 switch conversion이라는 최적화가 하나 더 있어요. case마다 상수 하나만 대입하는 단순한 switch라면 분기 자체를 없애고, 상수 배열에서 값을 꺼내는 코드로 바꿔버려요. 바이너리를 열어봤을 때 CSWTCH.123 같은 이름의 심볼이 보인다면 바로 이 최적화가 만든 배열이에요.
업계 맥락: 점프 테이블이 늘 정답은 아니에요
점프 테이블은 간접 분기를 써요. 간접 분기는 점프할 주소가 코드에 고정돼 있지 않고 실행 중에 정해지는 분기예요. 2018년 Spectre 취약점 이후 간접 분기를 안전하게 만드는 retpoline 같은 완화 기법이 들어오면서 간접 분기 비용이 크게 늘었어요. 그래서 리눅스 커널은 retpoline을 켠 x86 빌드에서 -fno-jump-tables로 점프 테이블을 아예 끄기도 했어요. 어떤 전략이 가장 빠른지는 하드웨어와 보안 환경에 따라 달라진다는 걸 보여주는 사례예요.
Clang/LLVM도 기본 아이디어는 같지만 세부 판단 기준이나 프로파일 정보를 쓰는 방식이 달라요. 그래서 같은 코드도 두 컴파일러가 서로 다른 어셈블리를 내놓을 때가 많아요. Compiler Explorer(godbolt.org)에서 나란히 비교해보면 꽤 재밌어요.
한국 개발자에게 주는 시사점
- switch를 손으로 if-else로 바꿔서 "최적화"하지 마세요. 그건 컴파일러가 훨씬 잘해요. 오히려 enum을 0부터 연속으로 정의하는 식으로 case 값을 촘촘하게 설계하는 게 컴파일러를 돕는 방법이에요.
- 인터프리터, 파서, 프로토콜 처리 코드처럼 switch가 성능에 민감한 핵심 경로(핫패스)에 있다면 생성된 어셈블리를 한 번쯤 확인해보세요.
-O2로 컴파일한 결과를 godbolt에서 보기만 해도 배울 게 많아요. - 임베디드나 보안에 민감한 환경이라면
-fno-jump-tables,--param case-values-threshold같은 옵션이 왜 있는지 알아두세요. 디버깅할 때 큰 도움이 돼요.
마무리
한줄 정리: switch문 하나에도 점프 테이블, 비트 테스트, 이진 트리를 상황에 맞게 섞어 쓰는 컴파일러의 계산이 숨어 있어요.
여러분은 성능 때문에 컴파일러가 만든 어셈블리를 직접 들여다본 적이 있나요? 예상과 다른 코드가 나와서 놀랐던 경험이 있다면 공유해 주세요!
🔗 출처: Hacker News