C/C++의 switch 문은 소스 코드에서 보이는 것보다 훨씬 복잡한 구조물이다. 개발자는 흔히 "조건이 많으면 if-else보다 빠르다" 정도로 알고 있지만, 실제로 컴파일러가 switch를 어떤 기계어로 바꿀지는 단순하지 않다. 최근 공개된 한 분석 글은 GCC(-O3 기준)가 switch를 점프 테이블, 비트셋, 비교 트리 등 여러 전략으로 변환하는 과정과 그 판단 기준을 소스 코드 수준에서 추적한다. 참고로 비트셋 변환을 제외한 대부분의 최적화는 clang에도 동일하게 적용된다.
점프 테이블과 밀집도
가장 직관적인 예는 입력값 x에 따라 f0, f1 같은 함수를 호출하는 경우다. 사람이 직접 짠다면 함수 포인터 배열을 만들고 입력을 인덱스로 쓸 것이고, 컴파일러도 같은 선택을 해 switch를 점프 테이블로 바꾼다. 값들이 상수만큼 일정하게 떨어져 있는 경우(오프셋)도 인식한다. 다만 값이 듬성듬성 흩어질수록 점프 테이블은 손해다. 실험을 통해 확인한 GCC의 임계값은 '케이스 레이블 하나당 점프 테이블 항목 약 8개'다. 이 비율을 넘어가면 점프 테이블 대신 비교 트리로 펼쳐진다. 흥미롭게도 컴파일러는 전체가 희소해도 밀집된 부분집합을 따로 찾아낸다. 예를 들어 1~5번 케이스에 100이라는 외톨이 값이 끼면, 100은 단일 분기로 처리하고 1~5는 점프 테이블로 묶는다.
값이 0~87 사이에 20개 레이블이 흩어진 경우를 보면 휴리스틱이 레이블 수가 아니라 비교 횟수를 기준으로 작동한다는 점이 드러난다. 88개 항목짜리 테이블은 88 < 20×8이므로 레이블 기준으로는 이득처럼 보이지만, GCC는 비교문으로 펼쳤다. 이유는 연속된 케이스들이 이미 범위로 합쳐져 네 번이 아니라 두 번의 비교로 처리되기 때문이다. 총 비교 횟수 10을 기준으로 삼으면 10×8 < 88이 되어 점프 테이블이 불리하다는 계산이 맞아떨어진다.
비트셋이라는 또 다른 길
때로는 cmp도 점프 테이블도 없이 bt(비트 테스트) 명령과 2753205 같은 정체불명의 상수가 등장한다. 이 상수를 2진수로 풀어 보면 하나의 비트셋이며, 1로 설정된 비트들이 케이스 레이블의 ASCII 값에서 48을 뺀 위치에 대응한다. 문자 분류처럼 값들이 좁은 구간에 모여 있을 때 GCC가 쓰는 비트셋 변환이다. 이 전략은 clang에는 없다.
컴파일러 내부의 판단 구조
이 모든 결정은 pass_lower_switch 패스가 analyze_switch_statement를 호출하며 이뤄진다. GCC의 내부 표현인 Gimple 단계에서 각 레이블은 이미 상한·하한 값을 가진 범위로 합쳐져 있고, 레이블마다 simple_cluster가 할당된다. 여기엔 값의 범위, 해당 출력 엣지, 그리고 그 클러스터가 선택될 확률(기본은 균등, PGO로 조정 가능)이 담긴다. 이후 비트셋으로 묶을 수 있는 구간, 점프 테이블로 묶을 구간을 차례로 찾고, 남은 것은 비교 트리로 넘긴다. 즉 비트셋과 점프 테이블은 결정 트리의 잎 노드가 되는 셈이다.
비트셋과 점프 테이블 모두 동적 계획법으로 '최소 개수'의 묶음을 찾은 뒤, is_beneficial 검사로 이득이 없는 작은 묶음을 쳐낸다. 변환 가능 여부는 can_be_handled가 판단하는데, 레이블 수 대 테이블 항목 수의 비율과 오버플로를 확인한다. 핵심 비율은 최적화 목표에 따라 달라진다. 속도 최적화(-O1/2/3/fast)에서는 8, 크기 최적화(-Os)에서는 2가 쓰인다. 또 점프 테이블은 간접 점프와 경계 검사라는 고정 비용이 있어 최소 케이스 수를 요구한다. 이 기준값을 정하는 case_values_threshold는 아키텍처마다 다르지만 현대 x64·Arm64에서는 5로 기본 설정된다.
실무자에게 주는 시사점
어느 변환도 불가능하면 GCC는 비교의 이진 트리로 되돌아간다. 이때 각 클러스터의 확률을 고려해 양쪽 절반의 확률이 같아지도록 분할하고 재귀적으로 트리를 만든다. 확률은 PGO 또는 __builtin_expect_with_probability로 줄 수 있다는 점은 성능에 민감한 코드에서 기억해 둘 만하다.
정리하면, switch의 성능은 작성자가 생각하는 '분기 개수'보다 값의 밀집도, 연속성, 그리고 최적화 플래그에 더 크게 좌우된다. 희소한 값을 억지로 점프 테이블로 만들려는 미세 최적화는 대개 컴파일러가 이미 더 정교하게 판단하고 있으며, 반대로 성능이 중요한 분기라면 PGO나 기대 확률 힌트를 제공하는 편이 트리 모양 자체를 개선하는 현실적인 수단이다. 다만 이 수치들은 실험과 특정 버전의 소스를 근거로 한 것이므로, 아키텍처와 컴파일러 버전에 따라 임계값이 달라질 수 있다는 한계는 염두에 둬야 한다.