Swiss Table (2017)

2025년 2월 11일 Go 1.24 가 출시됐다. 이제부터 map의 구현은 Swiss table (2017)을 사용한다.

Swiss table은 이미 C++, Rust에서 사용하고있다고 한다.

0. 스포일러

Swiss table은 CppCon (2017) 에서 처음 소개됐다. 스스로 이해하는 것을 좋아하는 사람은 이 동영상과 약간의 검색으로 충분할 것이다.

Swiss table이 해결한 문제

1. 탐색(lookup) 성능 개선
2. 저장 공간 사용 개선

Swiss table이 동원한 수단

1. CPU가 메모리에 접근하는 방법(spatial locality) 고려
2. 비트 단위의 연산
3. SSE intruction

Swiss table은 알고리즘을 바꿨다기보다는 엔지니어링의 결과 같다. array를 사용하는 것은 원래 해시 테이블과 똑같다.

Swiss table 발표 강연은 해시 테이블의 발전 과정을 따라가면서 설명한다. 그래서 이 글도 똑같이 썼다. 그럼 가장 기본적인 해시 테이블부터 시작해보자.

1. Hash Table

해시 테이블은 collision 이 발생한다. Collision을 해결하는 방법은 두가지가 있다.

1. Chaining: 링크드 리스트에 element를 저장.
2. Open addressing: array에 element를 저장.

아래 그림은 chaining을 사용한 해시 테이블이다. 모르는 사람이 없을테니 설명은 하지 않겠다.

• H: 해시 코드; 해시 함수에 의해 임의로 만들어진 값 [*] [**]
• V: 가리키는 값; 해시 테이블의 value 부분
• Φ: Null pointer
• s: 인덱스
• size(): 해시 테이블에 저장된 element 개수
• bucket: element를 저장하는 곳; 여기서는 링크드 리스트
• bucket_count(): bucket 개수
• Load factor: 해시 테이블을 확장(resize)할 때 참고하는 값

[*] H와 s의 구분이 모호하다.

1. H: 어떤 해시 함수 의 값이다.
2. s: 일반적으로 생각하는 해시 값이다. 계산은 잘 알다시피 H % bucket_count()이다. 다른 방법도 있지만 여기서는 그렇게 간주하겠다.

[**] 해시 테이블을 확장할 때 s를 다시 계산해야하니까 H를 저장한다.

2. std::unordered_set

이 그림은 위에서 본 해시 테이블을 C++에서 구현한 것이다. 아까와 다른 점이 무엇인가?

알고리즘은 똑같다. 단지 구현이 좀 더 직관적으로 바뀐 것 뿐이다.

만약 s가 곧바로 링크드 리스트를 가리킨다면 첫번째 node가 있는지 없는지 검사해야한다. 대신 dummy node를 쓰면 첫번째 node는 항상 있으므로 특별한 if 절을 추가할 필요가 없다.

3. node_hash_set

unordered_set보다 더 나은 버전은 무엇일까? Open addressing 방법을 쓰면 된다.

링크드 리스트를 없애고 linear probing 으로 바꾸면 메모리를 절약할 수 있다. 이제 Value를 가리키는 포인터만 저장하면 된다. [*]

하지만 단점도 생긴다. Element를 삭제하면 빈 공간이 생긴다. 빈 공간은 tombstone 으로 표시해서 선형 탐색을 계속하라는 힌트를 남겨야한다. (그림에서 검게 칠한 부분) 그래서:

1. element를 삭제해도 탐색 성능이 나아지지 않는다.
2. element를 삭제해도 load factor가 변하지 않는다. Resize/Rehash가 더 많이 발생할 수 있다.

[*] 그림에서는 생략됐지만 key, value 둘 다 저장해야한다.

4. dense_hash_set

node_hash_set에서는 포인터를 저장했다. 그런데 굳이 포인터를 쓸 이유가 있을까?

dense_hash_set에서는 그냥 array에 element를 저장한다. 포인터가 없으니 메모리를 참조할 필요도 없고 공간도 절약할 수 있다. 그리고 메모리 locality때문에 탐색 속도도 더 빠르다.

• x axis: 해시 테이블에 저장된 element 개수 (Key size = 4byte)
• y axis: 탐색에 걸리는 시간

탐색 시간이 많이 개선됐다.

• small payload: Key size = 4byte
• large payload: Key size = 64byte

왜 key 사이즈가 성능에 영향을 미치는 걸까. dense_hash_set은 memory locality에 의존하기 때문에 key 사이즈가 커지면 paging 효율이 떨어진다는 이유 같다.

5. flat_hash_set

dense_hash_set 탐색할 때 key 사이즈가 크면 비교하는 시간이 오래 걸린다. 그럼 key를 대체할 수 있는 어떤 작은 값을 읽으면 되지 않을까?

flat_hash_set에서는 metadata를 사용한다.

