GitHub는 대소문자 접기, 즉 Case Folding을 단일 코어에서 초당 45기가바이트를 넘는 속도로 실행할 수 있게 되었습니다. 이는 첫 번째 비ASCII 바이트에서 멈추는 대신 데이터에 의존하는 제어 분기 없이 버퍼 전체를 스캔하도록 소프트웨어 루프를 재설계한 결과입니다. 회사는 1억 8,000만 개가 넘는 저장소와 480테라바이트 이상의 소스 코드를 색인하는 코드 검색 엔진 Blackbird에서 이 작업을 사용합니다.
Alexander Neubeck과 Greg Orzell은 2026년 7월 31일 GitHub 블로그에 게시된 글에서 이 설계의 세부 사항을 소개했습니다. 이 글에서는 그 결과물을 casefold라는 이름의 오픈 소스 Rust 라이브러리로 공개했다고도 밝혔습니다.
대소문자 접기는 단순히 소문자로 변환하는 것이 아니다
검색 엔진과 텍스트를 일치시키는 도구는 대소문자가 다른 문자열을 비교할 때 동일하게 만들 수 있는 표준 표현이 필요합니다. 이는 검색, 대소문자를 구분하지 않는 정규 표현식, 사용자 이름과 호스트 이름에서 나타납니다.
그러나 텍스트를 소문자로 변환하는 것만으로는 같은 목적을 달성할 수 없습니다. 소문자 변환은 언어와 문맥에 의존할 수 있습니다. 예를 들어 그리스 문자 시그마는 단어의 끝과 내부에서 형태가 다르며, 튀르키예어의 I 문자에도 다른 규칙이 적용됩니다. 반면 대소문자 접기는 비교를 위해 설계되었으므로 언어와 문맥에 독립적입니다. 또한 독일어 문자 ß, 튀르키예어 문자 İ, 그리스어의 종성 시그마와 같은 경우에도 결과가 서로 다릅니다.
이 라이브러리는 Unicode 문자 데이터베이스에 속한 CaseFolding.txt 파일의 C 및 S 상태에 따라 단순한 일대일 접기만 수행합니다. ß를 ss로 변환하는 것과 같은 다중 문자 접기나 튀르키예어 전용 접기 작업은 수행하지 않습니다.
루프를 느리게 하던 최적화 제거
소스 코드는 대부분 ASCII 문자로 구성되므로 가장 빠른 경로는 A부터 Z까지의 라틴 대문자를 소문자로 변환하는 데 집중합니다. 직관적인 설계는 ASCII가 아닌 바이트를 발견하면 즉시 중단한 뒤 나머지 텍스트를 Unicode 경로로 넘기는 방식이었습니다. 그러나 Apple M4 프로세서에서 실시한 테스트 결과, 이 방식은 초당 약 3기가바이트를 넘지 못했습니다.
주된 원인은 루프 내부의 제어 분기였습니다. 각 바이트를 검사하고 조기에 중단하는 대신, 알고리즘은 모든 바이트의 최상위 비트를 하나의 변수에 모은 다음 스캔이 끝난 뒤 결과를 검사합니다. 바이트가 대문자 범위에 속하는지 확인하는 작업은 문자 A를 뺀 뒤 래핑하고 결과를 숫자 26과 비교하는 방식으로 계산합니다. 그런 다음 계산 마스크를 사용해 바이트의 다섯 번째 비트를 설정합니다. 이로써 분기나 조건부 쓰기 없이 대문자를 소문자로 변환할 수 있습니다.
이 구조를 통해 LLVM 컴파일러는 Apple M4의 NEON을 사용해 한 번에 16바이트를 처리하는 벡터 명령을 생성할 수 있습니다. 그 결과는 초당 45기가바이트를 넘어서며, 메모리 대역폭 한계에 가까워집니다. GitHub의 측정에 따르면 조기 종료를 제거한 것이 벡터화를 가능하게 한 요인입니다. 데이터에 기반한 종료를 유지하면 루프의 나머지 부분이 분기 없이 구성되더라도 벡터 명령이 생성되지 않습니다.
통합 스캔이 항상 더 빠르지 않은 이유
GitHub는 블록 단위로 ASCII를 검사한 뒤 ASCII 접두부를 변환하는 절충안을 테스트했습니다. 이 방식은 데이터를 두 번 읽지만 초당 약 23기가바이트를 달성했습니다. 이는 순진한 루프보다 훨씬 빠르면서도 첫 번째 비ASCII 블록에서 중단할 수 있는 능력을 유지합니다.
반면 16바이트 블록을 처리하는 하나의 루프에서 검사와 변환을 통합하는 방식은 더 느렸으며, 속도는 초당 약 8.7기가바이트로 두 번 순회하는 방식의 초당 23기가바이트에 미치지 못했습니다. 게시글에 따르면 각 블록 뒤에 있는 조기 종료 분기 때문에 컴파일러가 루프를 풀거나 읽기, 검사, 변환, 쓰기 사이의 대기 시간을 숨기기 어려워집니다. 따라서 데이터를 더 적게 건드리지만 콘텐츠에 의존하는 분기를 포함한 하나의 루프보다, 깔끔하고 벡터화할 수 있는 두 개의 루프가 더 뛰어났습니다.
메모리 할당 줄이기
simple_fold 함수는 String을 소유권과 함께 받으므로 내부 버퍼를 수정한 뒤 그대로 반환할 수 있습니다. 텍스트가 완전히 ASCII라면 문자를 제자리에서 변환한 뒤 동일한 메모리를 반환하므로 두 번째 버퍼나 추가 복사가 필요하지 않습니다.
ASCII가 아닌 문자가 있더라도 알고리즘은 길이나 내용이 변하는 문자에 도달할 때까지 새 버퍼를 만들지 않습니다. 게시글은 대부분의 접기 작업이 UTF-8 길이를 유지하거나 줄인다고 설명합니다. 그러나 U+023A와 U+023E는 각각 길이가 2바이트에서 3바이트로 늘어날 수 있습니다. 따라서 알고리즘은 버퍼를 점진적으로 확장하고 데이터를 다시 복사하는 대신 입력 길이의 약 1.5배에 해당하는 최대 용량을 한 번만 예약합니다.
또한 변하지 않은 바이트 묶음은 바이트 단위로 하나씩 복사하지 않고 copy_nonoverlapping을 사용해 이동합니다. CJK, Hangul, Kana, 아랍어, 히브리어, 기호와 같은 일부 비라틴 텍스트는 접기가 필요한 문자를 포함하지 않을 경우 원래 할당을 유지합니다.
바이트 공간에서 Unicode 처리
Unicode 16.0에는 1484개의 단순 접기 작업이 있지만, GitHub는 접기 가능한 문자가 64개 코드 포인트 단위의 페이지에 모여 있다는 점을 활용해 테이블을 1776바이트로 압축했습니다. 특정 문자가 접기를 필요로 하는지 확인하기 위해 알고리즘은 비트맵을 사용합니다. 해당 비트가 활성화되어 있지 않으면 UTF-8을 디코딩하거나 해시 테이블을 검색하지 않고 문자를 즉시 거부합니다.
접기 작업이 포함된 페이지 내부에서 알고리즘은 각 코드 포인트마다 별도의 레코드를 저장하는 대신 인접한 범위를 저장합니다. 범위는 시작, 끝, 단계, 차이로 설명되며, 약 1484개의 작업을 59개 페이지에 분산된 238개 범위로 줄입니다. 또한 적절한 범위를 찾기 위해 한 번에 8개의 키를 병렬로 비교합니다.
범위를 찾은 뒤에는 문자를 코드 포인트로 디코딩했다가 다시 인코딩하는 대신, 범위에 특유한 상수를 사용해 UTF-8 수준에서 두 바이트를 더하여 접힌 문자를 계산합니다. 이를 통해 켈빈 기호인 U+212A를 3바이트에서 1바이트인 k로 변환하거나, U+023A를 3바이트 문자로 변환하는 것처럼 길이 변화도 처리할 수 있습니다.
이 방식은 입력이 올바르고 정규화된 UTF-8이라는 전제를 두며, Rust의 String 및 str 타입이 이를 보장합니다. 다른 출처에서 들어오는 원시 데이터는 이러한 계산을 사용하기 전에 유효성을 검사하거나 정규화해야 합니다.
결과와 측정의 한계
일반적인 ASCII의 경우 게시글에 제시된 측정에 따르면 라이브러리의 속도는 초당 45기가바이트를 넘으며, 완전히 동일한 기능은 아닌 str::to_lowercase 함수보다 50% 이상 빠릅니다. 대부분의 문자를 접어야 하는 최악의 입력에서는 바이트 공간의 계산에 기반한 방식이 최적화된 UTF-8 디코딩 및 재인코딩 경로보다 약 2배 빨랐습니다.
GitHub는 자동 벡터화, SWAR, little-endian 바이트 순서에 따른 바이트 계산, 메모리 대역폭, 프로세서 구조에 따라 수치와 비교 비율이 달라지므로 이를 프로세서 간에 그대로 옮길 수 있는 값이 아닌 참고용 수치라고 강조합니다. 게시글은 핵심을 두 가지 원칙으로 요약합니다. 일반적인 경로는 분기 없이 끝까지 스캔하고, Unicode의 드문 경로는 문자를 디코딩하고 다시 인코딩하는 대신 바이트 공간에서 실행하는 것입니다.