해시드 정렬은 보통 해시 테이블보다 빠르다

문제 설명: 대부분이 고유한 uint64로 이루어진 큰 배열에서 고유값의 개수를 세어라. 표준적인 두 가지 접근은 다음과 같다.

• 해시 테이블에 삽입하고 엔트리 수를 반환한다.
• 배열을 정렬한 뒤, 바로 이전 값과 다른 위치의 개수를 센다.

점근적으로는 해시 테이블이 면접에서 승리한다(O(n) 대 O(n log n)). 하지만 잘 튜닝된 구현에서는 정렬이 보통 더 빠르다. 이 문제와 그 변형들은 세계에서 가장 큰 CPU 워크로드 일부의 내부 루프다.

벤치마크 하이라이트

다음은 M2 Pro2에서, 최적으로 튜닝한 해시 테이블과 정렬 구현을 비교한 성능이다. 또한 레퍼런스로 품질 높은 범용 구현인 Rust의 기본 구현(sort_unstable(), foldhash::fast를 사용하는 HashSet)도 포함했다:

튜닝한 정렬은 작은 크기를 제외하면 최적의 해시 테이블보다 약 1.5배 빠르며, Rust 표준 라이브러리의 뛰어난 “Swiss Table” 해시 테이블보다 최대 4배까지 빠르다.

벤치마크 코드는 여기.

왜 정렬이 이길까?

메모리 대역폭: 정렬은 메모리를 여러 번 통과하더라도, 각 패스가 해시 테이블의 단일 패스보다 대역폭을 훨씬 더 효율적으로 사용하기 때문이다.

데이터셋이 CPU 캐시를 초과하면(단일 코어 기준 보통 ~1 MiB 근방, CPU에 따라 다름), 해싱과 정렬 모두 메인 메모리로부터의 캐시 라인 페치 대역폭에 의해 제한된다. 캐시 라인은 보통 64바이트이며, 단 1바이트만 접근하더라도 CPU는 전체 라인을 가져온다.

해시 테이블은 대역폭을 낭비한다: 각 8바이트 키 접근은 64바이트 캐시 라인을 통째로 끌어온다. 따라서 해시 테이블은 처리하는 각 uint64마다 최소 128바이트의 트래픽을 발생시킨다: 64바이트 읽기 + 64바이트 쓰기.

정렬에서는 패스마다 1024개의 버킷으로 나누는 기수 정렬(radix sort)을 사용하며, 2^30 개의 원소에 대해 단 3회 패스면 충분하다3. 각 패스는 배열 전체를 한 번 읽고 한 번 쓰며, 접근의 공간 지역성이 충분해 해시 테이블과 달리 _캐시 라인 전체_가 생산적으로 사용된다. 따라서 하나의 uint64를 처리하는 데 드는 총 메모리 트래픽은 48바이트에 그친다: 읽기 8바이트 × 3패스, 쓰기 8바이트 × 3패스.

이 분석은 해시 테이블 대비 2.7배(128바이트 대 48바이트)의 속도 향상을 시사한다. 실측 속도 향상은 약 1.5배에 그치는데, 주된 이유(추정)는 기수 정렬에서 CPU 캐시 시스템을 원하는 대로 정확히 동작하게 만드는 일이 해시 테이블보다 어렵기 때문이다4. 해시 테이블은 이상적인 성능에 더 근접하며, 기수 정렬은 이상적 성능 자체가 더 좋아서 결국 승리한다.

기수 정렬을 견고하게 만들기

기수 정렬은 무작위 데이터에서는 종종 가장 빠른 정렬 알고리즘이지만, 키 공간에 균일하게 퍼져 있지 않은 데이터에서는 성능이 저하된다. 한 패스는 키의 한 바이트를 기준으로 256개 버킷으로 나누는데, 실데이터에서 이 256개 중 일부 소수의 버킷만 사용된다면(예: uint64의 상위 바이트가 항상 0) 그 패스의 작업 중 많은 부분이 낭비될 수 있다.

이를 보이기 위해, (a) 무작위 uint64와 (b) 무작위 비트를 “퍼뜨린(spread-out)” uint64로 정렬을 벤치마크했다. 퍼뜨린 숫자는 짝수 비트만 무작위이고 홀수 비트는 0인 형태, 예를 들어 0a0b0c0d…와 같다. 퍼뜨린 숫자의 경우, 각 기수 패스는 256개 중 16개 버킷만 사용하므로 효율이 나빠진다. 무작위 수에서는 기수 정렬이 퀵소트보다 약 2배 빠르지만, 퍼뜨린 수에서는 약 1.5배 느리다:

