컴파일 때 충돌을 없앤 C++ 조회표, M4에서 초당 10억 회 넘게 찾는다

본문

C++에서 HTTP 메서드나 헤더 이름처럼 키가 미리 정해진 문자열을 조회할 때는 보통 std::unordered_map을 씁니다. Daniel Lemire와 Francisco Geiman Thiesen이 소개한 C++23 라이브러리는 이런 고정 키 집합을 컴파일 시점에 완전 해싱(perfect hashing)으로 변환합니다. 실행 중에는 해시 충돌을 처리하지 않고, 계산한 슬롯에 든 문자열 하나를 비교합니다.

실행 중 해시 테이블을 만들지 않는 방식

완전 해시는 주어진 키 집합에서 각 키가 서로 다른 슬롯을 가리키도록 해시 함수를 미리 구성합니다. 이 라이브러리에서는 키 길이와 특정 위치의 문자에 연결한 값을 더해 슬롯을 계산합니다. 테이블 크기를 2의 거듭제곱으로 두면 나머지 계산은 비트 마스크 연산으로 바뀝니다. 연관 값은 컴파일 시점에 탐색하므로 프로그램 실행 중 초기화 비용이 들지 않습니다.

문자열 비교도 짧게 처리합니다. 라이브러리는 키를 16바이트 벡터로 읽고, 키 길이 뒤쪽을 0으로 만든 뒤 저장된 키와 한 번에 비교한다고 설명합니다. 짧은 키의 끝을 넘어 읽는 SIMD 경로와 페이지 경계 가까이에서 쓰는 느린 경로를 함께 둡니다.

수치는 특정 프로세서와 키 집합의 벤치마크입니다

글의 Apple M3 Max·AppleClang 15 벤치마크에서 표준 HTTP 헤더 이름 20개를 무작위 순서로 조회했을 때 라이브러리는 조회당 약 1.3나노초를 기록했습니다. 같은 비교에서 gperf는 7.7나노초, Abseil flat_hash_map은 10.9나노초, std::unordered_map은 16.6나노초였습니다. 글은 URL 프로토콜부터 S&P 100 종목 코드까지 여러 키 집합에서 조회당 1.2~2나노초를 보고했습니다.

저장소가 제시한 Apple M4 결과는 URL 프로토콜 키 6개를 대상으로 초당 10억 회를 넘긴 수치입니다. 키 집합과 프로세서가 달라지면 결과도 달라질 수 있으며, 이 벤치마크만으로 HTTP 요청 처리나 파서 같은 전체 프로그램의 속도 향상을 알 수는 없습니다. 문자열 조회가 전체 실행 시간에서 차지하는 비중도 자료에 제시되지 않았습니다.

페이지 경계와 C++ 객체 경계는 다른 조건입니다

글은 16바이트 로드가 메모리 페이지를 넘지 않도록 검사하면 버퍼 끝을 지나 읽어도 괜찮다고 설명합니다. 이 검사는 페이지 폴트를 피하는 하드웨어 조건을 다룹니다. C++에서 객체가 차지하는 범위를 넘어 읽는 문제까지 없애지는 않습니다. C++ 표준 초안은 포인터 산술을 배열 안쪽과 끝 바로 다음 위치로 제한합니다.

라이브러리 저장소도 SIMD 경로가 짧은 키의 끝을 몇 바이트 넘어 읽는다고 밝힙니다. 메모리 안전 컴파일러 Fil-C에서는 이 경로 대신 스칼라 경로를 자동으로 선택한다고 설명합니다. 따라서 성능 결과와 별개로 이 최적화가 각 컴파일러와 실행 환경에서 어떤 메모리 접근으로 구현되는지가 적용 조건입니다.

자료: Daniel Lemire 블로그 / 정리·해설: Trawling

참고 자료

• GitHub - ConstexprCore/perfect_hash: A compile-time perfect hash implementation · GitHub — https://github.com/ConstexprCore/perfect_hash
• [expr.add] — https://eel.is/c++draft/expr.add