일찍 멈추지 마라: 메모리 속도로 소스 코드의 대소문자를 정규화하기
GitHub는 코드 검색 엔진 Blackbird에서 대규모로 수행되는 유니코드 케이스 폴딩을 메모리 대역폭에 가까운 속도로 최적화했다. 핵심은 비ASCII 문자를 만나면 즉시 중단하는 기존 최적화를 제거하고, 전체 버퍼를 분기 없이 처리해 컴파일러의 SIMD 벡터화를 유도한 것이다. Apple M4에서 단순 구현의 약 3.1GiB/s 처리량을 45GiB/s 이상으로 끌어올렸으며, 분기 없는 코드는 벡터화를 가능하게 할 때만 이점이 있다는 점도 확인했다. ## 케이스 폴딩과 소문자 변환의 차이 - 케이스 폴딩은 표시를 위한 변환이 아니라 문자열 비교를 위한 정규화다. - 대소문자만 다른 문자열을 동일하게 취급하기 위해 사용된다. - 검색 엔진 - 정규식의 `(?i)` 옵션 - 대소문자를 구분하지 않는 사용자명과 호스트명 - 일반적인 소문자 변환과 달리 케이스 폴딩은: - 로케일에 독립적이다. - 문맥에 의존하지 않는다. - 비교 관계가 일관되고 대칭적이다. - 그리스어 final sigma, 터키어의 `I`, 독일어 `ß`처럼 소문자 변환과 케이스 폴딩 결과가 달라지는 문자가 있어 `to_lowercase`를 대체 수단으로 사용하면 잘못된 검색 결과가 발생할 수 있다. - 공개된 Rust `casefold` 크레이트는 Unicode `CaseFolding.txt`의 단일 문자 변환인 C·S 상태만 구현한다. - `ß → ss`와 같은 다중 문자 변환은 지원하지 않는다. - 터키어 전용 폴딩도 지원하지 않는다. - ripgrep과 정규식 엔진도 유사한 제한을 둔다. ## GitHub에서 케이스 폴딩이 중요한 이유 - Blackbird는 1억 8천만 개 이상의 저장소와 480TB가 넘는 소스 코드를 색인한다. - 색인 전에 모든 바이트를 폴딩하고, 검색 결과 후보를 확인할 때도 케이스 폴딩이 반복적으로 수행된다. - 소스 코드는 대부분 ASCII이므로 ASCII 경로를 메모리 속도로 처리하는 것이 가장 큰 성능 개선 요소다. - 비ASCII 입력은 드물기 때문에, 최적화의 목표는: - 흔한 ASCII 경로를 최대한 빠르게 만들고 - 드문 유니코드 경로가 ASCII 성능을 방해하지 않게 하는 것이다. ## 조기 종료를 제거한 ASCII 처리 기존 방식은 비ASCII 바이트를 만나면 즉시 반복문을 종료하고 유니코드 처리로 넘겼다. ```text if byte >= 0x80 { break } ``` 하지만 이 데이터 의존적 `break`는 컴파일러의 루프 벡터화를 막는다. 개선된 구현은 다음과 같이 동작한다. - 모든 바이트를 끝까지 순회한다. - `high_bit_acc |= byte`로 모든 바이트의 최상위 비트를 누적한다. - 반복문이 끝난 뒤 누적값을 한 번만 검사해 비ASCII 문자가 있었는지 확인한다. - 따라서 반복문 내부에는 데이터에 따른 분기나 조기 종료가 없다. 이 방식은 비ASCII 여부를 동일하게 알아내면서도 SIMD 명령을 사용할 수 있게 한다. ## 분기 없는 ASCII 대소문자 변환 ASCII 대문자 변환도 조건문 대신 산술 연산으로 처리한다. - `b.wrapping_sub(b'A') < 26` - 바이트가 `A`부터 `Z` 사이일 때만 참이 된다. - 별도의 분기 없이 대문자 여부를 0 또는 1 마스크로 만든다. - `u8::from(is_upper) << 5` - 대문자이면 ASCII의 비트 5를 설정해 소문자로 바꾼다. - 그 외 문자는 아무 변화가 없다. - 모든 바이트를 항상 저장하므로 조건부 저장 명령도 제거된다. 결과적으로 루프는 다음 특성을 갖는다. - 데이터 의존적 분기 없음 - 조기 종료 없음 - 연속적인 메모리 접근 - LLVM이 NEON 기반 16바이트 단위 SIMD 코드 생성 가능 ## 벤치마크와 성능 개선 Apple M4에서 5.7KB ASCII 버퍼를 처리한 누적 측정 결과는 다음과 같다. - 조기 종료와 분기 조건을 사용하는 순진한 구현: **3.1GiB/s** - 본문만 분기 없이 바꾸고 조기 종료를 유지한 구현: **2.6GiB/s** - 조기 종료를 제거한 구현: **7.6GiB/s** - 대문자 판별과 저장까지 분기 없이 처리한 최종 구현: **45GiB/s 이상** 성능 향상의 핵심은 단순히 분기를 없앤 것이 아니다. - 조기 종료 제거가 루프 벡터화를 가능하게 했다. - 대문자 변환의 분기 제거가 완전한 벡터화를 가능하게 했다. - 최종 성능은 사실상 메모리 대역폭 한계에 도달했다. ## 스칼라 코드에서는 분기 없는 방식이 느릴 수 있다 - 조기 종료를 유지한 채 본문만 분기 없이 바꾼 구현은 오히려 3.1GiB/s에서 2.6GiB/s로 느려졌다. - 기존 분기 방식은 실제로 값이 바뀌는 대문자일 때만 저장한다. - 소문자, 숫자, 공백이 대부분인 일반 텍스트에서는 조건부 저장 분기가 매우 잘 예측된다. - 반면 분기 없는 구현은 모든 바이트를 무조건 저장해 불필요한 쓰기 트래픽이 발생한다. - 따라서 분기 없는 코드는 그 자체로 항상 빠른 것이 아니다. - 이 사례에서는 분기 없는 코드가 SIMD 벡터화를 가능하게 하는 수단이었기 때문에 최종적으로 큰 이득을 냈다. 실용적으로는 데이터 규모가 크고 반복 횟수가 많은 바이트 처리에서 조기 종료가 정말 최적인지 확인해야 한다. 특히 루프의 조기 종료가 SIMD 벡터화를 막는다면, 전체 버퍼를 일정한 흐름으로 처리하고 마지막에 상태를 확인하는 방식이 훨씬 빠를 수 있다.
원문 읽기(새 탭에서 열림)
