분기 예측을 없앤 퀵 정렬, 속도가 2배 빨라진다!
분기 예측 실패(Branch Misprediction)를 회피하는 블랜치리스(Branchless) 기법으로 퀵 정렬 성능을 극대화함
Apple M1 및 AMD Ryzen 시스템에서 `std::sort` 대비 최대 2.8배 빠른 성능을 기록한 벤치마크 결과 제시
C/C++ 단일/멀티 스레드 버전을 제공하며, 커스텀 데이터 구조 정렬도 쉽게 지원함
최악의 입력 데이터(Bad Input Data)에 대한 O(n²) 방지를 위해 피벗 선택 및 힙 정렬 전환 전략 적용
블랜치리스 퀵 정렬(Branchless Quicksort)의 성능 이점
커뮤니티에서는 현대 CPU의 분기 예측 실패(Branch Misprediction) 회피가 프로그램 속도 향상의 핵심 기법임을 강조한다. 특히, 조건 분기(Conditional Branch)를 제거한 퀵 정렬 구현은 5천만 개의 double 데이터를 정렬하는 작업에서 `std::sort` 대비 Apple M1 시스템에서 약 1.4배, AMD Ryzen 시스템에서 약 2.8배의 성능 향상을 보였다고 언급한다. 이는 보조 버퍼(Auxiliary Buffer)를 활용한 데이터 복사를 통해 분기 예측 실패로 인한 오버헤드를 줄이는 전략에 기반한다.
다양한 하드웨어 및 언어 인터페이스 지원
제시된 벤치마크 결과는 Apple M1 및 AMD Ryzen 시스템에서 각각 Clang과 GCC 컴파일러를 사용하여 측정되었다. 특히 C++ 버전과 C 버전 간의 성능 차이가 미미하다는 점은 주목할 만하다. 또한, 단일 스레드(Single-Threaded) 및 멀티 스레드(Multi-Threaded) 버전을 각각 C와 C++로 제공하여 다양한 환경에서의 활용성을 높였다. 1024개 요소의 스택 배열(Stack Array)을 사용하는 보조 버퍼 전략은 힙 메모리(Heap Memory) 할당 오버헤드를 피한다.
최악의 입력 데이터(Bad Input Data) 방지 전략
O(n²) 시간 복잡도를 유발하는 최악의 입력 데이터 문제를 해결하기 위해, 동일 요소 그룹화(Grouping Identical Elements) 및 불균형 감지 시 힙 정렬(Heapsort) 전환 전략을 사용한다. 또한, 중앙값-중앙값(Median-of-Medians) 피벗 선택 전략과 루프 풀기(Loop Unrolling) 기법을 적용하여 파티셔닝 성능을 최적화한다. 2~16개 요소의 작은 부분 집합은 정렬 네트워크(Sorting Networks)를 사용하여 분기 없이 효율적으로 처리한다.
복사 비용이 높은 데이터 타입 처리 방안
문자열과 같이 복사 비용이 높은 데이터 타입의 경우, 보조 버퍼를 이용한 블랜치리스 방식의 효율성이 떨어진다. 이 경우, BlockQuicksort 변형을 사용하여 데이터 이동을 최소화하고 인덱스(Index)만 분기 없이 처리하는 방식을 채택한다. 이는 `std::sort`나 `pdqsort` 대비 복잡한 데이터 구조 정렬에서 상당한 성능 우위를 제공한다고 언급된다.
사용 편의성 및 커스텀 데이터 구조 지원
라이브러리는 `blqs.h` 또는 `blqsort.h` 헤더 파일 포함만으로 `std::sort`와 유사하게 쉽게 사용할 수 있다. C++에서는 연산자 오버로딩(Operator Overloading)을, C에서는 매크로(Macro)를 이용한 타입 및 비교 함수 정의를 통해 커스텀 데이터 구조 정렬을 지원한다. 실제 구조체 정렬 벤치마크에서도 `std::sort` 대비 Apple M1에서 약 3.8배, AMD Ryzen에서 약 2.2배의 성능 향상을 보여주었다.