이러한 느려짐을 피하기 위해 해시 테이블의 아이디어를 차용한다: key가 아니라 hash(key)로 정렬하자. 고유값 개수 세기에서는 최종 순서가 아니라 그룹화만 중요하다. 물론 이는 정렬 순서를 바꾸지만, 우리가 관심 있는 것은 순서 자체가 아니라 고유값의 개수이므로 상관없다.

더 나아가, 역변환 가능한(전단사) 해시를 사용해 키를 제자리에서 변환하자. 그러면 키와 해시를 모두 저장하거나 매 패스마다 해시를 재계산할 필요가 없다. 널리 쓰이는 여러 해시 함수가 uint64에 대해 가역적이며, 여기서는 Murmur3와 더 가벼운 변형인 MulSwapMul을 사용했다.

적당히 빠른 해셔를 쓰면 해싱 비용은 작고 분포 문제를 바로잡을 수 있다. MulSwapMul을 사용하면, 데이터 분포와 거의 무관하게 성능이 다음과 같이 나온다:

이것이 본문 상단의 “최고 알고리즘”이다: MulSwapMul로 해싱한 다음 diverting LSD기수 정렬을 사용한다. 나는 해싱을 기수 정렬의 첫 패스와 융합하고, 카운팅을 마지막 패스와 융합해 소폭의 추가 속도 향상을 얻었다.

해시 테이블과 해시드 기수 정렬 중 무엇을 선택해야 할까?

일부 해시 테이블 사용처는 해시드 기수 정렬로 재구성할 수 없다. 후자는 더 제약이 있다. 해시 테이블의 조회/삽입을 해시드 기수 정렬로 바꾸려면 근본적으로 _배치 처리_가 필요하다: 결과가 한참 뒤에 필요해도 될 만큼 많은 조회를 한꺼번에 발행해야 한다. 때로는 일회 통과 알고리즘(자료구조를 순회하며 즉시 조회)을 두 번 통과로 바꿀 수 있다: 먼저 자료구조에서 키를 모은다; 기수 정렬을 수행한다; 그 다음 다시 자료구조를 순회하며 결과를 써 넣는다. 하지만 해시 컨싱, 공통 부분식 제거, 파서 조회 테이블 같은 시나리오에서는 배치 요구가 결정적 장애물이라 정렬이 성립하지 않는다.

배치가 _가능_하다면, 해시드 기수 정렬은 대개 적용 가능하다:

• 해시 테이블에서 쓸 수 있는 모든 키 타입은 해시드 기수 정렬에서도 사용할 수 있다: 같은 해시를 적용하면 된다.
• 해시 테이블을 _구축_한다면, 그 아날로그는 기수 정렬로 정렬된 배열을 만드는 것이다. 기존 테이블을 _조회_한다면, 그 아날로그는: 조회들을 정렬한 뒤, 기존의 정렬된 키 배열과 선형 시간에 머지하는 것이다.
• 기수 정렬은 적어도 해시 테이블만큼 잘 병렬화되며, 종종 더 낫다.

해시드 기수 정렬이 문제에 적용 가능하다면, 더 빠를까? 주요 결정 요인은 _고유 키당 반복 접근 횟수_로 보인다. 고유 키 수보다 훨씬 많은 삽입/조회가 이뤄지면 해시 테이블이 유리하고, 접근 횟수가 고유 키 수와 같은 규모(대부분의 키는 몇 번만 접근)라면 기수 정렬이 유리하다. 이는 해시 테이블은 O(고유 키 수) 메모리를 쓰는 반면 기수 정렬은 O(접근 횟수) 메모리를 쓰기 때문이다. 더 작은 풋프린트에 맞추면 메모리 시스템 성능이 자주 더 좋아진다.

내 벤치마크에서는, 키가 평균 ~30번 접근되기 시작하면 해시 테이블이 앞서기 시작했다. 그 임계값은 문제 크기가 커질수록 올라간다:

왜 중요할까?

여러 고성능 시스템은 이와 동등한 내부 루프를 갖고 있다. 나는 개인적으로 두 가지에 참여했다.

