GCC는 어떻게 불필요한 정수 나눗셈을 제거하는가 — 매직 넘버와 역수 곱셈의 원리

본문

이 글은 'Practical Number Field Sieve for Programmers' 시리즈의 8번째 파트로, 소수 체(sieve)에서 반복적으로 수행되는 배수 판정(divisibility test)을 최적화하는 과정을 다룹니다. 저자는 GCC가 변수 제수보다 상수 제수를 받았을 때 더 빠르게 동작한다는 사실을 관찰했는데, 1억 회 반복 벤치마크에서 상수 제수 버전(ConstantMod)은 0.454초, 변수 제수 버전(VariableMod)은 0.562초가 나왔습니다. 그 원인을 어셈블리 수준에서 추적한 내용이 글의 핵심입니다.

어셈블리 비교 — div 대신 곱셈과 비교

-O2 -masm=intel로 생성한 어셈블리를 보면 두 함수의 차이가 극명합니다. 변수로 나누는 VariableMod는 div esi 명령을 그대로 호출하고 나머지(edx)가 0인지 검사합니다. 반면 x % 17 == 0을 계산하는 ConstantMod는 imul edi, edi, -252645135 한 번과 cmp edi, 252645135 비교만으로 끝납니다. 즉 x % 17 == 0이 x * 0xF0F0F0F1 <= 0x0F0F0F0F로 변환되는 것입니다. 글은 StackOverflow에 정리된 사례를 인용해 이 패턴이 보편적임을 보여줍니다 — x % 3은 x * 0xAAAAAAAB <= 0x55555555, x % 7은 x * 0xB6DB6DB7 <= 0x24924924처럼 각 제수마다 고유한 매직 넘버 쌍이 존재하며, 64비트 제수(예: 4294967291)에도 동일하게 적용됩니다.

매직 넘버의 원리 — 역수 곱셈(Reciprocal Multiplication)

이 최적화의 정식 명칭은 '역수 곱셈'입니다. 매직 넘버는 '올림한 2의 거듭제곱을 제수로 나눈 몫'을 미리 계산해 둔 값입니다. 실행 시에는 이 매직 넘버를 곱한 뒤 다시 2의 거듭제곱으로 나누어(시프트) 버림 효과를 냅니다. 수학적으로는 mexact라는 분수 형태의 정확한 역수가 존재하고, 이를 정수로 올림한 값이 매직 넘버가 됩니다. Jones(1999)와 Ammon(2010)을 따라 이 방식을 'round-up 알고리즘'이라 부릅니다.

Round-up의 한계와 Round-down 알고리즘

Round-up 알고리즘에는 치명적인 약점이 있습니다. 어떤 제수에서는 매직 넘버가 33비트가 되어 일반적인 32비트 레지스터에 들어가지 않는 경우가 생깁니다. Ammon(2011)의 논문 'Fast Unsigned Division by Constants'은 이를 해결하는 'round-down 알고리즘'을 제시하며, round-up이 실패하는 경우에도 32비트 안에 들어가는 매직 넘버를 찾을 수 있음을 보장합니다.

실제 구현과 검증

저자는 LibDivide를 참고해 매직 넘버를 계산하는 UnsignedMagicInfo 함수를 C로 구현했습니다. 이 함수는 2의 거듭제곱을 제수로 나눈 몫과 나머지를 지수를 올려가며 갱신하고, round-up 조건이 충족되면 quotient + 1을 매직 넘버로, 홀수 제수에서 실패하면 round-down 결과에 increment 플래그를 붙여 반환합니다. 짝수 제수는 2의 인수를 미리 시프트(preShift)로 제거한 뒤 재귀 호출로 처리합니다. 검증 함수 MagicNumberDivisibilityTest는 preShift 적용, 필요 시 피제수 증가, 64비트 곱셈 후 상위 32비트 추출 및 postShift를 거쳐 original == q * divisor로 배수 여부를 판정합니다. 제수 7의 예시에서는 Multiplier 1227133513, Post-shift 1, Increment 1이 출력됩니다.

Reddit 반응

• @DataBaeBee — GCC는 상수 제수를 받으면 두 개의 매직 넘버를 찾아 나눗셈을 곱셈과 비교로 바꾸며, 이 연산의 정식 용어가 '역수 곱셈'이라고 정리했습니다. 2011년의 잘 알려지지 않은 논문이 매직 넘버 도출법을 보여준다고 평가했습니다.
• @Elektro-Hijena — Java의 JIT 컴파일러 C2도 동일하게 나눗셈을 Granlund-Montgomery 곱셈(mul/imul)과 비트 시프트(sar/shr)로 변환한다고 지적했습니다. 7처럼 시프트 전에 결과를 보정하는 덧셈이 필요한 '비협조적 제수(uncooperative divisor)'도 존재한다고 덧붙였습니다.
• @LonelyAndroid11942 — 이 기법의 목적이 부동소수점 정밀도 문제를 줄이는 것인지 질문했고, 다른 댓글 작성자들의 설명을 통해 배울 점이 많았다고 답했습니다.
• @Open-Adhesiveness-86 — 자주 혼동되는 관련 트릭을 소개했습니다. 홀수 d에 대한 x % d == 0 판정은 몫 없이 x에 2^32에 대한 d의 모듈러 역수를 곱한 뒤 결과가 (2^32 - 1) / d 이하인지만 확인하면 되며, 짝수 d는 먼저 trailing zero 비트 수만큼 우측 로테이션하면 됩니다. GCC와 Clang 모두 버전 9 무렵부터 이 형태를 출력하기 시작했으며, 같은 함수에서 x / d도 쓰면 컴파일러가 몫을 따로 계산하는 점에 주의가 필요하다고 설명했습니다.

원문: LeetArxiv (Substack) / 번역·요약: Trawling