해시 테이블, 이거 은근히 골치 아픕니다.
평균 O(1) 탐색이라는 std::unordered_set의 약속을 보면, 우리 손가락이 저절로 가는 거, 인정하시죠? 특히 C++로 뭔가 쫙쫙 빠릿하게 만들고 싶을 때, 이게 기본값이고 똑똑한 선택처럼 느껴지잖아요. 그런데 대부분 사람들이 놓치는 게 있어요. 성능이 극도로 중요한 코드, 특히 나노초 싸움이 벌어지는 ‘핫 루프(hot loop)’ 안에서라면, 그 자동적인 습관이 엄청난 대가를 치르게 할 겁니다. 그냥 조금이 아니에요. 성능이 한두 단계, 아니 몇 단계는 훅 떨어집니다.
이건 그냥 이론적인 이야기가 아닙니다. 제가 근사 최근접 탐색을 위한 Vamana 그래프 인덱스를 다루면서 이걸 직접 겪었어요. 작업 중에 방문한 노드를 추적해야 했는데, 노드 ID가 빽빽한 정수들이었습니다. 그리고 어떤 노드를 방문했는지 확인하는 작업이요? 그게 전체 탐색 경로 중 가장 ‘핫한 루프’ 안에서 일어났던 거죠. 이보다 더 중요한 지점은 없죠.
제 첫 번째 선택은 당연히 std::unordered_set였습니다. 물론 맞았죠. 제 할 일을 했습니다. 하지만 느렸습니다. 규모가 커지니 정말 고통스러울 정도로 느렸어요.
얼마나 심각한지 파악하려고 테스트를 좀 해봤습니다. 1000개의 무작위 uint32_t ID 벡터를 가지고 세 가지 다른 중복 제거 방법을 돌렸죠. 앞서 말한 std::unordered_set, 고전적인 sort + unique 조합, 그리고 boost::dynamic_bitset<>입니다. ID는 [0, 2n) 범위에서 샘플링된 빽빽한 정수들이었습니다. 결과요? 처참했습니다.
| n | unordered_set (ms) | sort+unique (ms) | boost bitset (ms) |
|---|---|---|---|
| 128 | 5 | 3 | 1 |
| 32,768 | 1,649 | 1,455 | 177 |
| 500,000 | 50,302 | 26,759 | 3,423 |
마지막 행을 보세요. 50만 개 데이터에서 비트셋이 거의 15배 빨랐습니다. 왜냐고요? 해시 테이블은 복잡한 북키핑 작업에 여념이 없었기 때문입니다. 키 해싱, 버킷 확장, 너무 붐빌 때 전체를 다시 해싱, 그리고 메모리 여기저기 포인터 추적까지. 비트셋은요? 단일 인덱스 메모리 연산입니다. 단순하고 직접적이며, 데이터가 맞으면 훨씬 효율적이죠.
심지어 sort + unique 조합조차도 규모가 커지니 해시 테이블을 앞질렀습니다. 왜냐고요? 그냥 연속된 메모리를 훑고 지나갈 뿐이니까요. CPU요? CPU는 연속된 메모리를 엄청 좋아합니다.
자, 해시 테이블을 완전히 버리기에 앞서, 주의할 점이 있습니다. ID가 희소(sparse)하면 이야기가 달라져요. 적어도 비트셋에게는요. 1억 개라는 엄청난 전체 값에서 겨우 n개의 ID만 샘플링했더니, 비트셋은 각 벡터마다 거대한, 대부분 비어있는 배열을 비워야 했습니다. 이건 무시할 수 없는 오버헤드죠.
| n | unordered_set (ms) | boost bitset (ms) |
|---|---|---|
| 128 | 6.3 | 149.7 |
| 2,048 | 91.9 | 145.5 |
| 65,536 | 4,169.3 | 985.4 |
보이시나요? 작고 희소한 입력의 경우, std::unordered_set이 오히려 더 좋습니다. 비트셋은 입력이 충분히 커서 초기 클리어 비용을 상쇄할 수 있을 때부터 빛을 발하기 시작합니다. 늘 그렇듯, 이건 트레이드오프죠.
그렇다면 언제 std::unordered_set를 써야 할까요? ID가 희소하거나, 범위가 없거나, 아니면 그냥 직접 인덱싱하기 어려운 정수일 때입니다. 하지만 핫 루프 안에서 빽빽한 정수들이 춤을 추고 있다면요? 멤버십 확인 방법을 다시 생각해야 합니다. 대신 인덱싱된 로드나 스토어로 바꾸세요. 더 저렴하고, 더 빠르고, CPU를 존중하는 방법입니다.
CPU는, 그 실리콘 심장을 가진 CPU는, 여러분의 Big-O 표기법 따위 신경 쓰지 않습니다. 캐시 라인과 메모리 접근 패턴을 신경 씁니다. 이걸 잘못 건드리면 그대로 끝장입니다.
CPU는 여러분의 Big-O 표기법 따위 신경 쓰지 않습니다. 메모리 접근 패턴을 신경 씁니다.
이런 std::unordered_set를 빡빡한 루프에서 피해야 한다는 문제는 새삼스러운 게 아닙니다. 옛날에도 비슷한 분석을 하던 사람들이 있었어요. 이건 고전적인 성능 함정입니다. 범용적이고, 겉보기에 효율적인 구조의 유혹이 현대 프로세서의 초고속, 저수준 현실을 가려버립니다. 누가 돈을 버냐고요? 우리 코드의 비효율성을 무력으로 돌파할 더 빠른 CPU를 팔아먹는 반도체 제조사들이죠. 그리고 어쩌면, 정말 어쩌면, 루프를 최적화하는 사람들이 경쟁 우위를 얻을지도 모릅니다.
이게 개발자에게 왜 중요할까요?
많은 분야, 특히 시스템 프로그래밍, 게임 개발, 과학 컴퓨팅, 임베디드 시스템에서 효율성이 여전히 왕이기 때문입니다. 이런 저수준 성능 특성을 무시하는 것은 상당한 속도를 그대로 버리는 셈입니다. 단순히 밀리초를 줄이는 게 아니에요. 더 큰 데이터셋, 더 복잡한 시뮬레이션, 더 반응성 좋은 애플리케이션을 가능하게 하는 것입니다. 불필요하게 하드웨어를 낭비하지 않는 코드를 작성하는 것입니다. 그리고 오픈소스 세계에서는, 자원이 제약된 경우가 많고 모든 사이클이 중요하기 때문에, 이런 미묘한 차이를 이해하는 것이 프로젝트가 번영하느냐 아니면 자체 성능 부채에 시달리느냐를 가르는 차이가 될 수 있습니다.
std::unordered_set, 언제 제대로 된 선택일까요?
물론입니다. 해시 충돌이 드물고, 데이터 접근 패턴이 정말 무작위이거나, 희소한 데이터를 위한 비트셋 클리어 오버헤드가 해시 테이블 연산보다 클 때, std::unordered_set는 여전히 완벽하게 합리적이거나 심지어 최고의 선택일 수 있습니다. 핵심은 맥락입니다. 대부분의 일상적인 프로그래밍 작업에서는 그 편리함과 평균적인 성능만으로도 충분합니다. 하지만 성능의 벽에 부딪히거나, 프로파일링이 무언가 병목 현상이라고 알려줄 때, 추상적인 O(1) 약속보다 더 깊이 파고들어야 합니다. 그때 도구가 아니라 습관 자체에 의문을 제기해야 합니다.
