GitHub 엔지니어링 블로그에 흥미로운 최적화 이야기가 올라왔어요. 주제는 케이스 폴딩(case folding)인데요. 이게 뭐냐면, 대소문자를 구분하지 않고 텍스트를 비교하기 위해 문자를 하나의 기준 형태(보통 소문자)로 통일하는 작업이에요. 예를 들어 "Hello"와 "HELLO"를 같은 단어로 취급하려면 둘 다 "hello"로 바꿔서 비교하면 되거든요. 코드 검색에서 대소문자 무시 옵션을 켜면 뒤에서 바로 이 작업이 일어나고 있는 거죠.
문제는 규모예요. GitHub의 코드 검색은 수억 개 저장소, 수십억 개 파일을 인덱싱하는데, 이 모든 소스코드를 케이스 폴딩해야 하니까 변환 속도가 조금만 느려도 전체 인덱싱 파이프라인이 병목에 걸려요. 그래서 목표가 "메모리 속도", 그러니까 CPU가 RAM에서 데이터를 읽어오는 속도 자체가 한계가 될 때까지 변환 로직을 최적화하는 거였어요. 연산이 아니라 데이터를 실어 나르는 속도가 병목이 되는 지점, 이게 이런 종류의 최적화에서 도달할 수 있는 이론적인 끝판왕이거든요.
"일찍 멈추지 마라"는 역설
글 제목이 재미있어요. Don't stop early, 일찍 멈추지 말라는 건데요. 보통 우리는 최적화를 생각할 때 "불필요한 일을 건너뛰자"고 배우잖아요. 예를 들어 "이 문자열이 이미 전부 소문자면 변환을 건너뛰자", "ASCII가 아닌 문자를 만나면 그때만 복잡한 유니코드 처리를 하자" 같은 조기 종료(early exit) 검사를 넣는 거죠. 직관적으로는 일을 덜 하니까 빨라질 것 같은데요.
그런데 현대 CPU에서는 이런 "검사 후 분기" 패턴이 오히려 독이 될 수 있어요. 이유는 분기 예측(branch prediction) 때문인데요. CPU는 명령어를 미리 줄 세워서 실행하는데, if문을 만나면 어느 쪽으로 갈지 예측하고 미리 실행해버려요. 예측이 맞으면 공짜지만, 틀리면 미리 해둔 작업을 전부 버리고 다시 시작해야 해서 수십 사이클을 날리게 되거든요. 소스코드처럼 대문자와 소문자가 불규칙하게 섞인 데이터에서는 "이 문자가 대문자인가?" 같은 분기의 예측이 계속 빗나가요. 그래서 조건 검사를 아예 없애고 모든 바이트를 조건 없이 똑같은 연산으로 처리하는 브랜치리스(branchless) 방식이 오히려 빠른 거예요.
여기에 SIMD가 더해져요. SIMD는 Single Instruction, Multiple Data의 약자로, 한 번의 CPU 명령으로 16바이트, 32바이트, 64바이트를 동시에 처리하는 기술이에요. 문자를 하나씩 소문자로 바꾸는 대신, 32개 문자를 한꺼번에 벡터 레지스터에 올려놓고 "이 중 대문자인 것들만 골라 값을 더해라"를 명령 몇 개로 끝내버리는 거죠. 조기 종료 검사를 넣으면 이렇게 한 덩어리로 밀어붙이는 흐름이 끊기기 때문에, "확인하고 건너뛰기"보다 "무조건 다 처리하기"가 이기는 구조가 만들어져요.
유니코드라는 복병
물론 세상이 ASCII로만 이루어져 있다면 이야기가 간단한데요. 실제 소스코드의 주석이나 문자열에는 한글, 일본어, 이모지, 독일어 움라우트 같은 온갖 문자가 들어 있어요. 유니코드 케이스 폴딩은 단순히 일정한 값을 더하는 수준이 아니라, 독일어 ß가 "ss" 두 글자로 바뀌는 것처럼 글자 수 자체가 변하는 경우도 있고, 터키어의 점 없는 ı처럼 언어별 규칙이 얽힌 경우도 있거든요. 그래서 실전에서는 "대부분의 데이터는 ASCII"라는 사실을 이용해 ASCII 구간은 SIMD로 고속 처리하고, 비ASCII 문자가 섞인 블록만 정확한 유니코드 처리 경로로 넘기는 이중 구조를 짜요. 핵심은 이 판별조차 바이트 단위 분기가 아니라 블록 단위로 뭉텅뭉텅 처리한다는 점이에요.
우리에게 주는 교훈
이 글이 좋은 이유는 GitHub 규모가 아니어도 써먹을 교훈이 있어서예요. 첫째, "일을 덜 하는 최적화"가 항상 이기는 게 아니라는 것. 예측 불가능한 분기 하나가 단순 연산 수십 개보다 비쌀 수 있어요. 둘째, 최적화의 목표를 메모리 대역폭이라는 물리적 한계로 잡으면 얼마나 더 짜낼 수 있는지 객관적으로 알 수 있다는 것. 내 코드가 초당 1GB를 처리하는데 메모리는 초당 수십 GB를 공급할 수 있다면 아직 갈 길이 멀다는 뜻이거든요. 셋째, 이런 저수준 최적화가 Rust나 C++만의 전유물이 아니라는 것. Go나 Java, C#에도 벡터 연산 API가 있고, 표준 라이브러리의 소문자 변환 함수들이 내부적으로 이런 기법을 쓰는 경우가 많아요. 핫패스에서 문자열을 대량으로 다룬다면 프로파일링해볼 가치가 충분해요.
정리하면, "확인하고 건너뛰기"보다 "무조건 밀어붙이기"가 빠를 수 있는 게 현대 CPU의 세계라는 이야기였어요. 여러분은 실무에서 분기 제거나 SIMD로 성능을 끌어올려 본 경험이 있나요? 어떤 상황에서 효과를 봤는지 궁금하네요.
🔗 출처: Hacker News