Compile-time Dispatch 최적화로 Pattern Match 속도 10배 개선

How We Made a 128-Arm Pattern Match Run 10 Faster

sentomk2026년 5월 8일5분advanced

AI 요약

Context

C++17 환경에서 Variant 및 Enum 처리를 위한 Pattern Matching 라이브러리 구현 중, 케이스 수가 증가함에 따라 반복적인 객체 생성으로 인한 성능 저하 발생. 특히 128개 브랜치 기준 Naive 접근 방식이 hand-written switch 대비 10배 느린 10.79ns의 Latency를 기록하는 병목 지점 확인.

Technical Solution

dispatch_plan_selector를 통한 Compile-time 최적의 Dispatch 전략 자동 선택 구조 설계
O(1) Array Lookup 기반의 static_literal_dense 및 literal_runtime_dense 전략 도입
Variant 타입별 인덱스 테이블을 사전 계산하는 variant_simple 및 Binary Search 기반의 variant_alt_bucketed 계층 구성
Value Span이 케이스 수의 4배 이하일 때만 Dense Table을 사용하는 Density Heuristics 적용으로 메모리 효율성 확보
std::is_empty 대신 sizeof <= 1 휴리스틱을 도입하여 컴파일러별 [[no_unique_address]] 동작 불일치 문제 해결 및 Cache 경로 보장
최종적으로 Linear Fallback인 sequential 전략까지 포함한 6단계 Dispatch Hierarchy 구축

실천 포인트

- 다량의 분기 처리가 필요한 시스템 설계 시, 단순 Linear Search가 아닌 데이터 밀도에 따른 Table-driven Dispatch 검토 - 컴파일러 특성(`[[no_unique_address]]` 등)에 의존하는 최적화 시, Assembly 레벨 검증 및 보수적인 휴리스틱(`sizeof`) 적용 고려 - 라이브러리 설계 시 사용자가 최적화 설정을 수동으로 제어하지 않도록 Compile-time Analyzer를 통한 자동 전략 선택 구현

태그

#C++17 #Template Metaprogramming #Pattern Matching #Dispatch Table #Compile-time Optimization

원문 읽기