첫째, 예를 들어 10억분의 1의 희소성, 비제로당 스칼라 하나 같은 극도로 희소한 비구조적 행렬 곱셈. 이는 2015년 구글의 최대 워크로드 중 하나였고, 전체 플릿 CPU의 몇 퍼센트를 소비했던 Google의 Sibyl에 적용된다. 나를 포함한 많은 사람이 수년간 이 내부 루프를 최적화했다.

둘째, 난수 생성기용 BigCrush 테스트 스위트는 이상을 찾기 위해 생성된 수의 n-그램에서 중복을 센다.

내 경험상 이런 문제의 기본값은 해시 테이블이다. 그러나 벤치마크를 돌려보니, 기수 정렬이 상당한 차이로 이길 수 있다는 사실이 놀라웠다.

---

부록 1: 기수 정렬 튜닝

빠른 기수 정렬에 관한 문헌과 라이브러리가 풍부하다. 나는 주로 diverting LSD sort, diverting fast radix, Rust 라이브러리 voracious_radix_sort를 참조하고 추천한다. 이러한 고성능 구현의 주요 특징은 다음과 같다.

• Diverting 기수 정렬을 사용한다. 이는 소수의 기수 패스만 수행한 뒤 삽입 정렬로 넘어간다. 한 패스의 버킷 수를 radix(예: 1024)라 하면, p번 패스 후 배열은 radix^p개의 버킷으로 분류되며 각 버킷은 아직 정렬이 필요하다. 충분한 패스를 거치면 버킷이 아주 작아지므로(평균 크기 < 1) 기수 패스를 멈추고 삽입 정렬로 지역적으로 마무리한다. 이렇게 하면 diverting 기수 정렬의 복잡도는 O(n log_{radix} n)이 되고, 비-diverting 기수 정렬의 O(n·w)(여기서 w는 워드 길이)보다 유리하다. uint64 같은 큰 키에서는 보통 절반 이상의 패스를 절약할 수 있다.
• 각 패스 직전에 하나씩 히스토그램을 만드는 대신, 기수 정렬의 p개 모든 패스에 대한 히스토그램을 한 번의 스윕에서 만든다. 이렇게 하면 대역폭을 절약한다: 메모리를 통과하는 스윕이 2p회에서 p+1회로 줄어든다.

위의 문헌 표준 기법 외에, 나는 두 가지 최적화를 더 했다.

첫째, 메모리 대역폭을 절약하려고(정렬 전의) 해싱 패스를 (정렬의 첫 단계인) 히스토그램 패스에 융합했다.

둘째, 표준 라이브러리 함수를 호출하는 대신 인라인된 삽입 정렬로 폴백한다. 표준 라이브러리 정렬은 이 배열이 매우 작다는 사실을 알아내기 위해 크기에 따라 많은 분기를 수행해야 하며, 이는 평균 크기가 1인 버킷에서는 큰 오버헤드다. 인라인 삽입 정렬은 작은 배열에서 매우 빨리 끝난다.

부록 2: 다른 메모리-대역폭-효율적 정렬들

우리가 기수 정렬을 선호하는 이유는, 메모리를 통과하는 횟수가 퀵소트/병합정렬의 log_2(n) 패스보다 적은 log_1024(n) 패스이기 때문이다. 패스를 줄이는 또 다른 방법은 _다중 병합 정렬(multi-way mergesort)_이다: 2개가 아니라 한 번에 k개 배열을 병합하며, 토너먼트 트리로 구현하는 것이 가장 좋다.

이를 구현해 벤치마크했다. 내 구현에서는 퀵소트와 기수 정렬보다 상당히 성능이 떨어졌다. 메모리 대역폭 사용은 더 낫지만, 명령어 사용량이 더 나쁜 듯하다. 다만 특히 여기서는 문헌이 상대적으로 드물어, 내 구현이 충분히 튜닝되지 않았을 가능성도 있다.

부록 3: 해시 테이블 튜닝

우리의 튜닝된 해시 테이블은 이 워크로드에서 기본 “Swiss Table” 해시 테이블보다 최대 3배 빠르다. 이는 우리가 특정 경우(거대한 테이블, uint64 키, 메모리 풋프린트보다 실행 시간 우선)에 맞게 최적화할 수 있는 반면, Swiss Table은 여러 사용처(문자열, 작은 테이블, 메모리 풋프린트)를 균형 있게 고려해야 하기 때문이다.

