성능보다 정확성이 중요한 도메인 개발을 오래 해온 엔지니어라면, Rust로 코드를 짜고 N+1 쿼리만 피하면 대체로 충분히 빠르다는 감각에 익숙할 것이다. 그러나 실제로 뜨거운 경로(hot path)를 최적화해야 하는 순간이 오면 이야기가 달라진다. 한 개발자가 자신의 블로그에서 소개한 사례는 바로 그 지점에서 출발한다. 슬라이스에 담긴 숫자 중 임계값보다 큰 값만 골라내는, 데이터베이스 엔진이 하루 종일 처리하는 흔한 필터링 문제였다. 관용적이고 읽기 쉬운 코드였지만, 벤치마크를 돌리자 예상하지 못한 결과가 나왔다.
데이터양으로는 설명되지 않는 타이밍
입력은 0.0부터 100.0 사이에 고르게 분포한 100만 개의 f64 난수였고, 임계값을 조정해 전체의 1%, 25%, 50%, 75%, 99%를 남기는 경우를 각각 측정했다. criterion으로 잰 결과에서 이상한 점은 절반만 복사하는 50% 케이스가 가장 느렸다는 것이다. 데이터를 거의 두 배 더 많이 복사하는 99% 케이스가 오히려 2.6배 빨랐다. 입력의 총량은 모든 행에서 동일했고, 출력의 양으로도 이 타이밍을 설명할 수 없었다. 흔히 의심하는 collect()의 Vec 재할당을 미리 preallocate로 제거해 봤지만 50% 케이스는 3.87ms로 약 2% 개선되는 데 그쳤다. 재할당은 실재했지만 병목은 아니었다.
진짜 원인은 현대 CPU의 동작 방식에 있다. CPU는 한 번에 한 명령씩 실행하지 않고, 하나가 실행되는 동안 다음 명령들을 미리 가져오고 해독하는 깊은 파이프라인을 돌린다. 문제는 비교 결과에 따라 경로가 갈라지는 분기(branch)를 만날 때다. 비교가 끝나기 전까지 어느 쪽으로 갈지 알 수 없지만 CPU는 기다리지 않는다. 대신 분기 예측기(branch predictor)가 추측해 한쪽 경로를 앞서 실행한다. 단골의 평소 주문을 미리 만들어 두는 바리스타처럼, 예측이 맞으면 훌륭하지만 매일 무작위 주문이 들어오면 만든 음료를 계속 버리게 된다. 예측이 틀리면 CPU는 투기적으로 실행한 모든 것을 폐기하고 파이프라인을 비운 뒤 분기점부터 다시 시작하는데, 전형적인 x86 코어에서 이 비용은 약 15~20 사이클이다. 비교 연산 자체는 1 사이클 남짓이다.
범인은 분기가 아니라 예측 불가능성
핵심은 분기 자체가 아니라 예측할 수 없는 데이터에 의존하는 분기라는 점이다. 이를 확인하려고 저자는 코드와 임계값을 그대로 둔 채 입력 순서만 바꿨다. 측정 구간 바깥에서 데이터를 정렬한 뒤 50% 케이스를 다시 돌리자 같은 함수, 같은 100만 개의 부동소수점인데도 4.5배 빨라졌다. 정렬된 데이터에서는 앞쪽 절반은 전부 "버림", 뒤쪽 절반은 전부 "유지"라는 패턴이라 가장 단순한 예측기조차 한 번의 실패 후 학습한다. "정렬된 배열이 정렬되지 않은 배열보다 빠르게 처리되는 이유"를 묻는 Stack Overflow 질문이 2만 7천 표를 받은 것도 정확히 이 효과 때문이다. 물론 정렬은 해법이 아니다. 정렬 비용이 필터링보다 훨씬 크고, 대개 원래 순서를 유지해야 하기 때문이다. 다만 무엇을 고쳐야 하는지가 분명해졌다.
분기 없는(branchless) 프로그래밍의 발상은 예측할 수 없는 분기를 아예 제거해 추측할 대상 자체를 없애는 것이다. 원소를 쓸지 말지를 결정하는 대신, 항상 쓰되 비교 결과로 다음 원소가 놓일 위치를 정한다. 비교는 여전히 남아 있지만 그 결과가 프로그램의 진행 방향을 가르는 결정이 아니라 하나의 숫자로 쓰인다. 컴파일러 용어로는 제어 의존성을 데이터 의존성으로 바꾼 것이다. 실제 생성된 어셈블리에서 비교는 0이나 1을 만들어내는 seta 명령이 되고, 갈림길이 사라지므로 잘못 예측할 것도 없어진다. 물론 out[n] = x에는 경계 검사가, 루프 조건에도 분기가 남지만 이것들은 100만 번 내내 같은 방향으로 가기 때문에 예측기가 공짜로 처리한다. 사라져야 할 것은 예측 불가능한 그 분기 하나뿐이었다.
최선의 경우를 팔아 최악의 경우를 산다
그 결과 최악의 케이스가 거의 4배 빨라졌고, 분기 없는 버전의 실행 시간은 데이터 분포에 따라 거의 변하지 않는 평탄한 곡선을 그렸다. 다만 대가가 있다. 1%만 남기는 경우에는 오히려 관용적인 버전이 이긴다. 거의 항상 맞는 예측은 사실상 공짜인 반면, 분기 없는 버전은 언제나 100만 번의 쓰기를 치러야 하기 때문이다. 즉 분기 없는 코드가 일반적으로 더 빠른 것이 아니라, 최선의 경우를 내주고 최악의 경우를 사는 거래를 하는 것이다.
실무자 입장에서 이 기법의 교훈은 성능 상수 자체보다 판단 기준에 있다. 분기 없는 코드는 읽기 어렵고 실수하기 쉬우며, 컴파일러도 이미 상당 부분 비슷한 최적화를 대신 해준다. 그래서 대부분의 상황에서는 손대지 않는 편이 낫다. 이 기법이 크게 보상하는 조건은 명확하다. 프로파일러가 특정 뜨거운 루프를 지목하고, 그 루프가 예측 불가능한 데이터에 의존하는 분기를 품고 있을 때다. 반대로 말하면 최적화에 앞서 병목이 재할당인지, 출력량인지, 아니면 분기 예측 실패인지부터 측정으로 갈라내야 한다는 뜻이다. 이 사례에서 재할당 제거가 2%에 그친 반면 분기 제거가 4배를 만든 것처럼, 짐작으로 고른 최적화는 진짜 병목을 비켜가기 쉽다.