clz(count leading zeros)와 ctz(count trailing zeros)는 고정 크기 정수에서 앞쪽 또는 뒤쪽에 연속으로 나타나는 0비트의 개수를 세는 연산이다. 압축, 비트셋 순회, 부동소수점 정규화 같은 저수준 작업에서 자주 등장하며, 현대 CPU는 이를 전용 명령어로 지원한다. 문제는 '지원'과 '빠름'이 같은 말이 아니라는 점이다. 예를 들어 인텔 Arrow Lake에서 tzcnt는 지연시간(latency)이 3사이클에 달한다. 한 개발자가 FPU 에뮬레이터를 작성하던 중 ctz를 피하려다 부동소수점 트릭을 고안했고, 이것이 벡터화 가능한 ctz 대체 구현으로 일반화된다는 사실을 정리한 글을 살펴본다.
지수가 곧 로그라는 발상
핵심 아이디어는 부동소수점 수의 지수 필드가 값의 '편향된 로그'라는 성질을 이용하는 것이다. clz부터 보면, 32비트 정수 x를 어떤 값 2^k의 가수(mantissa) 자리에 끼워 넣으면 2^k(1+2^-52·x)를 나타내는 double이 만들어진다. 여기서 2^k를 double 연산으로 빼면 2^(k-52)·x가 남고, 이 결과의 지수를 추출하면 k-52+31-clz(x) 형태가 된다. 즉 지수에서 비트 뺄셈 한 번으로 clz를 복원할 수 있고, k를 적절히 고르면 x=0인 경계 조건까지 정상 동작하게 만들 수 있다.
이 방식의 명백한 한계는 정밀도다. 32비트 입력을 다루려면 64비트 double이 필요하며, 그래서 임의의 64비트 입력에는 쓸 수 없고 52비트까지만 유효하다. 가수가 52비트이기 때문이다. 바꿔 말하면 이 기법은 '32비트 값을 네 개씩 묶어 u64x4 벡터로 처리'하는 시나리오에 딱 맞게 재단되어 있다.
측정된 성능과 CPU별 차이
저자의 Haswell에서 벡터화 clz는 반복당 0.45ns로, 스칼라 버전의 1ns보다 빨랐다. 다만 지연시간에 묶이는 상황에서는 2ns 대 1ns로 역전된다. 이는 처리량(throughput) 최적화와 지연시간 최적화가 다른 목표라는 점을 보여준다. 한 제보자가 Alder Lake에서 측정한 값은 0.29ns 대 0.85ns, 지연시간 기준으로는 1.3ns 대 0.85ns였다. 실무적으로 중요한 단서가 하나 붙는다. 벡터화된 비트 카운트에서 지연시간에 묶여 있다면 애초에 설계가 잘못됐을 가능성이 크다는 것이다. 벡터화의 이점은 처리량에서 나오기 때문이다.
AMD 계열에서는 결론이 달라진다. Zen CPU는 lzcnt가 워낙 저렴해서 스칼라 버전이 오히려 이기기 쉽다. 또한 Zen은 AVX-512를 지원하므로 벡터 명령인 vplzcntd를 그대로 쓰는 선택지도 있다. 즉 이 트릭은 '하드웨어 명령이 느린 특정 환경'을 겨냥한 최적화이지 만능 처방이 아니다.
ctz와 세 가지 접근
ctz는 조금 더 손이 간다. 먼저 x⊕(x-1)로 최하위 셋 비트만 남긴 뒤, 그 값의 로그를 같은 부동소수점 기법으로 구한다. 여기서 까다로운 건 경계 처리다. x=0을 올바르게 다루기 위해 가수에 2^32를 미리 섞어 넣고 x-1 대신 x+2^32-1을 쓰며, 홀수 입력이 느린 비정규화(subnormal) 수를 만들지 않도록 가수에 1을 추가로 섞는다. 저자가 '이걸 맞추느라 얼마나 시간을 썼는지 상상이 가느냐'고 토로할 만큼 세부 조정이 많은 작업이다. 성능은 Haswell에서 0.49ns, Alder Lake에서 0.35ns로 clz보다 명령어 하나만큼 느리다.
대안으로 de Bruijn 수열 기반 방식도 제시된다. 다만 vpshufb가 16바이트 레인을 넘어 참조하지 못하기 때문에 진짜 32바이트 룩업 테이블은 쓸 수 없다. 그래서 16비트 de Bruijn 수열을 두 번 반복해 ctz의 하위 4비트를 구하고, 어느 절반이 0인지에 따라 16이나 32를 더하는 우회로를 택한다. 이를 성립시키는 매직 상수 0xf0a6f0a7은 가능한 네 개 중 하나다. 속도는 Haswell에서 1ns로 FP 방식보다 느려 보이지만 처리량이 두 배라, 셔플 연산을 줄여야 하는 상황에서는 더 유리할 수 있다.
64비트 입력에는 또 다른 전용 알고리즘이 쓰인다. (x-1)&~x의 각 바이트를 두 니블로 나눠 반전된 popcount를 구한 뒤, vpsadbw로 수평 합산과 반전 보정을 한 번에 처리하는 방식이다. ctz(0)=64를 정확히 반환하며 Haswell에서 0.63ns가 나온다. 그러나 vpsadbw가 정확히 8바이트 단위로만 수평 합산하는 탓에 이 알고리즘은 64비트에 특화되어 32비트에는 쓸 수 없다. 32비트 시나리오에서는 여전히 de Bruijn 방식이 가장 빠르다.
정리하면, 이 작업이 주는 실무적 교훈은 '하드웨어 명령이 있다고 항상 최선은 아니다'라는 것이다. 특정 마이크로아키텍처에서 tzcnt·lzcnt의 지연시간이 발목을 잡고, 데이터를 벡터로 묶어 처리할 수 있는 핫루프라면, 부동소수점 지수를 로그처럼 활용하거나 de Bruijn 테이블을 쓰는 폴리필이 유의미한 이득을 낸다. 반대로 AMD처럼 네이티브 명령이 저렴하거나 벡터화 여지가 없는 코드라면 평범한 스칼라 명령이 정답이다. 적용 전에 대상 CPU에서 처리량 기준과 지연시간 기준 양쪽을 반드시 직접 측정해야 한다는 점도 잊지 말아야 한다.