Go 맵(map)의 성능을 향상시킨 스위스 테이블, 그 기술적 원리를 파헤치다!
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과 같이 증가하는 간격으로 해시 테이블을 탐색한다. 이러한 방식은 해시 충돌(Hash Collision) 발생 시, 연속된 슬롯(Slot) 점유로 인한 성능 저하를 완화하는 데 기여한다. 벤치마크 결과에 따르면, 이 방식은 테이블이 가득 찼을 때 기존 방식보다 훨씬 빠른 성능을 보인다.
그룹화(Grouping) 및 제어 바이트(Control Bytes)의 활용
저자는 해시 테이블의 각 슬롯에 여러 개의 키-값 쌍을 저장하는 그룹화(Grouping) 방식을 시도했다. 또한, 각 그룹에 대한 제어 바이트(Control Bytes)를 추가하여, 잠재적인 일치 항목과 빈 항목을 빠르게 식별하고자 했다. 하지만, 이러한 방식은 선형 탐사(Linear Probing) 방식보다 성능이 저조했다. 이는 그룹 내에서 키를 검색하는 과정에서 발생하는 오버헤드(Overhead) 때문일 수 있다.
SIMD(Single Instruction, Multiple Data) 기술 적용 가능성
저자는 SIMD(Single Instruction, Multiple Data) 기술을 활용하여 스위스 테이블의 성능을 더욱 향상시킬 수 있다고 언급한다. SIMD는 단일 명령어로 여러 데이터를 처리하는 기술로, 제어 바이트(Control Bytes)를 검사하는 과정을 가속화할 수 있다. Go 1.26 버전부터는 인텔 칩(Intel Chips)에서 SIMD를 효율적으로 사용할 수 있는 라이브러리가 제공되지만, 저자는 현재 접근 가능한 환경에서는 AVX512 명령어를 지원하는 CPU가 없어 SIMD 구현을 시도하지 못했다.
커뮤니티 반응: 기존 C++ 스위스 테이블과의 관계
댓글에서는 Go의 스위스 테이블이 기존 C++의 스위스 테이블과 동일한 디자인을 기반으로 한다는 점을 지적한다. 특히, 2017년 구글(Google)에서 발표하고 Abseil C++ 라이브러리에 공개된 스위스 테이블 디자인을 차용했음을 언급한다. 해시 테이블(Hash Table)은 성능이 중요한 분야에서 널리 사용되며, 특히 테이블의 크기를 조정해야 할 때 성능 문제가 발생할 수 있다는 점을 강조한다.
