std::unordered_map이 느려서 답답했다면 — '홉스카치 해싱'으로 빨라지는 원리

어떤 라이브러리냐면요

C++로 개발하다 보면 해시맵(hash map)을 정말 자주 써요. 키(key)를 주면 값(value)을 빠르게 찾아주는 자료구조인데요. 표준 라이브러리에 std::unordered_map이라고 기본으로 들어 있긴 해요. 그런데 이게 성능에 민감한 코드에서는 생각보다 느리다는 게 C++ 진영의 오랜 불만이었거든요. 오늘 소개할 hopscotch-map(Tessil이 만든 헤더 전용 라이브러리예요)은 바로 그 표준 해시맵을 거의 그대로 바꿔 끼울 수 있으면서 더 빠른 대안이에요. 'hopscotch hashing'이라는 기법을 써서요.

std::unordered_map은 왜 느리냐면요

표준 해시맵은 '체이닝(chaining)'이라는 방식을 써요. 이게 뭐냐면, 같은 칸(버킷)에 여러 값이 몰리면 그걸 연결 리스트(linked list)로 줄줄이 매달아 두는 거예요. 문제는 이 연결 리스트의 각 노드가 메모리 여기저기 흩어져 있다는 거예요. 값을 하나 찾으려고 포인터를 따라가다 보면, CPU가 매번 멀리 떨어진 메모리를 새로 읽어와야 해요. 이걸 '캐시 미스(cache miss)'라고 하는데요, 현대 CPU에서는 이 메모리 왔다 갔다 하는 비용이 계산 비용보다 훨씬 비싸요. 그래서 포인터를 자주 따라가는 자료구조는 느릴 수밖에 없어요.

홉스카치 해싱은 뭐가 다르냐면요

hopscotch 해싱은 '개방 주소법(open addressing)' 계열이에요. 연결 리스트로 따로 빼지 않고, 값을 배열 안에 직접 차곡차곡 담아요. 그래서 메모리가 한 덩어리로 붙어 있어서 캐시에 친화적이에요. 핵심 아이디어가 재밌는데요. 각 값은 원래 들어가야 할 '집(home) 버킷'이 정해져 있는데, 홉스카치는 '어떤 값이든 자기 집에서 정해진 이웃 범위(예: 32칸) 안에는 반드시 있다'는 규칙을 지켜요. 이름이 왜 홉스카치(사방치기, 칸 뛰기 놀이)냐면, 빈자리가 멀리 있을 때 그 자리를 이웃 칸들로 '폴짝폴짝' 옮겨 와서 항상 집 근처에 머물게 만들기 때문이에요. 덕분에 값을 찾을 땐 딱 그 이웃 범위 몇 칸만 쭉 훑으면 돼요. 메모리가 붙어 있는 짧은 구간만 읽으니까 엄청 빠르고요.

다른 빠른 해시맵들과 비교하면요

사실 '빠른 해시맵'은 요즘 선택지가 꽤 많아요. 구글이 만든 absl::flat_hash_map, 로빈후드 해싱을 쓰는 ska::flat_hash_map이나 robin-map(이것도 Tessil 작품이에요) 같은 것들이 대표적이에요. 이들 대부분이 공통적으로 추구하는 건 똑같아요. '포인터 추적을 줄이고 데이터를 한 배열에 붙여서 캐시를 잘 쓰자'예요. hopscotch는 그중에서도 이웃 범위 보장이라는 독특한 방식으로 이걸 달성하는 거고요. 만든이 Tessil은 hopscotch-map 말고도 robin-map, sparse-map, ordered-map 같은 시리즈를 같이 내놨는데, 상황에 맞게 골라 쓰라는 의도예요. 메모리를 아끼고 싶으면 sparse 계열, 삽입 순서를 유지하고 싶으면 ordered 계열 식으로요.

쓸 때 주의할 점도 있어요

공짜 점심은 없어요. 개방 주소법 계열은 배열이 너무 꽉 차면(높은 적재율) 성능이 급격히 나빠져서, 적당한 시점에 배열을 키워줘야 해요. 또 표준 unordered_map은 원소의 메모리 주소가 변하지 않는다고 보장하는데, 이런 배열 기반 맵들은 크기가 커질 때 내부적으로 값을 옮기기 때문에 그 보장이 약해요. 그래서 '맵에 넣은 원소의 포인터를 오래 들고 있다가 쓰는' 코드라면 그대로 갈아 끼우면 안 되고 동작을 꼭 확인해야 해요. 삭제가 많은 경우의 처리 방식도 라이브러리마다 달라서, 우리 워크로드로 직접 벤치마크해 보는 게 제일 정확해요.

마무리

정리하면, hopscotch-map은 '값을 집 근처 이웃 칸에 모아두기'라는 영리한 규칙으로 캐시를 잘 활용해서 표준 해시맵보다 빠른 성능을 내는 라이브러리예요. 헤더만 추가하면 거의 그대로 바꿔 낄 수 있다는 것도 큰 장점이고요. 여러분은 std::unordered_map이 느려서 다른 해시맵으로 갈아탄 경험이 있나요? 어떤 걸 써봤고 결과가 어땠는지 궁금해요.