GitHub, 조기 종료 분기 하나 없애 코드 검색 대소문자 변환을 3.1→45 GiB/s로 가속

일찍 멈추는 최적화가 만든 병목

GitHub의 코드 검색 엔진 Blackbird는 1억8천만 개가 넘는 저장소, 480TB 이상의 소스 코드를 색인한다. 검색어와 코드의 대소문자를 일관되게 비교하려면 모든 바이트에 대소문자 접기(case folding)를 적용해야 한다. 작은 문자열 함수의 비용도 이 규모에서는 검색 인프라 전체의 처리량을 좌우한다.

“GitHub case-folds every byte of code search at over 45 GiB/s on one core. The biggest win came from removing an early-exit branch, not adding one.”

GitHub의 원문 트윗은 단일 코어에서 45 GiB/s를 넘긴 핵심이 조건을 더 넣는 대신 조기 종료 분기를 제거한 데 있다고 요약했다. GitHub 공식 계정은 제품 변경뿐 아니라 대규모 코드 검색과 저장소 운영에서 얻은 엔지니어링 결과도 공유한다. 이번 결과는 구현과 벤치마크, 공개 Rust 크레이트까지 연결된다.

3.1에서 45 GiB/s 이상으로

기술 글의 Apple M4, 5.7KB ASCII 버퍼 실험에서 순진한 구현은 3.1 GiB/s였다. 비ASCII 바이트를 만나면 멈추는 분기가 데이터 의존적 종료 조건을 만들어 LLVM의 자동 벡터화를 막았다. 분기를 유지한 채 비교와 쓰기만 무분기 방식으로 바꾸면 오히려 2.6 GiB/s로 느려졌다.

GitHub은 루프 안에서 모든 바이트의 최상위 비트를 OR 누산하고, 대문자 범위 검사를 산술식으로 바꾸며, 조건부 쓰기를 비트 연산으로 대체했다. 조기 종료를 없애자 LLVM이 16바이트 단위 NEON 명령을 생성했다. 중간 구현은 7.6 GiB/s, 완전 벡터화된 루프는 45 GiB/s 이상을 기록했다. 두 번 읽는 표준 라이브러리형 절충안은 약 23 GiB/s였다.

비ASCII 경로도 별도로 압축됐다. Unicode 16.0의 단순 접기 1,484개를 1,776바이트 표로 표현하고, 대부분 접히지 않는 문자를 빠르게 제외한다. 결과는 casefold Rust 크레이트로 공개됐다.

다음 확인 지점

45 GiB/s는 Apple M4와 특정 버퍼에서 나온 수치이므로 x86, 다른 ARM 코어, 더 큰 버퍼에서 절대값과 비율이 달라질 수 있다. 실제 Blackbird 배포에서 CPU 시간과 색인 지연이 얼마나 줄었는지, 단순 접기가 지원하지 않는 다문자·터키어 접기 요구를 어떻게 처리하는지도 봐야 한다. 교훈은 무분기 코드 자체가 아니라, 컴파일러가 전체 루프를 벡터화할 수 있는 형태인지 측정으로 확인하라는 데 있다.