구글이 수치 배열 정렬 성능을 획기적으로 개선한 SIMD(Single Instruction, Multiple Data) 기반 퀵정렬(Quicksort) 코드를 오픈소스로 공개했습니다. 이 새로운 구현은 C++ 표준 라이브러리(std::sort)보다 최대 19배 빠른 속도를 자랑하며, 기존 아키텍처 전용 정렬 알고리듬의 성능마저 능가합니다. 이는 정렬 작업이 필요한 다양한 애플리케이션의 성능 향상에 크게 기여할 것으로 기대됩니다.
이번 퀵정렬의 핵심은 CPU 시간의 대부분을 차지하는 분할(partitioning) 작업을 벡터화한 것입니다. 피벗(pivot)보다 작은 원소와 나머지 원소를 효율적으로 나누기 위해, Arm SVE, RISC-V V, x86 AVX-512 등 최신 명령어 집합의 compress-store 명령을 활용합니다. 이 명령은 특정 조건을 만족하는 원소만 연속된 메모리에 저장하는 방식으로, 정렬 성능을 크게 끌어올립니다. 또한, Highway 라이브러리의 이식 가능한 SIMD 함수를 사용하여 단일 구현으로 3개 아키텍처의 6개 명령어 집합을 지원하며, 16비트부터 128비트까지 다양한 입력 데이터를 처리할 수 있습니다. 3GHz 인텔 스카이레이크(Intel Skylake)의 AVX-512 환경에서는 약 1.12GB/s의 정렬 처리량을 기록하며, 이는 같은 CPU의 표준 라이브러리 대비 9~19배 빠른 수치입니다.
이러한 고성능 정렬은 열 지향 데이터베이스(Column-oriented database), 슈퍼컴퓨터, 머신러닝용 선형대수, 비디오 처리, 이미지 코덱 등 대량의 데이터를 빠르게 정렬해야 하는 분야에 큰 영향을 미칠 것입니다. 특히 정렬이 비용이 큰 작업으로 여겨졌던 과거와 달리, 이제 단일 CPU 코어에서 초당 1GB 이상의 정렬이 가능해지면서 새로운 애플리케이션과 기능 개발의 문이 열렸습니다. 구글은 이 코드를 아파치 2(Apache2) 라이선스로 GitHub에 공개하여 개발자들이 자유롭게 활용하고 개선할 수 있도록 했습니다.