정렬은 프로그래밍에서 가장 기본적인 연산이라 '이미 끝난 문제' 같지만, 실제로는 지금도 계속 빨라지고 있어요. 2022년 구글이 오픈소스 블로그에 공개한 vqsort가 대표적인 사례인데요. C++ 표준 라이브러리의 std::sort보다 약 10배 빠르고, 특정 CPU 전용으로 최적화된 당시 최신 알고리즘보다도 빠르면서, x86의 AVX2와 AVX-512, ARM의 NEON과 SVE, 심지어 RISC-V 벡터 확장까지 하나의 코드로 돌아간다는 게 핵심이에요. 몇 년 된 글이지만 이 글에 담긴 '분기 없는 코드'와 '이식 가능한 SIMD'라는 사고방식은 지금 봐도 배울 게 많아요.
SIMD가 뭐냐면
SIMD는 Single Instruction, Multiple Data의 약자예요. 명령어 하나로 여러 개의 데이터를 한꺼번에 처리하는 방식이죠. 보통 CPU가 정수 두 개를 비교하는 명령을 실행하면 한 쌍만 비교되는데, SIMD 명령을 쓰면 256비트 레지스터에 32비트 정수 8개를 담아서 8쌍을 동시에 비교할 수 있어요. 계란을 하나씩 옮기는 대신 계란판째로 옮기는 거라고 생각하면 돼요.
그런데 SIMD에는 약점이 있어요. if를 싫어한다는 거예요. 8개를 한꺼번에 처리하는데 그중 3개는 이쪽으로, 5개는 저쪽으로 보내야 한다면 한 번에 처리한다는 장점이 깨지죠. 그리고 퀵소트는 본질적으로 '피벗보다 작으면 왼쪽, 크면 오른쪽'이라는 if의 반복이에요. 그래서 오랫동안 정렬은 SIMD로 옮기기 어려운 알고리즘으로 여겨졌어요.
세 가지 핵심 아이디어
구글 팀은 이 문제를 크게 세 가지 방법으로 풀었어요.
첫째는 파티션을 벡터 단위로 처리하는 거예요. 파티션이 뭐냐면, 피벗 값을 기준으로 배열을 작은 쪽과 큰 쪽으로 가르는 퀵소트의 핵심 단계예요. vqsort는 원소 8개나 16개를 한 벡터로 읽고, 피벗과 한 번에 비교해서 어느 원소가 작은지를 비트 마스크로 만들어요. 그다음 압축(compress) 연산으로 마스크가 켜진 원소들만 앞으로 모아서 배열의 왼쪽 끝에 쓰고, 나머지는 오른쪽 끝에 써요. 분기 없이 마스크와 데이터 이동만으로 파티션이 끝나는 거죠. AVX-512에는 이 압축 명령이 아예 하드웨어로 있고, AVX2나 NEON처럼 없는 경우에는 마스크 값을 인덱스로 삼아 미리 만들어둔 순열 테이블을 찾아보고 셔플 명령으로 같은 효과를 내요.
둘째는 작은 구간에서 재귀를 멈추고 정렬 네트워크를 쓰는 거예요. 정렬 네트워크가 뭐냐면, 어떤 입력이 들어오든 항상 똑같은 순서로 '두 값을 비교해서 작은 걸 앞으로' 연산을 반복하는 고정된 회로예요. 데이터에 따라 실행 경로가 바뀌지 않으니 분기가 없고, 각 단계가 min과 max 연산이라 SIMD로 아주 잘 돌아가요. vqsort는 여러 벡터를 세로 방향으로 놓고 각 열을 정렬 네트워크로 정렬한 다음, 행과 열을 뒤집는 전치를 거쳐 병합하는 방식으로 수백 개 원소를 한 번에 정리해요.
셋째는 피벗을 똑똑하게 고르는 거예요. 배열에서 무작위로 샘플을 뽑아서 정렬 네트워크로 정렬한 뒤 그 중앙값을 피벗으로 써요. 무작위성이 들어가서 특정 입력으로 일부러 느리게 만드는 공격에 강하고, 모든 값이 똑같은 배열처럼 퀵소트가 취약한 패턴도 따로 감지해서 처리해요.
이 모든 걸 하나의 C++ 코드로 쓸 수 있게 해주는 게 Highway 라이브러리예요. 벡터 길이를 고정하지 않고 추상화해 두었기 때문에, 같은 소스가 AVX-512에서는 16개씩, NEON에서는 4개씩 처리하도록 컴파일되고 실행 시점에 CPU를 보고 알맞은 버전을 골라요. 결과적으로 최신 서버 CPU에서는 초당 수억 개 이상의 키를 정렬하는데, 이쯤 되면 메모리 대역폭이 병목이 되는 수준이에요. 참고로 안정 정렬은 아니고, 추가 메모리 없이 제자리에서 정렬해요.
다른 정렬들과 비교하면
정렬 세계의 최근 흐름을 보면 크게 두 갈래예요. 하나는 SIMD 없이 분기를 줄이는 쪽인데, pdqsort가 대표적이고 Rust 표준 라이브러리에 들어간 ipnsort와 driftsort, Go의 정렬도 이 계열이에요. 다른 하나는 SIMD를 정면으로 쓰는 쪽으로, vqsort와 인텔의 x86-simd-sort가 있어요. 인텔 쪽은 AVX-512 전용이라 최고 성능을 뽑기 쉽지만 ARM 서버에서는 못 쓰고, vqsort는 이식성을 우선했다는 차이가 있죠. 인텔 라이브러리는 numpy에 채택돼서 파이썬 사용자도 모르는 새 혜택을 보고 있어요.
우리한테 무슨 의미인가
C++ 개발자라면 Highway를 의존성으로 추가하고 바로 써볼 수 있어요. 게임 엔진, 로그 처리, 시계열 데이터베이스, 검색 인덱스처럼 정렬이 프로파일에 실제로 잡히는 곳이라면 시도해볼 가치가 충분해요. 다른 언어를 쓰더라도 배울 점은 분명해요. 분기를 없애면 CPU가 예측에 실패하는 일이 사라진다는 것, 데이터를 벡터 단위로 배치하면 같은 알고리즘도 완전히 다른 속도를 낸다는 것, 그리고 아키텍처별로 코드를 따로 쓰지 않고 추상화 계층 위에서 SIMD를 다룰 수 있다는 것이에요. 특히 요즘 국내에서도 AWS 그래비톤 같은 ARM 서버 도입이 늘고 있어서, 'x86에서만 빠른 코드'보다 '어디서든 빠른 코드'의 가치가 점점 커지고 있어요.
정리
40년 된 퀵소트도 분기를 걷어내고 벡터 단위로 다시 쓰면 10배 빨라질 수 있다는 걸 보여준 사례예요. 여러분은 프로파일링하다가 정렬이 병목으로 잡힌 경험이 있으신가요? 그리고 SIMD를 실무 코드에 직접 써본 적이 있다면 어떤 느낌이었는지도 궁금해요.
🔗 출처: Hacker News