무슨 이야기인가요
로우레벨 성능 이야기를 자주 다루는 purplesyringa 블로그에 '벡터화된 CLZ와 CTZ'라는 글이 올라왔어요. 제목만 보면 아주 좁은 주제 같지만, 압축, 직렬화, 파서, 해시 테이블처럼 성능이 중요한 코드 깊숙한 곳에서 자주 쓰이는 연산이라 한 번 이해해 두면 두고두고 써먹을 수 있어요. 원문을 읽기 전에 알아두면 좋은 배경과 대표적인 기법들을 정리해볼게요.
CLZ, CTZ가 뭐냐면
- CLZ(Count Leading Zeros): 숫자를 2진수로 썼을 때 맨 앞(최상위 비트)부터 0이 몇 개 연속되는지 세는 연산이에요.
- CTZ(Count Trailing Zeros): 반대로 맨 뒤(최하위 비트)부터 0이 몇 개 연속되는지 세요.
- 컴파일러 출력을 직접 보세요. Compiler Explorer(godbolt.org)에서
leading_zeros()를 루프로 돌리는 코드를-mavx2와-mavx512cd로 각각 컴파일해 보면 같은 코드가 얼마나 다른 어셈블리가 되는지 바로 보여요. - 배포 환경의 CPU를 확인하세요. 클라우드 인스턴스 세대나 ARM(Graviton 등) 여부에 따라 쓸 수 있는 명령어가 달라요. 런타임에 CPU를 감지해 경로를 나누는 '디스패치'가 실무에선 사실상 필수예요.
- 비트 트릭은 손에 익혀두세요.
x & -x,x & (x - 1)같은 패턴은 알고리즘 문제에도 자주 나오니 이번 기회에 정리해두면 좋아요.
예를 들어 32비트 정수 12는 2진수로 ...00001100이에요. 앞쪽에 0이 28개라 CLZ는 28, 뒤쪽에 0이 2개라 CTZ는 2예요.
이게 왜 쓸모 있냐면, 32 - CLZ(x)가 곧 x를 표현하는 데 필요한 비트 수거든요. 그래서 protobuf의 varint 같은 가변 길이 정수 인코딩, 압축의 비트 패킹, 정수 log2 계산에 쓰여요. CTZ는 '가장 낮은 위치의 1이 어디 있나'를 알려줘서 비트셋 순회나, SIMD 비교 결과 마스크에서 첫 번째 일치 위치를 찾을 때 쓰여요. 구글의 SwissTable 해시 테이블이 바로 이 방식을 써요.
값 하나씩 처리하는 스칼라 버전은 이미 쉬워요. x86에는 LZCNT, TZCNT 명령어가 있고, C++20의 std::countl_zero나 Rust의 leading_zeros()가 이걸 한 줄로 불러줘요.
문제는 '한꺼번에' 할 때예요
SIMD는 명령어 하나로 여러 값을 동시에 처리하는 기술이에요. 128비트 레지스터에 32비트 정수 4개, 혹은 8비트 정수 16개를 넣고 한 번에 더하는 식이죠. 덧셈, 비교 같은 기본 연산은 대부분 SIMD 버전이 있어요.
그런데 CLZ/CTZ는 사정이 달라요. x86의 벡터 CLZ 명령어(VPLZCNTD/Q)는 AVX-512의 CD 확장에만 있고, 그마저 32·64비트 단위만 지원해요. 8·16비트 단위는 없고, 벡터 CTZ는 아예 전용 명령어가 없어요. AVX2까지만 되는 CPU도 여전히 많으니, 결국 없는 명령어를 다른 명령어 조합으로 흉내 내는 기술이 필요해져요.
대표적인 우회 기법들
1. 부동소수점 변환 트릭
정수를 float로 바꾸면 CPU가 알아서 '최상위 1비트의 위치'를 지수(exponent) 필드에 적어줘요. 그 지수만 꺼내면 CLZ를 역산할 수 있죠. 정수→실수 변환은 SIMD로 빠르니 꽤 효율적인데, 함정이 있어요. float의 가수부는 24비트라 큰 수는 반올림되고, 이때 지수가 하나 올라가 버릴 수 있거든요. 그래서 x & ~(x >> 1)처럼 최상위 비트 바로 아래 비트를 0으로 만들어 올림을 막는 보정이 필요하고, 0과 부호 비트도 따로 챙겨야 해요.
2. 니블 룩업 테이블(pshufb)
8비트 단위라면 SSSE3의 pshufb(16칸짜리 표에서 값을 꺼내오는 명령어)를 쓸 수 있어요. 바이트를 4비트씩 두 조각(니블)으로 나눠서, 상위 니블이 0이 아니면 표에서 바로 답을 찾고, 0이면 4에 하위 니블의 답을 더하는 방식이에요. 표 조회 두 번과 비교·선택 몇 번이면 16바이트를 한 번에 처리해요.
3. CTZ를 다른 연산으로 바꾸기
x & -x는 최하위 1비트만 남기는 유명한 트릭인데, 여기에 CLZ를 쓰면 CTZ(x) = 31 - CLZ(x & -x)가 돼요(0은 별도 처리). 또 ~x & (x - 1)은 '뒤쪽 0들'만 1로 바꿔주니까, 여기에 1의 개수 세기(popcount)를 하면 바로 CTZ가 나와요. 이 경우 x가 0이면 자연스럽게 32가 되고요. 비트 순서를 뒤집을 수 있다면 CTZ는 그냥 '뒤집은 값의 CLZ'이기도 해요. 최신 x86의 GFNI 확장은 바이트 내 비트 뒤집기를 명령어 하나로 해서 이 경로가 열려요.
4. ARM은 조금 더 편해요
ARM NEON에는 8·16·32비트 단위 벡터 CLZ(vclzq)가 기본으로 있고, 바이트 단위 비트 뒤집기(vrbitq_u8)도 있어요. 다만 64비트 단위 CLZ는 없어서 역시 조합이 필요하고, SVE로 가면 훨씬 넉넉해져요. 같은 알고리즘도 아키텍처마다 최적 경로가 다르다는 게 이 주제의 재미이자 고통이에요.
업계 맥락
simdjson이나 각종 base64·UTF-8 검증 라이브러리처럼 스칼라 코드를 SIMD로 갈아엎어 몇 배 빠르게 만드는 흐름은 몇 년째 이어지고 있어요. 공통점은 CPU가 대놓고 주지 않는 연산을 비트 트릭과 표 조회로 재구성한다는 거예요. 벡터 CLZ/CTZ는 그 기본 부품이라, 잘 만들어 두면 varint 일괄 인코딩이나 정수 압축 같은 상위 알고리즘이 한 단계 빨라져요.
언어 차원의 지원도 늘고 있어요. Java Vector API에는 LEADING_ZEROS_COUNT, TRAILING_ZEROS_COUNT 연산이 있고, Rust의 std::simd에도 레인별 leading_zeros()가 있어요. 다만 이런 고수준 API가 실제로 어떤 명령어로 바뀌는지는 타깃 CPU마다 천차만별이라, 위 기법들을 알아야 '이 코드가 왜 생각보다 느리지?'를 설명할 수 있어요.
한국 개발자에게 주는 시사점
마무리
한 줄 정리: CPU가 주지 않는 명령어는 비트 트릭과 표 조회로 직접 만든다 — 벡터 CLZ/CTZ는 그 기술의 좋은 교과서예요.
여러분은 실무에서 SIMD 최적화를 해보신 적 있나요? 컴파일러 자동 벡터화에 맡기는 편인지, 인트린식으로 직접 짜는 편인지, 그 판단 기준이 궁금해요.
🔗 출처: Hacker News