2024년 1월 14일 공개된 기술 블로그 포스트에서 GCC 컴파일러가 switch 문을 기계어로 변환하는 내부 로직이 상세히 설명되었습니다. 개발자들은 이 자료를 통해 컴파일러가 단순히 조건문을 나열하는 것이 아니라, 성능과 코드 크기에 따라 세 가지 전략 중 하나를 선택한다는 사실을 확인했습니다.
주요 전략은 점프 테이블, 비트셋 테스트, 그리고 이진 비교 트리입니다. GCC는 속도 최적화 모드인 -O1, -O2, -O3, -Ofast에서는 점프 테이블 항목 수와 필요한 비교 연산 수의 비율이 약 8 이하일 때만 점프 테이블을 생성합니다. 반면 크기 최적화 모드인 -Os에서는 이 비율이 2로 더 엄격하게 적용됩니다.
현대의 x64 및 Arm64 아키텍처에서는 case_values_threshold 함수가 기본값으로 5를 설정하고 있습니다. 이는 switch 문 안에 최소 5개 이상의 케이스 라벨이 존재해야 비로소 점프 테이블 생성을 검토한다는 의미입니다. 간접 분기와 경계 검사 자체가 오버헤드를 발생시키기 때문에, 너무 적은 수의 케이스에는 단순한 분기문이 더 효율적이라고 판단하기 때문입니다.
연속되지 않은 작은 범위의 값들이 등장할 경우, GCC는 분기 대신 x86의 bt 명령어를 사용하여 사전 계산된 비트 마스크 상수와 단일 비트 테스트를 수행하기도 합니다. 만약 점프 테이블도, 비트셋도 유리하지 않은 상황이라면 GCC는 확률 가중치를 적용한 이진 의사결정 트리를 구축하여 최종적으로 코드를 생성합니다.
커뮤니티 반응에서는 이러한 최적화 로직에 대한 흥미로운 논의가 이어졌습니다. 특히 대규모 희소 switch 문에 대해 GCC와 LLVM 모두 완벽한 해싱을 구현하지 않는다는 점이 지적되었습니다. 한 개발자는 유니코드 작업 등에서 완벽한 해싱을 직접 구현하면 컴파일 시간을 크게 단축할 수 있다고 언급했으나, 공식 컴파일러에는 아직 해당 기능이 포함되어 있지 않습니다.
또 다른 사례로는 .NET의 System.HashCode 개발 당시, 특정 상황에서 의사결정 트리가 점프 테이블보다 훨씬 빠른 성능을 보였다는 경험담이 공유되기도 했습니다. 이는 컴파일러의 일반적인 휴리스틱이 모든 하드웨어 환경이나 데이터 패턴에서 최적이 아닐 수 있음을 시사합니다.
현재로서는 GCC의 tree-switch-conversion.cc 소스 코드에서 동적 프로그래밍을 활용해 최적의 클러스터 분할을 결정하는 과정까지 추적할 수 있습니다. 다만, sparse_8 예제처럼 값을 나누어 점프 테이블을 단순화하는 변형은 GCC가 자동으로 찾아내지 못하는 것으로 나타났습니다.