"초당 10억 건 조회" C++ 해시 테이블 성능 13배 끌어올린 괴물 최적화 ㄷㄷ

요약 웹 서버의 HTTP 메서드 판별이나 컴파일러의 키워드 파싱처럼 소프트웨어에서는 문자열을 특정 값에 매핑하는 작업이 빈번하게 일어납니다. C++ 개발자들은 흔히 std::unordered_map을 사용하지만, 키 집합이 미리 고정되어 변경되지 않는 경우에도 런타임마다 문자열 전체 해싱, 버킷 탐색, 포인터 추적 및 비교를 수행해 불필요한 오버헤드가 발생합니다. 컴퓨터 과학자 다니엘 르마이어(Daniel Lemire)는 C++23의 constexpr 기능을 활용해 컴파일 타임에 충돌 없는 퍼펙트 해시 함수(Perfect Hash Function)를 구축하는 라이브러리를 소개했습니다. 이는 1989년 등장한 GNU gperf와 유사한 원리로, 키 길이와 특정 위치 문자의 가중치를 조합해 고유한 슬롯을 산출하며 외부 도구 없이 순수 C++ 코드로 동작합니다. 특히 문자열 비교 병목을 해소하기 위해 SIMD 벡터 레지스터를 활용했습니다. 3바이트짜리 짧은 키라도 ARM NEON이나 x64의 16바이트 레지스터로 한 번에 로드한 뒤 셔플 명령어로 불필요한 바이트를 0으로 마스킹하고 한 번에 비교합니다. 이를 통해 기존 40여 개 명령어와 8개 분기문이 필요하던 비교 과정을 단 5개의 분기와 없는 명령어로 대폭 줄였습니다. 메모리 페이지 경계(4KB) 근처에서만 안전 검사를 수행해 예측 실패 위험도 최소화했습니다. Apple M3 Max 환경에서 벤치마크를 진행한 결과, 표준 HTTP 헤더 조회 시 1회당 약 1.3ns(약 5사이클)만에 조회를 마쳤습니다. 이는 전통적인 gperf(7.7ns) 대비 약 6배, Abseil flat_hash_map(10.9ns) 대비 약 8배, std::unordered_map(16.6ns) 대비 무려 13배 이상 빠른 속도입니다. S&P 100 티커나 자바스크립트 예약어 등 다양한 키 세트에서도 1.2~2ns 수준을 유지하며 초당 수억에서 10억 회 수준의 조회가 가능한 성능을 입증했습니다.