GN⁺: Static Search Trees : 이진 검색보다 40배 빠르게
(curiouscoding.nl)- "S+ 트리"라는 정적 탐색 트리를 구현하여 정렬된 데이터의 고속 검색을 수행
- Algorithmica 포스트에서 제안된 코드를 출발점으로 삼아 최적화하고, 제안된 추가 아이디어 및 개선 작업을 코드화
- 어셈블리 코드를 분석후 가능한 모든 명령어를 최적화하여 성능 극대화
- 다수의 쿼리를 병렬로 처리하여 처리량(throughput)을 향상시키는 배칭(batching)을 도입
- 목표는 S+ 트리를 통해 정렬된 데이터에서 높은 처리량을 유지하며 효율적으로 쿼리를 수행하는 것
1. 소개 및 동기
-
문제 정의:
- 입력: 정렬된 32비트 부호 없는 정수 리스트
vals: Vec<u32> - 출력: 최소한의 크기로, 특정 쿼리 (q) 이상인 값을 반환하는 데이터 구조
- 메트릭: 초당 처리 가능한 독립적인 쿼리 수
- 입력: 정렬된 32비트 부호 없는 정수 리스트
-
목적:
- 생물정보학에서 효율적인 데이터 구조 구축, 특히 DNA 서열 색인을 위한 접미사 배열 검색 속도 향상
- CPU 성능 및 SIMD 명령어를 활용한 성능 극대화 목표
-
추천 자료:
- 이진 탐색과 배열 레이아웃 연구 (“Array Layouts for Comparison-Based Searching”)
- S+ 트리와 정적 B-트리 소개 자료
2. S+ 트리와 최적화
2.1 이진 탐색 및 Eytzinger 레이아웃
- Rust 표준 라이브러리의 이진 탐색은 캐시 효율이 떨어지며, 데이터 크기 증가 시 성능 저하
-
Eytzinger 레이아웃:
- 이진 탐색 트리를 배열 형태로 저장, 캐시 활용 극대화
- 성능: L3 캐시를 넘어가는 데이터에 대해 이진 탐색보다 최대 4배 빠름
2.2 S+ 트리 개념
-
S-트리:
- 노드당 15개의 정렬된 값을 포함한 16진 트리 형태
- B-트리보다 효율적이고 Eytzinger 레이아웃보다 압축 가능
-
S+ 트리:
- 모든 데이터를 리프 노드에 저장하며, 상위 노드에 중복 저장
- 단순한 검색 및 효율적 구조 제공
2.3 find 함수 최적화
-
기본 선형 탐색:
- 데이터를 순회하며 조건에 맞는 값 반환 (비효율적)
-
자동 벡터화:
- 분기 없는 코드로 변환, SIMD 명령어 활용으로 성능 2배 향상
-
수동 SIMD 구현:
- 수동으로 SIMD 명령어를 활용해 최적화, 5개의 명령어로 성능 극대화
3. 배칭과 사전 가져오기
3.1 배칭 (Batching)
- 여러 쿼리를 병렬로 처리, 메모리 대기 시간을 상쇄
- 배치 크기를 늘리며 처리량 개선, 최대 배치 크기 16에서 포화
3.2 사전 가져오기 (Prefetching)
- 다음 노드를 미리 메모리에 가져와 L3 캐시를 넘어가는 데이터에서 성능 향상
- 배칭과 결합해 처리 시간 45ns/query에서 30ns/query로 단축
4. 데이터 레이아웃 및 구조 최적화
4.1 노드 크기 변경
- 노드당 값을 15개로 줄여 곱셈 연산 단순화, 캐시 효율성 증가
- L3 캐시 내 데이터에 대해 약간의 성능 향상
4.2 메모리 레이아웃 변경
- 레이아웃을 역순으로 저장하거나 패딩을 최소화한 구성 실험
- 역순 및 패딩 감소 레이아웃 모두 성능에 큰 영향 없음
5. 데이터 파티셔닝
5.1 접두사 기반 파티셔닝
- 데이터의 상위 비트를 기준으로 파트 분리
- 작은 데이터에 대해 성능 향상, 그러나 메모리 오버헤드 발생
5.2 압축된 서브트리
- 각 서브트리를 패킹하여 공간 효율성 증가
- 파트의 크기 추적 필요, 쿼리 속도는 다소 감소
6. 다중 스레드 비교
- 6개 스레드 사용 시 쿼리 시간 27ns → 7ns로 단축
- RAM 대역폭 제한이 병목이 됨
7. 결론 및 향후 연구
- 이진 탐색 대비 40배 이상의 성능 향상 (1150ns/query → 27ns/query)
-
향후 과제:
- 데이터 균형 최적화 및 RAM 액세스 감소
- 범위 쿼리 및 정렬 쿼리 처리
- 접미사 배열 검색 통합
Hacker News 의견
-
Rust가 알고리즘 관련 저수준 콘텐츠에서 점점 더 많이 사용됨을 관찰함. 과거에는 C(++)나 과학적인 의사코드로 작성된 콘텐츠가 주를 이루었음. Rust의 사용이 증가하는 것을 긍정적으로 봄
- Rust를 잘 모르지만, Rust로 작성된 콘텐츠를 이해할 수 있었음. C로 작성된 알고리즘 예제를 Rust 프로그래머가 이해할 수 있는 것과 유사함
- Rust가 표준화되는 것을 선호하며, Zig도 함께 사용되면 좋겠다고 생각함
-
쿼리를 배치로 나누는 방법이 탐구되지 않았음. 캐시 외부 테이블에서 조회하는 것이 주요 비용임
- 충분히 많은 쿼리가 있을 경우, 트리의 여러 계층을 한 번에 해결할 수 있음
- 결과를 올바른 출력 순서로 정렬해야 하는 문제가 발생할 수 있음
-
int32 값의 수는 많지 않으며, 전체 비트셋은 512MB임. 일반적인 데이터 구조로는 Roaring Bitmaps를 추천함
- 단순 조회만 필요하다면 최소 완벽 해시 함수를 고려할 가치가 있음
-
Rust에서 저수준 효율성을 높이는 방법에 대해 놀라움을 느낌. C++ 구현과 비교해보고 싶음
-
Eytzinger 트리의 장점은 노드 인덱스를 중위 순회 위치로 변환하는 공식이 있다는 것임
- 기본 키 저장소가 정렬된 키 집합일 경우 유용함
- Eytzinger를 사용하면 여러 루프 반복을 사전에 예측할 수 있음
-
4GB 메모리에서 u32를 검색하는 데 ~27ns의 오버헤드가 발생하는 것이 놀라움
- 배치 크기 8에서 최적화가 어떻게 진행되는지 궁금함
- 멀티스레딩 결과도 흥미로움. 1에서 6 스레드로 전환 시 오버헤드가 4배 개선됨
-
Rust와 C++에 대한 논의가 많지만, Common Lisp에서 SIMD를 유지하며 구현하는 방법을 고민함
-
저수준 최적화에 대한 글을 읽을 때마다 저자가 시간을 들여 나노초를 절약해 준 것에 감사함
- 이러한 최적화가 쌓여 인류가 얼마나 많은 시간을 절약했는지 궁금함
-
1.7 그림 3에 오류가 있다고 생각함. 1.3 그림 1의 y축 레이블이 "역전송량"이어야 한다고 제안함
-
가끔 쓰기를 지원해야 한다면, 큰 정적 검색 트리와 작은 쓰기 가능한 트리를 사용할 수 있음
- 충분한 변경이 있을 때 정적 트리의 새 버전으로 변경 사항을 전송할 수 있음