새 알고리즘이 상수 나눗셈을 ARM에서 10~20% 빠르게 한다

상수로 나누는 부호 있는 64비트 정수의 내림 나눗셈을 더 빠르게 계산하는 알고리즘이 제안됐다. 글에 실린 벤치마크에서는 이상적으로 컴파일했을 때 기존 알고리즘보다 ARM에서 대부분의 제수에 대해 처리량이 10~20% 높았고, x86에서는 양수 제수의 약 80%, 음수 제수의 약 60%에서 약 5~10% 높았다. 나머지 x86 사례에서는 더 느렸으며 지연 시간은 대체로 기존 알고리즘보다 나빴지만 경쟁력 있는 수준이었다. 결과는 특정 기기와 컴파일러에서 얻은 것이므로 다른 환경에서도 같은 차이가 난다고 보장하지 않는다.

내림 나눗셈(floor division)은 결과를 음의 무한대 방향으로 내린다. 0 방향으로 버리는 일반적인 부호 있는 나눗셈과 다르다. 예를 들어 음수 타임스탬프를 86400으로 나눌 때 일반 나눗셈은 날짜 계산에 맞지 않는 결과를 낼 수 있다. 이 글은 제수가 컴파일 시점에 알려진 경우를 다루며, 새 방식은 여러 비트 폭에서 쓸 수 있고 64비트에서 가장 큰 이점을 노린다. 양수 나머지 연산과 유클리드 나눗셈에도 활용할 수 있다.

글쓴이는 벤치마크 결과와 참조 구현을 공개했다. 웹 페이지의 함수 생성기로 비트 폭과 제수를 골라 코드를 만들 수 있고, 64비트 함수와 테스트 파일도 내려받을 수 있다. 코드를 주석까지 그대로 복사할 때만 해당 라이선스가 적용된다고 설명한다. 같은 로직을 다시 작성하는 경우에는 라이선스가 필요하지 않다고 글은 밝힌다.

나눗셈 방식과 기존 최적화

C, C++, Go, Swift 등 주류 언어와 컴파일러 중에는 내림 나눗셈을 기본 제공하지 않는 경우가 있다. C++의 x / 86400은 음수에서 0 방향으로 버리므로, 음수 타임스탬프 대부분에 틀린 결과를 낸다. 나머지까지 계산해 보정하는 일반적인 방법은 다음과 같다.

const int64_t div = x / 86400;
const int64_t rem = x % 86400;
return div - (rem < 0);

제수가 양수일 때 나머지 연산을 피하려고 div * 86400 > x를 검사하는 방법도 있지만, 글의 GodBolt 비교에서는 더 많은 어셈블리 명령을 만들고 느렸다. 양수·음수 제수를 모두 처리하는 흔한 일반식은 다음과 같다.

const int64_t div = x / y;
const int64_t rem = x % y;
return div - (rem != 0 && (x ^ y) < 0);

자바의 Math.floorDiv, NumPy, Zig, Ruby 등에서 유사한 방법을 쓴다고 글은 설명한다. 컴파일러가 상수 제수를 알면 일반 나눗셈을 곱셈과 시프트로 바꾸기도 하지만, 제수에 따라 보정이 필요하다. 예를 들어 100처럼 곱셈 상수가 비트 폭을 모두 쓰는 ‘비협조적’ 제수는 상위 곱셈 결과에 입력값을 더하는 보정이 들어갈 수 있다. 글은 일반 나눗셈이 대체로 곱셈 한 번과 2~3사이클 정도의 비용이라고 설명한다.

Granlund와 Montgomery가 1994년에 발표한 방법은 컴파일 시점 상수 제수에서 내림 나눗셈을 처리한다. 글은 양수 제수에 대해 음수 입력을 보정하는 XOR 기법도 설명한다. 음수를 비음수 영역으로 반사해 입력 범위를 절반으로 줄이고, 곱셈-시프트를 적용한 뒤 부호를 복원한다. 이 방식은 비협조적 제수에서도 곱셈-시프트만으로 처리할 수 있다. 글에서 확인한 라이브러리 사례는 PyPy이며, 음수 제수에는 나눗셈·나머지 방식으로 되돌아간다.

Robison의 2005년 방식은 곱셈, 덧셈, 시프트를 이용한다. 32비트 ARM에서는 곱셈-누산 명령을 활용할 수 있고, 8비트 계산에도 적합하다고 글은 평가한다. 예를 들어 32비트에서 100으로 나누는 식은 다음과 같다.

i32 A = 1374389535
i32 B = 0x28F50000
return (i64(x) * A + B) >> 37;

다만 제수에 따라 곱셈 상수가 비트 폭보다 커져 더 넓은 곱셈이 필요하다. 64비트에서는 128비트 곱셈을 두 개의 64비트 레지스터로 에뮬레이트할 수 있고, 특히 ARM64에서는 상·하위 곱 결과를 얻기 위한 곱셈 명령이 각각 필요해 보정 비용이 커질 수 있다. GCC와 Clang은 같은 수식을 서로 다르게 컴파일하기도 한다. 글은 64비트 Robison 구현을 두 가지 형태로 벤치마크에 포함했다.

