바이너리 서치 6배 빨라진 비결: CPU의 '기계적 공감'

Faster binary search: from compiled code to mechanical sympathy

scikit-learn의 그라디언트 히스토그램 부스팅 알고리즘에서 사용되는 바이너리 서치를 6배나 빠르게 최적화한 사례를 소개합니다. 단순히 알고리즘을 바꾸거나 병렬 처리를 도입하는 대신, CPU의 분기 예측 실패(branch misprediction)와 명령어 수준 병렬 처리(ILP) 같은 하드웨어 동작 방식을 이해하고 코드를 조정했습니다. 분기 없는(branchless) 구현, Rust의 `select_unpredictable` 힌트, 안전하지 않은(unsafe) 경계 검사 제거, 사전 계산 등을 통해 놀라운 성능 향상을 이뤄냈습니다. 이 과정에서 CPU의 기계적 동작 원리와 최적화 기법을 자세히 설명합니다.