구글이 C++ 표준 라이브러리(std::sort)보다 최대 19배 빠른 퀵정렬(Quicksort) 알고리즘을 오픈소스로 공개했습니다. 이 새로운 정렬 코드는 모든 최신 CPU 아키텍처에서 이식성을 유지하면서도, 기존의 아키텍처별 최적화 알고리즘보다도 뛰어난 성능을 보여줍니다. 이는 데이터베이스, 머신러닝 등 정렬 작업이 핵심인 분야에서 상당한 속도 향상을 가져올 것으로 예상됩니다.
이러한 성능 향상의 핵심은 SIMD(Single Instruction, Multiple Data) 명령어 활용에 있습니다. SIMD는 하나의 명령어로 여러 데이터를 동시에 처리할 수 있어, 예를 들어 AVX-512 명령어 세트에서는 16개의 float32 데이터를 한 번에 처리할 수 있습니다. 구글은 이 기술을 퀵정렬의 핵심 단계인 파티셔닝(partitioning)에 적용했습니다. 특히, 현대 명령어 세트(Arm SVE, RISC-V V, x86 AVX-512)에 포함된 '압축 저장(compress-store)' 명령어를 활용하여 특정 값보다 작거나 큰 요소를 효율적으로 분리하며, 이 명령어가 없는 AVX2 같은 환경에서는 순열(permute) 명령어를 에뮬레이션하여 이식성과 성능을 동시에 확보했습니다. 구글은 이를 위해 Highway라는 휴대용 SIMD 함수 라이브러리를 사용해 약 3,000줄의 C++ 코드를 각 플랫폼별로 재구현할 필요 없이 단일 코드로 다양한 아키텍처를 지원합니다.
실제로 100만 개의 32비트 정수를 정렬할 때, 애플 M1 칩에서는 499MB/s, AVX-512를 지원하는 3GHz Skylake CPU에서는 1123MB/s의 속도를 기록했습니다. 이는 C++ 표준 라이브러리가 같은 CPU에서 58MB/s를 기록한 것과 비교하면 9배에서 최대 19배 빠른 속도입니다. 이처럼 정렬 속도가 획기적으로 빨라지면서, 그동안 비용이 많이 든다고 여겨졌던 정렬 작업에 대한 인식이 바뀔 수 있습니다. 단일 CPU 코어에서 초당 1GB의 속도로 정렬이 가능해지면서, 컬럼형 데이터베이스, 실시간 데이터 분석, 대규모 데이터 처리 등 다양한 분야에서 새로운 애플리케이션과 기능이 개발될 수 있는 잠재력이 열렸습니다.