우리의 튜닝된 해시 테이블은 Swiss Table과 다음과 같이 다르다.

단일 테이블 vs. 메타데이터+데이터. Swiss Table은 실제 데이터 테이블 외에 “메타데이터”(7비트 해시 코드에서 파생된 1바이트 태그) 테이블을 유지한다. 먼저 메타데이터를 프로빙하고(SIMD 명령으로 한 번에 8–16개의 키), 일치 시 데이터 테이블을 프로빙한다. 이는 프로브 시퀀스가 길 때도 효율적인 프로빙을 가능케 하지만, 조회마다 _두 번_의 캐시 미스를 요구한다: 메타데이터 테이블 한 번, 데이터 테이블 한 번. 반면 우리는 데이터 테이블만 사용한다: uint64 키 프로빙은 이 자체로 충분히 빠르다. 이로써 조회당 캐시 미스를 한 번만 지불할 수 있다5.

Swiss Table의 프로빙은 캐시라인 경계에 정렬되어 있지 않다. 프로브 시퀀스가 캐시 라인 중간에서 시작해 다음 라인으로 넘어가면서 현재 라인을 끝내기 전에 이동할 수 있어 대역폭을 낭비한다. 우리의 튜닝된 테이블도 라인 중간에서 시작하지만, 캐시 라인의 끝을 치면 처음으로 래핑해 그 라인의 나머지를 모두 프로빙한 뒤 다음 라인으로 간다6.

Swiss Table은 우리 테이블보다 데이터를 더 촘촘히 채운다: 최대 부하율 78.5%를 목표로 하는 반면, 우리는 50%를 목표로 한다. 이는 시간 대 메모리의 순수한 트레이드오프다: Swiss Table은 메모리를 더 중시하고, 우리는 시간을 더 중시한다. 더 낮은 부하율을 사용하면 프로브 거리가 짧아지고, 한 번의 캐시 미스로 조회가 성공할 확률이 높아진다.

우리는 테이블 접근 시 프리패치 명령을 사용한다. Rust의 Swiss Table 구현은 이런 기능을 제공하지 않는다. 해시 테이블에서 프리패칭은 고급 사용자 기능인데, 루프를 프리패칭을 지원하도록 재구성(보통 루프 프로로그/바디/에필로그로 분리)해야 하기 때문이다. Rust의 HashSet이 제공하는 다른 어떤 API보다 훨씬 더 니치한 기능이어서, 표준 라이브러리에 포함되지 않은 것도 어쩌면 타당하다. 그럼에도 루프를 재구성하고 튜닝하는 수고를 감수한다면 프리패칭은 큰 속도 향상을 제공할 수 있다.

위의 차이들과 달리, 해시 함수 자체는 우리의 튜닝된 해시 테이블과 Swiss Table 간에 동일하다: 둘 다 MulSwapMul을 사용한다. 이는 foldhash::fast와 비슷한 속도이며, Rust 기본 SipHash보다 훨씬 빠르다.

이 모든 차이를 합치면 이 워크로드에서 Swiss Table 대비 약 3배의 속도 향상을 얻는다:

부록 4: 병렬화

많은 고성능 응용에서는 병렬화가 필요하다. 기수 정렬과 해시 테이블 모두 효율적으로 병렬화된다: 기수 정렬은 각 패스 내부를 병렬화하고 패스 경계에서 동기화하며, 해시 테이블은 테이블 내부의 캐시라인 단위로 세분화된 락 같은 미세한 락킹을 사용한다.

이론적으로는 기수 정렬과 해시 테이블 모두 매우 잘 병렬화되며, 병렬 환경에서도 기수 정렬의 이점이 유지된다고 예상한다. 나는 Rust의 상위권 병렬 기수 정렬과 병렬 해시 테이블 라이브러리 몇 개를 벤치마크했지만, 커스텀 튜닝 버전은 만들지 않았다.

기수 정렬의 경우, voracious_radix_sort가 뛰어난 병렬 성능을 보였다. 데이터가 8MiB를 넘어서면 최고 수준의 단일 스레드 구현을 이기기 시작했고, 단일 스레드에서 했던 일부 튜닝을 이식하면 더 개선될 여지도 있다고 본다.

