# Static Search Trees : 이진 검색보다 40배 빠르게

> Clean Markdown view of GeekNews topic #18540. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=18540](https://news.hada.io/topic?id=18540)
- GeekNews Markdown: [https://news.hada.io/topic/18540.md](https://news.hada.io/topic/18540.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-01-02T09:42:19+09:00
- Updated: 2025-01-02T09:42:19+09:00
- Original source: [curiouscoding.nl](https://curiouscoding.nl/posts/static-search-tree/)
- Points: 22
- Comments: 2

## Summary

"S+ 트리"는 정렬된 데이터의 고속 검색을 위해 최적화된 정적 탐색 트리로, 이진 탐색보다 최대 40배 빠른 성능을 제공합니다. 이 트리는 Eytzinger 레이아웃을 활용하여 캐시 효율성을 극대화하고, SIMD 명령어를 통해 성능을 더욱 향상시킵니다. 또한, 배칭과 사전 가져오기 기법을 도입하여 쿼리 처리 시간을 크게 단축시켰으며, 다중 스레드를 사용하여 쿼리 시간을 27ns에서 7ns로 줄였습니다.

## Topic Body

- "S+ 트리"라는 정적 탐색 트리를 구현하여 정렬된 데이터의 고속 검색을 수행   
- Algorithmica 포스트에서 제안된 코드를 출발점으로 삼아 최적화하고, 제안된 추가 아이디어 및 개선 작업을 코드화  
- 어셈블리 코드를 분석후 가능한 모든 명령어를 최적화하여 성능 극대화  
- 다수의 쿼리를 병렬로 처리하여 처리량(throughput)을 향상시키는 배칭(batching)을 도입  
- 목표는 S+ 트리를 통해 정렬된 데이터에서 높은 처리량을 유지하며 효율적으로 쿼리를 수행하는 것  
  
### 1. 소개 및 동기  
- **문제 정의**:  
  - 입력: 정렬된 32비트 부호 없는 정수 리스트 `vals: Vec<u32>`  
  - 출력: 최소한의 크기로, 특정 쿼리 \(q\) 이상인 값을 반환하는 데이터 구조  
  - 메트릭: 초당 처리 가능한 독립적인 쿼리 수  
  
- **목적**:  
  - 생물정보학에서 효율적인 데이터 구조 구축, 특히 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 액세스 감소  
  - 범위 쿼리 및 정렬 쿼리 처리  
  - 접미사 배열 검색 통합

## Comments



### Comment 32965

- Author: beenzinozino
- Created: 2025-01-04T02:52:52+09:00
- Points: 1

이야... 다양한 언어의 내장 라이브러리에 적용되면 파급효과가 상당할 것 같습니다.

### Comment 32868

- Author: neo
- Created: 2025-01-02T09:42:19+09:00
- Points: 2

###### [Hacker News 의견](https://news.ycombinator.com/item?id=42562847) 
- 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축 레이블이 "역전송량"이어야 한다고 제안함

- 가끔 쓰기를 지원해야 한다면, 큰 정적 검색 트리와 작은 쓰기 가능한 트리를 사용할 수 있음
  - 충분한 변경이 있을 때 정적 트리의 새 버전으로 변경 사항을 전송할 수 있음