기존보다 10배 빠른 정렬 알고리즘 만들어버린 구글 엔지니어들

요약 구글 오픈소스 블로그를 통해 기존 C++ 표준 라이브러리(std::sort)보다 최대 10배 이상 빠른 최초의 벡터화 퀵소트(Vectorized Quicksort) 알고리즘 및 오픈소스 코드가 공개되었습니다. 최근 데이터베이스 업계에서는 컬럼 기반 데이터 처리가 대세로 자리 잡으면서 대용량 정렬 작업의 효율성이 중요해졌습니다. 연구진은 단일 명령어로 여러 데이터를 동시에 연산하는 SIMD(벡터 명령어) 기술을 퀵소트의 분할(Partitioning) 단계에 집중 적용했습니다. 피벗(기준값)을 기준으로 원소를 나누는 과정에 최신 CPU가 지원하는 'compress-store' 명령어와 치환(permute) 에뮬레이션 기법을 결합하여 병목을 대폭 개선했습니다. 특히 구글의 이식성 높은 라이브러리인 '하이웨이(Highway)'를 활용함으로써 x86(AVX2, AVX-512), Arm(NEON, SVE), RISC-V 등 3개 아키텍처, 6개 명령어 세트 전반에 걸쳐 코드 중복 없이 최적화된 성능을 발휘하도록 구현되었습니다. 또한 기존 32비트 정수 특화 연구들과 달리 16비트부터 128비트까지 폭넓은 데이터 타입을 지원합니다. 성능 측정 결과, 인텔 스카이레이크(AVX-512) 환경에서는 초당 1GB가 넘는 1,120MB/s 안팎의 정렬 속도를 기록하며 기존 C++ 표준 라이브러리 대비 9~19배 수준의 향상을 보였습니다. 애플 M1(Arm NEON)에서도 460~499MB/s의 높은 처리량을 달성했습니다. 연구진은 아파치 2.0 라이선스로 코드를 공개하며 단일 CPU 코어에서 1GB/s급 정렬이 가능해짐에 따라 다양한 고성능 컴퓨팅 분야에서 활용될 것으로 기대하고 있습니다.