100만 건 데이터 조회 속도, 어떻게 1.7배 더 빠르게 만들었을까? (C++ 해시 테이블 최적화기)

안녕하세요. 풀링포레스트 테크리드 김영태입니다.

개발자 생활을 오래 하다 보면, 어느 순간 "더 이상 최적화할 곳이 없다"고 느껴지는 벽을 만납니다. 특히 해시 테이블(Hash Table) 같은 기본 자료구조는 이미 수십 년간 천재들이 깎고 다듬어 놓은 영역이라, 여기서 드라마틱한 성능 향상을 기대하기는 어렵다고 생각했죠. 저 역시 그랬습니다. std::unordered_map이 느리다는 건 누구나 알지만, 이미 SOTA(State-of-the-Art)라고 불리는 robin_hood나 ankerl::unordered_dense 같은 라이브러리를 쓰고 있다면 더더욱 그렇습니다.

그런데 최근 한 오픈소스 구현체를 뜯어보며 뒤통수를 한 대 맞은 듯한 기분이 들었습니다. 기존 최강자보다 조회 속도를 무려 1.7배나 끌어올린 사례를 발견했거든요. 오늘은 그 기술적 비밀인 'Grouped SIMD' 방식에 대해 이야기해 보려 합니다.

왜 기존 해시 테이블은 한계에 부딪혔을까?

우리가 흔히 쓰는 고성능 해시 테이블들은 대부분 오픈 어드레싱(Open Addressing) 방식을 씁니다. 충돌이 나면 다른 빈칸을 찾아가는 방식이죠. 여기서 많이 쓰는 기법이 Quadratic Probing(2차 탐사)입니다. 충돌 시 h, h+1, h+4, h+9... 이런 식으로 보폭을 넓히며 빈자리를 찾습니다.

문제는 여기서 발생합니다. CPU 캐시 입장에서는 이런 식의 메모리 접근이 정말 싫습니다. 데이터가 듬성듬성 흩어져 있으니 캐시 미스(Cache Miss)가 필연적으로 발생하죠.

"그럼 SIMD(Single Instruction Multiple Data)를 써서 한 번에 여러 곳을 찌르면 되지 않을까?"

많은 개발자가 이 생각을 했습니다. 저도 과거에 비슷한 시도를 해봤습니다. 그런데 결과는 처참했습니다. 흩어진 메모리 위치 16군데를 한 번에 긁어오는 gather 명령은 생각보다 오버헤드가 엄청났습니다. 스칼라 코드보다 오히려 5배나 느려지는 참사가 벌어지기도 했죠. 기술적으로는 멋져 보였지만, 실무에서는 쓸 수 없는 '예쁜 쓰레기'였던 겁니다.

발상의 전환: 흩어진 것을 줍지 말고, 뭉쳐있는 것을 훑어라

이번에 분석한 Grouped SIMD Hash Table의 핵심은 탐사(Probing) 방식의 혁신에 있습니다. 빈자리를 찾아 멀리 점프하는 대신, "그냥 인접한 16개를 통째로 읽어서 검사하자"는 전략입니다.

이 방식은 구글의 Swiss Tables와도 맥을 같이 하는데, 구현 방식이 아주 직관적입니다.

1. 메타데이터 분리: 각 슬롯에 1바이트짜리 메타데이터를 둡니다. (1비트는 사용 여부, 7비트는 해시값의 일부)

2. 통째로 로딩: SSE2 명령어를 사용해 연속된 16개의 메타데이터를 레지스터 하나(__m128i)에 때려 넣습니다.

3. 한 방에 비교: CPU 사이클 한 번에 16개의 슬롯을 동시에 비교합니다.

코드로 보면 이런 느낌입니다. (실제 구현체의 핵심 로직을 단순화했습니다.)

// 16개의 메타데이터를 한 번에 로드 (연속된 메모리라 매우 빠름)
__m128i metadata = _mm_loadu_si128((__m128i*)&metadata_[base]);

// 내가 찾는 해시값(target)과 16개를 동시에 비교
__m128i matches = _mm_cmpeq_epi8(metadata, target);

// 결과 마스크 생성 (어디 어디가 일치하는지 비트마스크로 반환)
uint32_t mask = _mm_movemask_epi8(matches);

이 코드를 보고 무릎을 탁 쳤습니다. "아, 왜 굳이 멀리 있는 빈칸을 찾아다녔을까? 옆에 있는 놈들을 묶음(Group)으로 처리하면 되는데."

이 방식은 CPU 캐시 친화적(Cache-friendly)입니다. 메모리를 연속으로 읽으니 프리페처(Prefetcher)가 신나서 데이터를 미리 가져다줍니다.

실제 성능: 조회 성능의 압도적 승리

이 구현체의 벤치마크 결과는 상당히 흥미롭습니다. 데이터가 100만 건(1M) 이상일 때 진가를 발휘합니다.

• 조회(Lookup) 속도: 기존 최강자(ankerl) 대비 약 1.7배 빠름 (61.5ms vs 104ms)

• 삽입(Insert) 속도: ankerl 대비 0.7배 수준으로 느림 (70.1ms vs 50.8ms)

확실한 트레이드오프가 보입니다. 데이터를 묶어서 관리하는 구조 탓에 삽입할 때는 오버헤드가 발생하지만, 일단 데이터가 구축된 후 '조회'만 주구장창 하는 워크로드에서는 타의 추종을 불허합니다.

어디에 써먹어야 할까?

풀링포레스트 팀에서도 대용량 트래픽을 처리하다 보면, "한 번 로드해두고 읽기만 엄청나게 하는" 데이터셋이 꽤 많습니다. 예를 들어 추천 시스템의 피처(Feature) 저장소나, 정적인 설정값 캐시 등이 그렇죠.

이런 상황이라면 무조건 std::unordered_map을 쓸 게 아니라, 데이터의 성격을 파악해야 합니다.

1. 데이터 크기가 50만 건 이상인가?

2. 쓰기보다 읽기(Lookup) 비율이 압도적으로 높은가?

이 두 가지 조건에 부합한다면, Grouped SIMD 방식의 해시 테이블 도입을 진지하게 고려해볼 만합니다.

마치며

개발자인 우리는 종종 "이미 해결된 문제"라고 치부하며 깊이 들여다보기를 멈추곤 합니다. 하지만 하드웨어의 발전(SIMD 명령어 세트의 대중화)과 함께, 고전적인 알고리즘의 정답도 계속 바뀌고 있습니다.

오늘 소개한 사례처럼, "흩어진 것을 줍는 것보다 뭉쳐있는 것을 훑는 게 빠르다"는 하드웨어적 특성을 이해하고 코드에 적용하는 태도야말로, 엔지니어로서 한 단계 성장하는 계기가 된다고 믿습니다.

여러분의 프로젝트에는 무심코 쓰고 있는 비효율적인 자료구조가 없나요? 오늘 한 번 프로파일러를 돌려보시는 건 어떨까요? 생각지 못한 병목을 발견하고 쾌재를 부를지도 모릅니다.