해시 테이블의 경우, 내가 찾은 구현 중 내 단일 스레드 최고 구현보다 나은 것은 없었다. 이는 의외였다: 다른 맥락에서는 캐시라인당 락 설계로 거의 선형에 가까운 병렬 속도 향상을 보았고, 여기서도 가능하다고 생각한다. 나는 여기에 많은 시간을 쓰지 않았고, 기존 라이브러리를 잘못 사용했거나 워크로드 프로파일이 대상 범위를 벗어났을 가능성도 있다.

---

1. 균형 잡힌 조회와 삽입이 있는 배치 알고리즘을 가정한다.↩︎

2. AMD의 대형 Zen 4 머신(AMD EPYC 9B14)에서도 구동했으며, 유사한 결과를 얻었다:

3. 전통적인 기수 정렬은 3패스가 아니라 8패스를 사용한다. 8바이트 키의 각 바이트마다 한 번씩이다. 이는 낭비다: 2^32 개 원소만 처리한다면 4패스 후에는 배열이 거의 완전히 정렬되어(각 버킷의 평균 원소 수가 1) 있으므로, 이때 삽입 정렬 같은 더 단순하고 캐시 지역적인 알고리즘으로 넘어가는 것이 좋다. 이 접근의 최선의 형태가 Diverting LSD 기수 정렬로 보인다.↩︎

4. 한 패스에서, 기수 정렬은 1024개의 쓰기 포인터(버킷당 하나)를 유지한다. 우리는 이 중 하나의 포인터에 uint64를 쓰고, 그 포인터를 8바이트만큼 전진시킨다. 이상적인 캐시 성능을 내려면, 각 포인터의 현재 캐시 라인이 L1 캐시에 유지되어(“핫” 상태)야 한다. 그런 다음 쓰기 포인터가 다음 캐시 라인으로 넘어가면, 이전 라인을 메모리에 플러시하고 다음 라인을 핫 상태로 유지해야 한다. 이는 CPU가 1024개의 특정 캐시 라인을 핫하게 유지했다가, 포인터가 현재 라인을 넘어설 때 빠르게 제거하고 다른 라인으로 대체할 수 있음을 요구한다. 현재 CPU는 일반적으로 L1 캐시에 약 2048개의 캐시 라인을 수용할 수 있으므로, 원칙적으로 가능하다. 불행히도 CPU 캐시는 소프트웨어가 아니라 하드웨어가 관리하므로, 우리가 CPU에게 그대로 _지시_할 수 없다: 대신 캐시 제거 정책의 휴리스틱에 의존한다. 때로는 오판이 발생해 메모리 트래픽을 낭비하며, 우리의 캐시라인 수요가 CPU 캐시 전체 용량의 큰 비율을 차지한다는 사실이 오판 확률을 높인다.

비교를 위해, 해시 테이블에서는 캐시 시스템에 요구되는 추측이 훨씬 적다. 이상적인 캐시 시스템 성능에 근접하려면, 주요 목표는 많은 캐시 미스가 병렬로 진행되어 캐시 미스 지연(latency) 제약이 아니라 캐시 미스 처리량(throughput), 즉 메모리 대역폭에 의해 제한되도록 하는 것이다. 이를 위해 조회를 수행하기 64회전 앞서 캐시라인 프리패치 명령을 발행해, 동시에 64개의 캐시라인 페치를 진행 중으로 만든다. 이는 (a) 우리가 캐시 시스템에 원하는 동작을 _지시_할 수 있는 CPU 프리패치 명령이 있고, (b) 2048개 중 64개 라인만 핫하면 되며 1024개가 필요한 기수 정렬보다 실수 가능성이 훨씬 낮기 때문에, 기수 정렬보다 이상에 훨씬 더 근접한다.↩︎

5. Meta의 F14 테이블은 14개의 메타데이터 슬롯과 14개의 데이터 슬롯을 동일한 한 쌍의 캐시 라인에 나란히 배치해 지역성과 SIMD 프로빙을 모두 달성한다. 이 크기에서는 여전히 두 번(인접한) 미스가 필요하다. uint64 키에는 7슬롯 변형이 이상적일 것이다.↩︎

6. 프로빙을 캐시라인 정렬로 만드는 더 단순한 방법은 모든 프로브 시퀀스를 캐시 라인의 시작에서 _시작_하게 하는 것이다. 하지만 이렇게 하면 평균 프로브 길이가 늘어난다. 프로브 시퀀스 시작 위치의 수가 줄어들어, 서로 다른 두 키가 같은 위치에서 시작할 가능성이 더 커지기 때문이다.↩︎