새 알고리즘과 적용 범위

새 방식은 올림 또는 내림 곱셈 상수를 입력의 부호에 따라 선택한다. 제수 3을 예로 들면 양수와 음수 방향에서 각기 정확한 쪽의 곱셈 상수를 택해, 부호 양쪽에서 올바른 내림 결과를 얻는다. 핵심 형태는 다음과 같다.

i64 M = MAX_U64 / 3 + 1
i64 m = M + (x >> 63)
i64 y = (i128)x * m >> 64

ARM64에서는 M + (x >> 63)을 시프트가 결합된 덧셈 한 명령으로 계산할 수 있다고 글은 설명한다. GCC는 이를 잘 컴파일했지만, 벤치마크 루프에서 Clang은 최적화가 어긋나는 경우가 있었다. 글은 C++에서 asm("" : "+r"(m));를 두 번째 줄 뒤에 넣으면 컴파일러가 m >= 0임을 증명하지 못해 해당 최적화 문제를 피할 수 있다고 적었다. Robison 방식에도 최적 코드를 얻기 위한 비슷한 어셈블리 장벽이 필요했던 사례가 있다.

일부 제수에는 부호 선택 방식 대신 입력을 특정 조건에서 1만큼 올리거나 내리고 곱셈-시프트를 적용할 수 있다. 예컨대 제수 3의 경우 올림 상수와 x < -1 조건을 쓰거나, 내림 상수와 0 <= x < MAX_INT64 조건을 쓰는 대안이 있다. 두 방식 모두 경계값에서 오버플로와 잘못된 결과를 피하도록 조건을 제한한다. 모든 제수가 두 반올림 방향을 모두 지원하는 것은 아니다. 제수별로 올림, 내림, 부호 선택 중 가능한 변형을 컴파일 시점에 계산한다.

음수 제수도 처리할 수 있지만 부호와 비교 조건을 조정해야 한다. 글의 예에서 -3은 한 방향의 반올림만 가능하고, -5는 시프트 65에서 부호 선택 방식이 가능하다. 음수 제수에 대한 구현은 양수 제수와 같은 공식에 단순히 부호만 바꾸는 것만으로는 충분하지 않다.

내림 나머지는 x - fast_floor_div<Divisor>(x) * Divisor로 얻을 수 있다. 음수 제수의 유클리드 나눗셈은 INT_MIN을 제외하면 양수 크기의 제수로 계산한 내림 몫을 부정하는 방식으로 만들 수 있으며, 나머지는 x + floor_div * Divisor로 구한다. 글은 뒤이은 부정 연산이 경우에 따라 후속 계산에 흡수될 수 있다고 설명한다.

검증과 성능 측정

글쓴이는 64비트에서 -32768부터 32767까지의 제수 65535개를 생성하고 경계값 테스트를 포함하는 단일 C++ 파일을 제공한다고 설명한다. 32비트 테스트 파일도 같은 제수 범위에 대해 만들 수 있으며, 파일 상단 주석에 빌드·실행 방법이 있다고 안내한다. 재현용 테스트와 벤치마크 코드는 저장소에 있다. 글에 제시된 실행 명령은 다음과 같다.

git clone https://github.com/benjoffe/fast-floordiv.git
cd fast-floordiv
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
./build/bin/div_bench -batch=8
./build/bin/div_bench -latency

측정 대상은 2의 거듭제곱이 아닌 -2^4부터 2^5까지의 제수와 100, 360, 86400, 105, 107, 86400000, 108 등 일부 큰 양수 제수다. 각 측정은 -repeat=10으로 실행해 중앙값을 기록했다. -batch=8은 메모리 접근이 병목이 되지 않도록 제수마다 계산을 8회씩 수행한다. 지연 시간 측정은 한 계산의 결과를 다음 계산의 입력으로 연결해 병렬화를 막는다.

테스트한 ARM 기기는 MacBook Pro M4 Pro와 Snapdragon X1-26-100 노트북이며, x86 기기는 AMD Ryzen 9 9950X3D와 2016년 MacBook Pro의 Intel 프로세서다. 컴파일러와 운영체제도 결과에 영향을 준다. ARM 처리량에서는 새 알고리즘이 모든 제수에서 가장 빠르거나 gm-v2와 동률이었다. ARM 지연 시간에서도 새 방식이 가장 빠르거나 동률이었다. x86 처리량은 Robison과 새 알고리즘 사이에서 우위가 바뀌었고, 일부 제수에서는 gm-v2도 가장 빨랐다. x86 지연 시간에서는 Robison이 대부분의 제수에서 앞섰다. 새 알고리즘이 처리량과 지연 시간 모두에서 드물게 이긴 사례는 14, -7, -14였다.

