Go 맵(map)의 성능을 향상시킨 스위스 테이블, 그 기술적 원리를 파헤치다!
by DD
2개월 전
조회수 16
Ravelin의 해커톤(Hackathon)에서 Go 맵(map)의 스위스 테이블(Swiss Table) 구현을 분석하여 성능 개선 가능성을 탐색함
선형 탐사(Linear Probing) 방식에서 개선된 프로브 시퀀스(Probe Sequence)를 적용하여, 테이블이 가득 찼을 때 성능을 향상시킴
그룹화(Grouping) 및 제어 바이트(Control Bytes)를 활용하여 해시 테이블의 성능을 더욱 개선하려 시도했으나, 선형 탐사 방식보다 성능이 저하됨
SIMD(Single Instruction, Multiple Data) 기술을 활용한 스위스 테이블 구현 가능성을 언급하며, 향후 성능 개선에 대한 기대감을 나타냄
스위스 테이블(Swiss Table)의 기본 원리
저자는 단순한 해시 테이블(Hash Table)에서 시작하여 Go 맵(map)에 사용된 스위스 테이블(Swiss Table)의 핵심 아이디어를 단계별로 설명한다. 선형 탐사(Linear Probing) 방식의 해시 테이블에서 시작하여, 프로브 시퀀스(Probe Sequence)를 개선하고, 그룹화(Grouping) 및 제어 바이트(Control Bytes)를 추가하는 과정을 벤치마크(Benchmark)와 함께 제시한다. 특히, 테이블이 가득 찼을 때 스위스 테이블이 기존 방식보다 뛰어난 성능을 보임을 강조한다.
프로브 시퀀스(Probe Sequence)의 중요성
저자는 기존의 선형 탐사(Linear Probing) 방식 대신, Go 맵(map)에서 사용되는 개선된 프로브 시퀀스를 소개한다. 이 시퀀스는 h, h+1, h+3, h+6, h+10과 같이 증가하는 간격으로 해시 테이블을 탐색한다. 이러한 방식은 발생 시, 연속된 슬롯(Slot) 점유로 인한 성능 저하를 완화하는 데 기여한다. 벤치마크 결과에 따르면, 이 방식은 테이블이 가득 찼을 때 기존 방식보다 훨씬 빠른 성능을 보인다.
