조기 종료하지 마라: 메모리 속도로 소스 코드 case folding하기

GitHub의 코드 검색 엔진 Blackbird는 1억 8,000만 개가 넘는 저장소와 480TB 이상의 소스 코드를 처리한다. 모든 바이트를 ngram 추출과 인덱싱 전에 case folding하고, 검색 결과를 찾는 과정에서도 같은 작업을 반복하기 때문에 기본 연산의 속도가 중요하다.

case folding은 표시를 위한 lowercasing과 다르다. locale과 문맥에 의존하지 않고 문자열 비교를 안정적으로 수행하기 위한 정규화 방식이며, Unicode의 CaseFolding.txt에 정의돼 있다. ß, 튀르키예어의 İ, 그리스어 final sigma처럼 두 연산의 결과가 달라지는 문자 때문에 단순히 lowercasing을 사용하면 잘못된 매칭이 발생할 수 있다.

공개된 Rust crate casefold는 CaseFolding.txt의 C·S 상태에 해당하는 단순한 1:1 folding만 구현한다. 따라서 ß → ss 같은 다중 문자 변환과 Turkic locale용 folding은 지원하지 않으며, ripgrep과 같은 도구와의 일관성을 택했다.

소스 코드 대부분이 ASCII라는 점을 활용해, 핵심 최적화는 의외로 조기 종료를 제거하는 데서 나왔다. 비ASCII 바이트를 만나는 즉시 중단하는 기존 방식은 Apple M4에서 약 3GiB/s에 그쳤고, 분기 비용 때문에 최적 수준보다 15배 이상 느렸다.

개선된 루프는 다음과 같은 방식으로 데이터 의존적 분기를 없앴다.

• 모든 바이트를 끝까지 순회하고 high_bit_acc에 OR 연산해 비ASCII 여부를 한 번만 확인한다.
• A..=Z 판별을 wrapping_sub(b'A') < 26이라는 산술 연산으로 바꾼다.
• 대문자 여부를 마스크로 변환한 뒤 bit 5를 설정해 조건부 쓰기 없이 소문자로 변환한다.

이 branchless 루프는 ASCII 입력을 별도 버퍼 없이 제자리에서 folding하며, 전체 순회가 끝난 뒤 비ASCII가 없으면 즉시 결과를 반환한다. 드문 비ASCII 입력만 이후 Unicode 경로로 넘겨 ASCII 처리 성능을 메모리 대역폭 수준에 가깝게 유지한다.