if문을 없앴더니 정렬이 더 빨라졌다 — 브랜치리스 퀵소트 이야기

std::sort보다 빠른 정렬이 나왔다고?

C++ 표준 라이브러리에 들어 있는 std::sort는 수십 년간 다듬어진, 정말 빠르기로 소문난 정렬 함수예요. 여기에 더해 pdqsort(pattern-defeating quicksort)라는, 현대 정렬의 끝판왕 소리를 듣는 알고리즘도 있고요. 그런데 이 둘보다 더 빠른 '브랜치리스 퀵소트(branchless quicksort, blqsort)'가 등장했어요. C와 C++ 양쪽에서 쓸 수 있는 API까지 제공하면서요.

어떻게 그 잘 만들어진 라이브러리들을 이겼을까요? 비밀은 제목 그대로 '브랜치(branch)를 없앤 것'에 있어요.

브랜치가 뭐고, 왜 느림의 원인일까

'브랜치'는 쉽게 말해 if문 같은 조건 분기예요. '이 값이 저 값보다 크면 이쪽, 아니면 저쪽' 하고 길이 갈라지는 지점이죠. 사람 눈엔 별것 아니지만, CPU 입장에선 골치가 아파요.

요즘 CPU는 속도를 높이려고 '분기 예측(branch prediction)'이라는 걸 해요. 이게 뭐냐면, if문 결과가 나오기 전에 '아마 이쪽으로 갈 거야'라고 미리 찍고 다음 작업을 앞당겨 실행하는 거예요. 예측이 맞으면 공짜로 시간을 번 거지만, 틀리면 미리 해둔 작업을 다 버리고 처음부터 다시 해야 해요. 이 손해를 '분기 예측 실패 페널티'라고 불러요.

그런데 정렬은 데이터를 비교하는 게 일의 전부라, 이 비교 결과가 들쭉날쭉이에요. 무작위 데이터를 정렬할 때는 '클까 작을까'가 거의 동전 던지기라서, CPU의 예측이 절반쯤 빗나가요. 즉 정렬은 분기 예측이 가장 자주 실패하는 작업 중 하나라서, if문 하나하나가 성능을 갉아먹는 거죠.

그래서 if문 대신 '계산'으로 바꾼다

브랜치리스 기법의 핵심은 '길을 갈라지게 하지 말고, 산술 계산으로 결과를 만들어내자'는 거예요. 예를 들어 '조건이 참이면 위치를 한 칸 옮긴다'를 if문으로 짜는 대신, 비교 결과(참은 1, 거짓은 0)를 그대로 더해서 위치를 옮겨요. 그러면 CPU 입장에선 갈림길이 없으니 예측할 것도, 틀려서 되돌릴 것도 없어요. 흐름이 한 줄로 쭉 이어지죠.

퀵소트에서 가장 분기가 많은 부분이 '파티션(partition)' 단계예요. 기준값(pivot)보다 작은 것과 큰 것을 양쪽으로 나누는 과정인데, 여기서 매 원소마다 if 비교가 일어나거든요. blqsort는 이 파티션을 브랜치리스로 다시 짜서, 예측 실패 페널티를 통째로 날려버린 거예요. 분기 예측이 잘 안 되는 무작위·반복 데이터에서 특히 효과가 크게 나타나고요.

업계 맥락

사실 '브랜치리스로 정렬을 빠르게 하자'는 아이디어는 앞서 말한 pdqsort나 인텔이 SIMD(한 번에 여러 데이터를 처리하는 명령)를 활용해 만든 정렬들에서도 핵심으로 쓰였어요. blqsort는 그 흐름 위에서 브랜치리스 파티션을 더 극단적으로 밀어붙이고, C/C++ 양쪽에서 바로 갖다 쓸 수 있게 API를 깔끔하게 정리한 게 강점이에요. '새로운 마법'이라기보단, 검증된 기법을 더 날카롭게 벼린 결과물에 가깝죠.

한국 개발자에게

대부분의 실무에선 std::sort나 언어 기본 정렬을 쓰는 게 맞아요. 굳이 정렬을 직접 최적화할 일은 드물거든요. 그래도 이 사례에서 꼭 챙겨야 할 교훈이 있어요. 바로 '알고리즘의 복잡도(Big-O)가 같아도 실제 속도는 하드웨어 특성에 따라 크게 갈린다'는 점이에요. 같은 O(n log n)인데도 CPU의 분기 예측, 캐시 친화성 같은 걸 고려했느냐에 따라 몇 배씩 차이가 나니까요. 성능에 진심인 분야(게임 엔진, 고빈도 거래, DB 내부)로 간다면 이런 저수준 감각이 진짜 무기가 됩니다. 직접 안 쓰더라도 '왜 빠른지' 원리를 이해해두면 코드를 보는 눈이 달라져요.