C 퀵 정렬, std::sort보다 빠르다!

본 논문은 분기 예측 오류(Branch Misprediction)를 최소화하기 위해 분기문을 제거하는 기술을 소개한다. 특히, auxiliary buffer를 활용하여 분기 없는 파티셔닝(Partitioning)을 구현함으로써 성능을 향상시켰다. 실제 사례로, 분기 회피 기법을 적용한 퀵 정렬은 기존 퀵 정렬 대비 2배 이상 빠른 속도를 보였다.

저자는 소규모 데이터셋에 대해 정렬 네트워크(Sorting-Networks)를 적용하여 성능을 더욱 개선했다. 정렬 네트워크는 비교 및 교환 연산을 고정된 순서로 수행하여 분기를 완전히 제거한다. 특히, 최대 26개의 요소를 정렬하는 네트워크를 구현하여 std::sort 및 pdqsort보다 우수한 성능을 달성했다는 점이 주목할 만하다.

게시물은 다양한 정렬 알고리즘의 성능을 비교하는 벤치마크 결과를 제공한다. Apple M1 및 Intel Xeon 시스템에서 5천만 개의 정수를 정렬하는 데 걸리는 시간을 측정했다. Branch-Avoidant Quicksort는 std::sort 및 pdqsort보다 빠른 속도를 보였으며, 정렬 네트워크를 활용한 구현은 더욱 뛰어난 성능을 기록했다.

댓글에서는 heap_sort 구현의 오류를 지적하며, 해당 코드가 완전하지 않다고 비판했다. 특히, 힙 정렬의 핵심 부분인 'heapify'만 구현되어 있고, 최대 요소를 하나씩 꺼내는 과정이 누락되었다고 언급했다. 이러한 오류는 다른 자료에서도 발견되었다는 점에서, 코드 복제에 대한 커뮤니티의 우려(Community Concern)를 보여준다.