조기 종료를 없애야 벡터화된다 — 메모리 속도 소스 코드 케이스 폴딩

GitHub의 코드 검색 엔진 Blackbird는 480TB 이상의 소스 코드를 인덱싱하기 전 모든 바이트에 case folding을 적용한다. 이 글은 Rust로 구현한 case folding을 메모리 대역폭 한계(45+ GiB/s)까지 끌어올린 두 가지 반직관적 최적화를 상세히 다룬다. 핵심은 루프 조기 종료(break) 제거로 LLVM 벡터화를 유도하고, UTF-8을 디코딩하지 않고 바이트 공간 산술만으로 fold를 수행하는 것이다.

핵심 포인트

루프 break를 제거하면 LLVM이 NEON 벡터 명령(41개)을 방출해 3.1 GiB/s → 45+ GiB/s로 도약한다. 분기 없는 코드만으로는 벡터화가 안 된다.
분기 없는 범위 테스트(wrapping_sub)와 bit OR 쓰기로 A–Z 소문자화를 구현하면 스칼라 경로에선 오히려 느리다. 벡터화 이후에야 이득이 생긴다.
Unicode case folding은 1,776바이트 테이블로 압축했다. 기존 라이브러리(ICU 70KB+, Go unicode 7.3KB)보다 훨씬 작고 빠르다.
1,484개 fold 매핑을 64-코드포인트 페이지 비트맵 + 238개 런으로 표현해 fold가 없는 일반 경우를 단 한 번의 비트 조회로 처리한다.
UTF-8 코드 포인트 디코딩 없이 바이트에 상수를 더하는 것만으로 fold를 수행한다. ICU, Go, Rust regex, CPython, glibc 모두 취하지 않은 독창적 접근이다.

상세 정리

case fold vs lowercase: lowercase는 표시용·locale 민감, case fold는 비교용·locale 독립적. CaseFolding.txt C·S 상태(1:1 단순 폴드)만 처리하며 ß→ss 멀티문자 fold, 튀르키예 locale fold는 제외.
최초 구현(3.1 GiB/s): non-ASCII 발견 시 break로 조기 종료. LLVM은 데이터 의존적 루프 종료를 만나면 벡터화를 포기하고 스칼라로 처리한다.
break만 제거(7.6 GiB/s): 조기 종료 없이 전체 스윕하면 LLVM이 부분 벡터화 시작. 벡터 명령 25개.
분기 없는 테스트+쓰기 추가(45+ GiB/s): wrapping_sub로 범위 체크, bit OR로 조건부 없는 소문자화. 벡터 명령 41개로 완전 벡터화. M4 기준 45 GiB/s 이상.
스칼라 vs 벡터 트레이드오프: 분기 없는 쓰기는 스칼라에서 모든 바이트에 쓰기가 발생해 오히려 느리다. 벡터화된 후에야 16바이트 벡터 쓰기 하나로 이득이 생긴다.
두 패스 방식(23 GiB/s): 표준 라이브러리처럼 is_ascii 스캔 후 변환하면 23 GiB/s지만 데이터를 두 번 읽는다. 한 패스로 합치면 8.7 GiB/s로 오히려 감소 — 16바이트마다 조기 종료 분기가 생기기 때문.
힙 할당 최소화: 순수 ASCII는 같은 버퍼를 재사용. fold 없는 비 ASCII(CJK, 한글, 아랍어 등)는 원본 그대로 반환. 길이가 늘어나는 fold(U+023A 등)는 len + len/2 + 4로 최악 경우를 커버한다.
페이지 비트맵: 코드 공간을 64-코드포인트 페이지로 나눠 1,484개 fold가 1,960개 페이지 중 59개에만 분포함을 이용. 비트가 0이면 fold 없음 확정, 세트 비트만 추가 조회.
런 인코딩: 인접 코드 포인트는 같은 delta를 공유(A–Z는 모두 +32). 238개 런으로 표현, 페이지당 평균 4개 엔트리만 검색.
SWAR 비교: 8개 end_low 바이트를 u64에 로드해 레지스터 내 SIMD로 병렬 비교. 0x8080... 마스크로 >= 조건을 브랜치 없이 판단한다.
바이트 공간 fold: 리틀 엔디언 머신에서 fold된 UTF-8 바이트 = 원본 바이트 + 런별 BYTE_DELTA 상수. UTF-8 디코딩·인코딩을 건너뜀. 테이블 총 1,776바이트.
성능 비교: 순수 ASCII에서 simd_normalizer 대비 37배, HashMap 방식 대비 216배 빠름. 최악 케이스(전부 fold)에서도 경쟁자와 대등하거나 앞선다.
오픈소스: casefold 크레이트(crates.io)로 공개.

왜 읽나Rust로 고성능 텍스트 처리를 구현하는 엔지니어에게 SIMD 벡터화를 이끌어내는 루프 패턴, UTF-8 바이트 공간 처리 기법, 컴팩트 Unicode 테이블 설계의 실전 레퍼런스다.

GitHub Engineering 블로그

원문은 여기서 이어서 읽을 수 있어요

원문 읽기

읽음 (0)

·takedown 요청

조기 종료를 없애야 벡터화된다 — 메모리 속도 소스 코드 케이스 폴딩

이 글과 비슷한

Cursor와 GitLab으로 Java 현대화하기

트랜잭션 스크립트에서 숙소 메타 + 가격 계산 모듈로 — 전시 아키텍처 개선기 (2/3)

Chat SDK에 X(Twitter) 어댑터 지원 추가