Google의 범용 고속 정렬 알고리즘, C++ 표준 정렬보다 10배 빠름
원제 Vectorized and performance-portable Quicksort (2022)
148 포인트댓글 24
Key Point
단일 포터블 구현으로 모든 주요 CPU 아키텍처에서 기존 방식보다 10배 빠른 정렬을 가능하게 했으므로, 데이터베이스와 대규모 데이터 처리 애플리케이션의 성능 혁신을 기대할 수 있다.
핵심 요약
- Google이 SIMD 벡터 명령어를 활용한 Quicksort 구현을 공개했으며, C++ std::sort보다 9~19배 빠르다.
- 단일 구현으로 AVX2, AVX-512, Arm NEON 등 6가지 명령어 세트를 지원하며, 플랫폼별 최적화 코드 재작성을 제거했다.
- 압축-저장(compress-store) 명령어를 활용한 파티셔닝으로 정렬 성능의 대부분을 차지하는 단계를 가속화했다.
- AVX-512 CPU에서 32비트 수 백만 개를 초당 1,123MB/s 속도로 정렬하며, Apple M1에서는 499MB/s 속도를 달성한다.
- 16~128비트 입력을 모두 지원하며, Apache2 라이선스로 GitHub에서 오픈소스로 공개되었다.