벡터화된 성능 이식성 Quicksort — std::sort보다 10배 빠른 Google의 SIMD 정렬

본문

Google Brain Computer Architecture Research의 Jan Wassenberg가 숫자 배열을 C++ std::sort보다 약 10배 빠르게 정렬하는 오픈소스 코드를 공개했습니다. 아키텍처별로 특화된 기존 최첨단 알고리즘보다도 빠르면서, 모든 최신 CPU 아키텍처에서 이식 가능하게 동작한다는 점이 특징입니다.

왜 지금 정렬인가 — 컬럼형 데이터베이스와 SIMD

배경에는 컬럼형(columnar) 데이터베이스의 확산이 있습니다. 레코드의 모든 필드를 연속 저장하는 행 기반 방식과 달리, 특정 컬럼의 값을 연속적으로 저장하는 방식은 필터링과 정렬에 유리하며 이는 SQL 쿼리의 핵심 구성 요소입니다. 정렬처럼 오래 연구된 분야에서 어떻게 10배 향상이 가능했을까요. 답은 SIMD/벡터 명령어에 있습니다. SIMD는 하나의 명령어로 여러 독립 요소를 동시에 처리하는데, 예를 들어 AVX-512에서는 float32 16개를, Arm NEON에서는 4개를 한 번에 연산합니다.

Compress-store로 파티셔닝하기

문제는 SIMD가 독립 요소만 다루는데 정렬은 인접 요소를 재배열해야 한다는 점입니다. 해법은 Quicksort의 구조에 있습니다. 배열을 피벗(pivot)보다 작은 값과 나머지로 분할(partition)한 뒤 재귀하고, 일정 크기 이하(예: 256개)가 되면 특수한 방법으로 정렬합니다. 이 분할 단계가 CPU 시간의 대부분을 차지하므로 여기를 SIMD로 가속하면 전체가 빨라집니다. 최신 명령어 집합(Arm SVE, RISC-V V, x86 AVX-512)에는 yes/no 입력을 받아 'yes'인 요소만 연속 메모리에 저장하는 compress-store 명령어가 있어 파티셔닝에 적합합니다. 이 값을 논리 부정한 뒤 한 번 더 적용하면 반대쪽 파티션도 채울 수 있습니다. compress-store가 없는 AVX2 같은 환경에서는 permute 명령어로 동일 동작을 에뮬레이션하는 기존 연구를 활용했습니다.

Highway로 한 번만 구현해 6개 ISA 지원

이 구현은 Highway의 이식 가능한 SIMD 함수를 사용해 3개 아키텍처의 6개 명령어 집합을 지원하는 최초의 벡터화 Quicksort입니다. 플랫폼마다 약 3,000줄의 C++ 코드를 다시 작성할 필요가 없으며, Highway가 compress-store를 쓸 수 있으면 그대로 쓰고 없으면 permute로 대체합니다. 32비트 정수 전용이었던 기존 최첨단 구현과 달리 16~128비트 입력 전 범위를 지원합니다.

성능 수치

Apple M1(Arm NEON)에서 100만 개의 32/64/128비트 숫자를 각각 499/471/466 MB/s로 정렬했습니다. 3GHz Skylake의 AVX-512에서는 1123/1119/1120 MB/s를 기록했습니다. AVX-512는 AVX2 대비 1.4~1.6배 빨랐는데, Highway가 CPU의 가용 명령어를 검사해 최적 버전을 자동 선택하므로 추가 노력 없이 얻은 이득입니다. AVX2에서 798 MB/s를 측정해 AVX2 전용으로 최적화된 기존 구현(699 MB/s)을 앞섰고, 같은 CPU에서 표준 라이브러리가 58/128/117 MB/s였으므로 타입에 따라 9~19배의 속도 향상입니다.

저자는 정렬이 비싼 연산으로 여겨졌던 과거와 달리 단일 CPU 코어에서 1GB/s로 정렬할 수 있게 되면 어떤 새로운 애플리케이션이 열릴지 기대한다고 밝혔습니다. 코드는 Apache2 라이선스로 GitHub에 공개됐고, 256개 요소 특수 처리를 포함한 상세 설명과 평가는 논문에서 확인할 수 있습니다.

Hacker News 반응

• @glouwbug — 아주 훌륭하네요. 이제 Paul Allen의 quicksort를 볼까요.
• @kg — 숫자 리스트를 벡터화해서 정렬하는 게 왜 필요한지 궁금하다면, 한 가지 용도는 히스토그램 만들기입니다. 샘플을 먼저 전부 정렬해 두면 히스토그램을 만들기가 훨씬 쉽습니다.
• @mcdonje — 몇 년이 지난 지금 이걸 실제로 구현한 앱이 뭐가 있을지 궁금합니다.
• @sigbottle — 솔직히 돌이켜 보면 제 삶과 관심사의 너무 많은 것들에 대해 똑같이 느낍니다.
• @trueno — 읽고 나서 같은 생각이 들었습니다. 정말 근본 있는 아이디어라 저에게 로그오프할 영감까지 줬습니다.

원문: Google Open Source Blog / 번역·요약: Trawling