L1 Cache 최적화 BusSort로 Java Dual-Pivot QS 대비 2배 속도 달성

Context

대규모 데이터 정렬 시 Dual-Pivot Quicksort의 무작위 쓰기 작업으로 인한 Cache Thrashing 발생. 배열 규모 확장에 따른 L1, L2 Cache Miss 증가가 성능 병목의 핵심 원인으로 분석됨.

Technical Solution

• L1 Cache 크기(48KB)에 맞춘 4096개 정수 단위의 Chunk 처리 구조 설계
• 4단계 Pass(Histogram 생성, Prefix Sum 계산, Local Buffer Scatter, Global Copy)를 통한 데이터 이동 최적화
• L1-sized Local Buffer 사용으로 Random Write의 Cache 범위 내 유지 및 메모리 접근 지연 최소화
• 128-way Splitting 기법을 적용하여 1억 개 요소 기준 재귀 깊이를 약 4단계로 제한
• 1024개 이하 소규모 데이터 세트에 대해 Insertion Sort를 Base Case로 채택하여 오버헤드 제거

Impact

• Random 데이터 100M개 정렬 시 Java Dual-Pivot QS(8604ms) 대비 약 2배 빠른 3991ms 기록
• Duplicates 데이터셋에서 최대 2.4배의 성능 향상 달성
• Stable Sort 특성을 유지하며 비교 연산 오버헤드 제거

Key Takeaway

알고리즘의 시간 복잡도(Big-O)를 넘어 하드웨어 계층의 Cache Line 및 메모리 계층 구조를 고려한 Cache-aware 설계가 실제 런타임 성능을 결정짓는 핵심 요소임.