5.1. Metadata

Metadata는 이렇게 구성한다. 크기는 8비트이고 MSB 를 element가 있는지 없는지 알리는 flag로 사용한다. 이것을 presence라고 부른다. 나머지 7비트는 해시 코드로 쓴다.

• presence = 1: 비었음
• presence = 0: element 있음; 해시코드 확인

5.2. Hash

metadata의 해시 코드 7비트는 그리 큰 숫자가 아니니까 collision이 일어날 수 있다. 그래서 더 긴 해시 코드와 함께 쓴다.

전체 해시 코드 크기는 64비트로 생성한다. 아래 7비트는 metadata로 쓰고 나머지 57비트는 인덱스를 계산할 때 쓴다.

여기까지 다시 정리해보자.

• H1: 데이터를 저장하는 array(slot)에서 인덱스를 결정할 때 쓰는 해시 코드.
• H2: metadata array(ctrl)에 저장해서 빠르게 탐색할 때 쓰는 해시 코드.

5.3. Data Structure

즉 flat_hash_set 해시 테이블은 2계층으로 생각할 수 있다.

• ctrl: metadata(presence + H2)를 저장하는 array
• slot: H1, value를 저장하는 array. H1 값이 같은 element는 바로 옆에 놓인다. (그림에서 같은 색으로 칠한 부분)

5.4. SSE Instruction

그런데 이렇게만 하면 탐색하는데 걸리는 시간은 dense_hash_set과 똑같다. 그래서 SSE instruction을 써야한다. SSE를 쓰면 metadata 16개를 거의 동시에 확인할 수 있다.

아래 SSE 명령어는 어셈블리어 명령어 한개로 처리할 수 있다고 한다.

_mm_set1_epi8: 128비트를 같은 값으로 초기화한다. 여기서 96은 예시로 만든 metadata(presence + H2) 값이다.

_mm_cmpeq_epi8: 128비트 두개를 비교해서 같은 값이면 0xFF, 다르면 0x00으로 만든다.

_mm_movemask_epi8: 각 8비트 중에서 가장 높은 위치의 비트를 반환한다.

위 명령어 3개를 조합한다. 찾고싶은 metadata 값을 가져와서 ctrlarray의 metadata 16개 중에 일치하는 것은 1, 다른 것은 0으로 나타낸다.

5.5. Group

SSE는 metadata 16개를 처리할 수 있으니 16개 element를 group으로 생각할 수 있다.

Group에서 탐색하는 방법은 이렇게 정리된다.

1. 16개의 metadata(ctrl) 중에서 일치하는 H2가 있는지 확인한다.
2. 일치하는 인덱스(slot)로 가서 H1 값을 비교한다.

알고리즘 설명 생략

5.5. Benchmark

Key 크기가 작고 element 개수가 적을 때는 dense_hash_set과 비슷하다. 나머지 상황에서는 더 빠른 속도를 보인다.

구글에서 migration하는 과정을 보여주고있다.

• x axis: 시간
• y axis: 구글 시스템에서 쓰는 CPU 총량
• 파랑: unordered_set
• 빨강: dense_hash_set
• 노랑: flat_hash_set
• 초록: __gnu_cxx::hash_map

어떻게 읽냐면 flat_hash_set이 차지하는 비율에 비해 전체 CPU가 얼마나 줄어들었나를 보면 된다.

이번엔 RAM 크기다.

5.6. 구현, 실험

CppCon 동영상에서는 구현에 대해 설명하고있다.

C++에서 unordered_set, dense_hash_set을 사용하는 예시를 보면서 flat_hash_set에서도 비슷한 행동을 할 수 있게 구현했다고 한다.

그리고 2017년 시점에서 여러가지 데이터 구조를 실험하고 있다고 한다.

나는 C++ 개발자가 아니니까 여기까지 알면 충분하다고 생각한다.

6. Swiss Table

flat_hash_set이 Swiss table이다.

구글에서 해시 테이블을 업그레이드하는 프로젝트를 맡은 팀장이 스위스 지부에 있고, Closed hash의 이니셜 'ch'가 스위스의 최상위 도메인 이름이라서 스위스 테이블이라고 이름을 정했다고 한다.

7. 소감

C++ 개발자가 무슨 일을 하고 있는지 잘 알 수 있었다. 이사람들이 진정한 프로그래머다.

x86 인스트럭션이 어떻게 사용되는지 처음으로 알게됐다. 최초의 x86 CPU는 1978년 인텔 8086이고 최초의 x86_64 CPU는 2003년 AMD Opteron이라고 한다. 내 CPU는 6코어짜리라고 무시했는데 새삼 다시보게됐다.

Rust가 C++를 대체할 수 있을까? 검색해보니 WASM SIMD는 기존 SIMD와 완벽히 호환된다고 한다. 잘 하고 있네...