x86에서 새 방식이 이기지 못한 양수 제수 사례는 7, 11, 13, 22, 26, 29였으며, 글은 이들이 64비트 양수 제수의 약 20%를 차지하는 올림 전용 제수라고 설명한다. 음수 사례는 -3, -5, -9, -11, -13, -15였고, Robison이 협조적인 경우에 부호 선택 방식이 불가능한 제수였다. 글은 음수 제수 전체에서 이런 유형이 약 40%라고 적었다. 나머지까지 계산하면 전통 방식과 빠른 방식의 차이는 줄지만, 빠른 방식이 여전히 더 빠르다고 덧붙였다. 나머지 성능 벤치마크는 제시하지 않았다.

구현 선택과 주의점

글은 8·16·32비트에서는 일반적으로 Robison 방식을 권한다. 64비트도 최대 성능이 목표가 아니라면 Robison 하나만 쓰는 편이 구현을 단순하게 유지할 수 있다. ARM 64비트에서는 새 알고리즘이 측정한 모든 지표에서 더 빠르거나 동률이어서 새 방식을 권한다. x86 64비트에서는 처리량을 우선하면 새 알고리즘이 대체로 유리하고, 지연 시간을 중시하면 Robison을 고려할 수 있다. 최대 처리량을 위한 라이브러리는 제수에 따라 알고리즘을 선택할 수 있지만, 글은 이를 상당히 적극적인 최적화라고 본다.

32비트 프로세서에서 직접 측정하지는 않았다. 글쓴이는 32비트 ARM에서는 곱셈-누산 명령을 활용하는 Robison 방식이 강할 것으로 예상하며, 32비트 x86은 64비트 x86과 비슷하게 선택이 복잡할 수 있다고 본다. ARM SVE2 SIMD에서는 새 방식의 이점이 벤치마크보다 클 가능성이 있지만, 글쓴이는 해당 기기를 직접 시험하지 못했다고 밝혔다. SIMD 최적화는 확인되지 않았다.

컴파일 시점에는 올림·내림 방식의 최악 사례를 검사해 상수와 시프트를 구한다. 양수 제수의 경우 올림 방식은 (D−1) mod D, 내림 방식은 0 mod D인 최악의 분자를 고려한다. 64비트에서는 특정 제수에 따라 내림 방식의 최악 입력이 정확한 정수가 되어 결과가 1만큼 높아지는 문제가 생길 수 있으며, 그런 제수에는 내림 방식이 선택되지 않는다. 음수 제수에서는 위험한 방향이 반대다. 두 반올림 방향이 모두 성립하면 더 큰 시프트를 쓰는 부호 선택 방식도 성립한다.

글은 새 알고리즘이 처음 제시된 방식인지 확정하지 않는다. 간단한 기법이라 이전에 누군가 사용했을 가능성이 있다고 보지만, 문서화된 사례를 찾지 못했다고 설명한다. 따라서 새롭다는 주장은 글쓴이가 조사한 범위에 관한 것이다.

TensorFlow의 오버플로 버그

글은 빠른 내림 나눗셈을 직접 구현할 때 철저한 테스트가 필요하다고 강조하며 TensorFlow의 과거 구현을 사례로 든다. 서로 부호가 다른 두 수를 절댓값으로 바꾼 뒤 abs_x + abs_y - 1을 계산하는 식이 극단적인 입력에서 부호 있는 64비트 범위를 넘을 수 있었다. 이 버그는 2017년 2월 TensorFlow 1.0에 들어갔고, 2021년 5월 수정되기까지 4년 넘게 남아 있었다. 글은 구현이 성숙하고 검토가 많이 된 코드베이스에서도 이런 오류가 발생할 수 있다며 언어와 표준 라이브러리가 내림 나눗셈을 기본 제공할 필요가 있다고 주장한다.

CPython은 부호 없는 정수를 쓰고 abs_y 항을 인수분해해 오버플로를 피하는 방법을 사용한다고 소개한다. 다만 이 방법도 INT_MIN에서 문제가 생길 수 있다고 글은 지적한다. TensorFlow의 당시 구현과 CPython 방식에 대한 링크는 각각 TensorFlow 소스, CPython 소스에 있다.

글은 상수 나눗셈의 배경으로 Hacker's Delight 2판의 관련 절도 언급한다. 해당 절은 나머지나 내림 나눗셈에 곱셈 상수를 적용하는 일이 단순하지 않으며, 부호에 따라 상수를 조정할 수 있다고만 적었다고 인용한다. 벤치마크에는 1994년 Granlund–Montgomery 논문, 2005년 Robison 논문, Stack Overflow 토론 등도 참고 자료로 연결돼 있다.

요약하면, 컴파일 시점 상수 제수의 64비트 내림 나눗셈은 곱셈-시프트만으로 처리할 수 있는 경우가 많지만, 제수와 CPU, 컴파일러에 따라 가장 빠른 변형이 달라진다. 새 방식은 ARM 64비트에서 특히 유망하고 x86에서는 처리량과 지연 시간의 우선순위에 따라 Robison 방식과 비교해 선택해야 한다.