벡터화와 성능 이식성을 갖춘 Quicksort (2022)

Google이 SIMD 기반 Quicksort 코드를 오픈소스로 공개함. 수치 배열 정렬에서 C++ std::sort보다 약 10배 빠르며, 기존 아키텍처 전용 정렬 알고리듬도 능가함 CPU 시간 대부분을 차지하는 분할 작업을 벡터화함. 피벗보다 작은 원소와 나머지를 compress-store 명령으로 나누고, 해당 명령이 없는 환경에서는 순열 명령으로 같은 동작을 구현함 Highway의 이식 가능한 SIMD 함수를 사용해 단일 구현으로 3개 아키텍처의 6개 명령어 집합을 지원하며, 16~128비트 입력을 처리함 3GHz Intel Skylake의 AVX-512 환경에서 약 1.12GB/s의 정렬 처리량을 기록함. 같은 CPU의 표준 라이브러리 대비 수치 자료형에 따라 9~19배 빠름 AVX-512는 AVX2보다 1.4~1.6배 빠르며, Highway가 CPU에서 사용 가능한 최적의 명령을 선택하므로 이 성능 향상을 위해 별도 구현이 필요하지 않음 열 지향 데이터와 SIMD 정렬 열 지향 데이터베이스는 한 레코드의 모든 필드를 연속 저장하는 대신, 특정 열의 값을 연속 저장함. SQL 쿼리의 핵심 구성 요소인 필터링과 정렬을 더 빠르게 처리할 수 있어 이번 구현은 이 데이터 배치에 초점을 맞춤 SIMD/벡터 명령은 독립적인 여러 원소에 대한 연산을 한 명령으로 수행함 AVX-512는 float32 16개, Arm NEON은 4개를 한 번에 처리할 수 있음 슈퍼컴퓨터, 머신러닝용 선형대수, 비디오 처리, JPEG XL 같은 이미지 코덱에서도 활용됨 정렬은 인접한 배열 원소를 재배치해야 하므로, 독립적인 원소를 처리하는 SIMD를 분할 단계에 적용하는 것이 핵심임 Quicksort 분할을 벡터화하는 방법 Quicksort 알고리듬은 배열을 피벗보다 작은 원소와 나머지 원소로 나눈 뒤 재귀적으로 처리함. 이상적인 피벗은 중앙값임 하위 배열이 256개 원소 이하가 될 때까지 분할하고, 작은 배열을 위한 별도 정렬 방법을 적용함 분할이 CPU 시간 대부분을 차지하므로 이 단계를 SIMD로 가속하면 전체 정렬도 빨라짐 Arm SVE, RISC-V V, x86 AVX-512의 compress-store 명령은 조건을 충족한 원소만 연속된 메모리에 저장함 각 원소가 피벗보다 작은지를 나타내는 참/거짓 값을 입력으로 사용해, 조건을 충족한 원소를 첫 번째 분할 영역에 저장함 참/거짓 값을 논리적으로 반전한 뒤 같은 명령을 다시...