SwissTable

SwissTable은 해시테이블의 최적화된 구현 형태 중 하나다.

2017년에 구글에서 처음 공개했으며, 처음 공개된 구현 버전은 C++이었다.

이전에 존재했던 해시테이블에 비해서 대체로 우월했고, 딱히 단점도 없어서 일부 언어들의 표준 라이브러리는 이걸로 대체되었다.

대표적으로 Rust의 std Hashmap(since 1.35), Go의 기본 map(since 1.24)이 swisstable 구현체다.
거의 최초로 전면 도입한게 Rust 쪽 환경인 것 같더라.

고전적인 해시테이블

대부분의 언어에서 제공하는 기본 해시테이블 구현체가 다음 방식을 따른다.

해시테이블은 기본적으로 그냥 배열이다.
Tom이니, John이니 하는 임의의 키값이 들어오면 그걸 해시함수 기반으로 각 배열 인덱스에 매핑시켜 저장하는 것이다. 보통 저 배열을 backing array이라고 부른다.

근데 문제는 해시값이 항상 충돌할 수 있다는 것이다.

다른 값이 동일하게 3 인덱스로 매핑되면 어떻게 할 것 같은가?

방법 1: Chaining

상당수의 해시테이블 구현에서는 아예 그냥 배열 요소 내부에 Linked List를 넣고, 한 키마다 여러개를 넣을 수 있도록 예외처리를 해둔다.

그래서 해시 충돌이 극심하게 발생한다면 한 요소의 데이터 크기가 비대해져서 삽입/삭제/조회 시간 등이 O(N)에 가깝게 나올 수도 있다는 단점이 있다. 물론 해시함수 성능에 따라서 갈리는 부분이긴 하다.

그리고 값이 단순히 삽입되거나 충돌될때마다 동적할당이 발생한다는 단점도 있고, Linked List 특유의 캐시 비친화성도 고질적인 한계 중 하나라고 할 수 있다.

방법 2. probing
이거 말고 probing(조사)라고 하는 방법도 있었다. open addressing이라고도 부른다.
사용 빈도는 chaining보다 낮긴 했는데, 그래도 꽤 쓰긴 썼다.

사실 원리는 별거 없다.
그냥 빈 공간 있으면 아무데나 저장하는 것이다. 그 아무데나를 어떻게 정할지도 구현 방법에 따라서 다르다.
가장 단순한 방법은 그냥 충돌이 발생한 다음 인덱스에 저장하는 것이다.

이런 식으로 말이다.

이러면 추가 할당이 Chaining에 비해서는 적을 수 있어서 나름 나쁘지 않은데, 충돌이 빈번하게 발생하거나 빈 Key가 적어진다면 성능이 급격하게 떨어진다는 단점이 있다.

https://hyoeun-log.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-11%EC%9E%A5-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94
사실 이런 불안정성 때문에 일반적으로 잘 쓰이지는 않는데, Python의 dict 구현 정도가 좀 특이하게 probing 기반으로 구현되었다.
물론 이걸 그냥 쓰면 꽉찼을때 성능이 아작나기 때문에 수용량, 그러니까 load factor을 더 민감하게 잡아놨다.

Swisstable

swisstable은 쉽게 말하면 이전에 반쯤 버려졌던 open addressing Hashtable의 변종이라고 할 수 있다.
그 기본 원리와 구조를 간단히 정리해보겠다.

Hash 값 구조

swisstable의 해시값은 반드시 8바이트 정수여야 한다.
왜나면 비트단위로 쪼개서 별개의 2가지 값을 동시에 사용하기 때문이다.

https://abseil.io/about/design/swisstables
그래서 상위 57비트를 우리가 원래 알던 테이블 분배용 키로 사용한다. 저게 같으면 같은 키고, 키가 같으면 충돌이 발생하는 것이다.
그리고 하위 7비트는 충돌이 발생했을 경우, probing을 위한 판단 기준으로 사용된다.

Probing

방금 언급한 7비트 H2 값을 충돌 발생 시 probing을 위한 부가 값으로 사용한다.
H1 키값이 같더라도 실제 값이 다르면 H2 값이 다를 확률이 매우 높으니, 그걸 기준으로 인덱스를 다시 분배해서 저장하는 것이다.

물론 이것도 결국 해시니까, 실제 원본 값이 다르더라도 H2 값에서도 해시 충돌이 발생할 수는 있다.
그래서 구현시에 예외처리는 해야겠지만 확률이 1/128 (2^7)로 낮아서 걱정할 일은 별로 없긴 하다.

SIMD

H2로 분산을 하든 어쨌든, Probing은 어쨌거나 H2 값 기반으로 빈자리가 나올때까지 찾아야 한다.
그러면 같은 그룹(H1 충돌 대상)에서 H2 값 기반으로 여러번 뒤져야할 수도 있는데, 그렇게 한다면 아무래도 성능상 비효율적인 부분이 발생할 수 있다.

그래서 swisstable을 SIMD를 응용해서 병렬 최적화를 달성한다.
어차피 H2는 1바이트짜리 작은 해시값이니까, SIMD에 8개-16개씩 우겨넣고 한번에 비교해서 빠르게 위치를 찾을 수 있는 것이다.

실성능

swisstable이 기존의 hashtable과 비교해서 빠르고 안정적이기도 하다는 것은 별로 이론의 여지가 없다.
검증도 거의 끝났고 사용에 아무런 문제가 없다.

추가 할당을 남발하지 않기 때문에 메모리 사용량에서는 배열과 거의 동등한 수준이다.

CPU 리소스 기준으로는 실제 속도도 2배 정도 빠르다고 하나, 이건 조금 구현 방식과 환경에 따라 다를 수 있다.
언어 환경에 따라서 (특히 Java의 경우) CPU Time 자체가 극적으로 줄어들지는 않는다는 의견도 있더라

참조
https://go.dev/blog/swisstable
https://github.com/rust-lang/hashbrown
https://abseil.io/about/design/swisstables
https://stackoverflow.com/questions/9010222/why-can-a-python-dict-have-multiple-keys-with-the-same-hash
https://dev.to/huizhou92/swisstable-a-high-performance-hash-table-implementation-1knc
https://leventov.medium.com/smoothiemap-2-the-lowest-memory-hash-table-ever-6bebd06780a3