최적화 카탈로그. 부동소수점 나눗셈이 정수 나눗셈보다 빠를 때

Go 작업에서 얻은 다소 직관에 반하는 핫패스 최적화 하나를 소개한다. 정수를 더 빠르게 나누기 위해 정수 나눗셈(IDIVQ)을 부동소수점 나눗셈(DIVSD)으로 바꾸는 방법이다.

2026년 06월 08일

지난 프로젝트를 하면서 핫패스 최적화를 꽤 많이 했고, 그중 몇 개는 정말 흥미로웠다. 그러니 그중 일부를 글로 남기지 않을 이유가 없다. 이 시리즈의 시작은 int 연산을 float 연산으로 바꾸는, 직관적이지 않은 치환으로 속도 향상을 얻은 흥미로운 사례다.

부동소수점 나눗셈으로 IDIVQ 피하기

먼저 이 최적화를 보자 (3배라는 주장은 무시해도 된다. 그 문서 주석에서 내가 틀렸다):

diff --git a/huffman.go b/huffman.go
index 33f8263..180dffc 100644
--- a/huffman.go
+++ b/huffman.go
@@ -378,7 +378,11 @@ func optimizeHuffmanCountsForRLE(counts []uint32, goodForRLEBuf *[]bool) {
 		if i != length {
 			sum += int(counts[i])
 			if stride >= 4 {
-				limit = (256*sum + stride/2) / stride
+				// float64 division is ~3x faster than IDIVQ for variable
+				// divisors, and exact for our input range (numerator < 2^25,
+				// denominator < 2^9, quotient < 2^17 — all exactly
+				// representable in float64's 52-bit mantissa).
+				limit = int(float64(256*sum+stride/2) / float64(stride))
 			}
 			if stride == 4 {
 				limit += 120

나는 정수 나눗셈 (256*sum + stride/2) / stride를 부동소수점 나눗셈으로 바꾸고, 그 결과를 다시 int로 변환하고 있다: int(float64(256*sum+stride/2) / float64(stride)). 그런데 정수 연산이 본질적으로 부동소수점 연산보다 더 빠른 것 아닌가? 음, 그렇기도 하지만 실제로는 그렇지 않다. 적어도 이 경우에는.

무엇이든 하기 전에 먼저 벤치마크를 돌려 이 최적화가 실제인지 확인해 보자 (벤치마크 코드):

goos: linux
goarch: amd64
pkg: idivq
cpu: 12th Gen Intel(R) Core(TM) i5-12500
          │    idivq    │               float                │
          │   sec/op    │   sec/op     vs base               │
DivInline   3.358n ± 0%   2.414n ± 0%  -28.10% (p=0.002 n=6)

좋다, 실제다. 마이크로벤치마크에서 28% 향상이다. AMD CPU에서도 벤치마크를 돌려 보자:

goos: linux
goarch: amd64
pkg: idivq
cpu: AMD Ryzen 5 7535HS with Radeon Graphics
          │    idivq    │               float                │
          │   sec/op    │   sec/op     vs base               │
DivInline   2.178n ± 0%   1.959n ± 0%  -10.08% (p=0.002 n=6)

~10% 향상이다.

그렇다면 왜 더 빠를까? 어셈블리를 비교해 보자:

핵심은 IDIVQ가 DIVSD로 대체된다는 점이다. uops.info에 따르면 IDIVQ의 지연 시간은 14-18이고 처리율은 10 사이클이다 (링크). 그리고 DIVSD는 지연 시간이 13, 처리율은 4 사이클이다 (링크). 그래서 내가 봐야 할 수치는 처리율이라고 생각했다.

왜 지연 시간이 아니라 처리율일까? 이 마이크로벤치마크에서는 각 나눗셈이 서로 독립적이기 때문이다. 하나의 결과가 이전 결과에 의존하지 않는다. 따라서 나눗셈 유닛은 가능한 가장 빠른 속도로 작업을 받아 계속 “포화” 상태를 유지한다. 그리고 그 속도를 막는 병목은 지연 시간이 아니라 처리율이다.

그래서 처리율이 10.0에서 4.0으로 떨어질 것이라고 예상했고, 그래서 위 문서 주석에 3x라고 썼다 (정확히는 10/4=2.5이므로 2.5x라고 썼어야 했다). 그런데 왜 실제로는 2.5배 향상이 아니라 ~1.4배만 나왔을까 (인텔에서 28% 향상)?

이 질문에 답하기 위해 perf stat을 실행해 arith.divider_active 메트릭을 수집했다. arith.divider_active는 cpu의 나눗셈 유닛이 바빴던 사이클 수를 센다.

perf에 따르면 IDIVQ에는 정확히 10사이클이 소요되며, 이는 uops.info의 예측과 일치한다 (지연 시간이 아니라 처리율을 본 것이 결국 옳았다). 여기서 하나 더 주목할 점은 총 사이클이 이 경우 겨우 0.03사이클 더 많을 뿐이라는 것이다. 즉, 컴파일러가 0으로 나누기와 오버플로를 검사하려고 추가한 그 모든 기계장치는 무시할 만하다는 뜻이다 (이것도 내가 확인하고 싶었던 또 다른 질문이었다. 혹시 속도 향상이 사실 그 기계장치 제거 때문은 아닐까 했는데, perf는 그렇지 않음을 보여줬다. 속도 향상은 진짜로 더 성능 좋은 DIVSD 명령을 사용했기 때문이다). 부동소수점(DIVSD) 케이스에서는 cpu가 나눗셈에 6.35사이클을 쓴다. 내가 기대했던 4.0사이클이 아니다. 또 추가 작업 때문에 약 1사이클이 더 들어 총 7.29사이클/op가 된다. 그렇다면 uops.info가 틀린 걸까?

내 생각에는 그렇지 않다. 나는 DIVSD 타이밍이 피연산자에 따라 달라진다고 꽤 확신한다.

• 6.35와 4의 차이 자체가 그 신호다. uops.info는 고정된 한 피연산자 집합으로 처리율을 측정하기 때문이다. 다만 정확한 규칙이 무엇인지는 나도 결정적으로 설명하지는 못하겠다.

주의할 점

정수 나눗셈과 부동소수점으로 나눈 뒤 int로 캐스팅하는 방식이 항상 같은 것은 아니다. 이유는 하드웨어에서 부동소수점 수를 표현하는 방식과 반올림 한계 때문이다. 2^53까지의 모든 정수는 fp 숫자로 정확하게 표현된다 (2^53 이후에도 표현 가능한 정수는 있지만, 그 위로는 간격이 생긴다. 짝수만 가능해지고, 그다음에는 4의 배수만 가능해지는 식이다). 아래에서 보겠지만, DIVSD의 피연산자는 <= 2^53이어야 한다. 2^53을 넘는 구간에서 표현 가능한 값들이 있다고 해도 도움이 되지 않는다.

이제 반올림 한계를 보자. 나눗셈 결과를 몫이라 하여 q라고 부르면, 결과는 q = floor(a/b)다. 하지만 a/b의 실제 값은 [q, q+1) 범위 어딘가에 있을 수 있다. 문제는 a/b가 q+1에 너무 가까워서 하드웨어가 그것이 실제로는 q+1보다 작다는 사실을 구별하지 못할 때 발생한다. 그러면 올바른 q 대신 1만큼 큰 q+1을 얻게 된다. ulp를 unit in the last place라고 할 때, ulp(q) >= 2/b이면 a/b는 q+1과 구별되지 않게 된다. 그리고 이는 bits(q) + bits(b) > 54일 때 발생하며, 결국 a ≈ q*b > 2^53을 강제한다.

즉, 기본적으로 a를 b로 나눌 때는 다음 두 제한이 있다:

• a <= 2^53
• b <= 2^53

이 조건들이 만족되면 안전하며, IDIVQ를 DIVSD로 바꿔도 된다.

마무리

즉, 이것은 “정수 연산이 당연히 더 빠르다”는 직관이 틀리는 몇 안 되는 사례 중 하나다. IDIVQ는 가장 비싼 정수 명령 중 하나이고, DIVSD에 int<-->float 변환을 더한 쪽이 실제로 더 빠른 것으로 드러난다. 물론 적용하기 전에 반드시 벤치마크를 해 봐야 한다.

아, 그리고 하나 빼먹었다. 이 최적화는 런타임 변수로 나눌 때만 적용 가능하다. 컴파일 타임 상수로 나누는 경우라면, 컴파일러가 이미 더 나은 최적화로 바꿔 준다.

업데이트

이 글은 Reddit에서 좋은 토론을 이끌어 냈다 (스레드). 몇몇 댓글은 다른 최적화 아이디어를 줬다.

u/Masztufa가 이렇게 썼다:

I wonder if the superscalar nature of cpus also comes up or not in these tests

You're always doing integer math (pointer arithmetic), so it would seem like that choosing integer math would load the int math part of the cpu, while if you used floats for the actual data you could use more of the silicon to get the job done

이 댓글을 보고 나는 번뜩하는 순간이 있었고, int 나눗셈과 float 나눗셈을 교차 배치해서 두 유닛이 동시에 일하게 만들고 슈퍼스칼라 실행의 이점을 얻을 수 있다는 사실을 깨달았다 (커밋). 가장 좋은 조합은 5개의 나눗셈을 교차 배치하는 것이었다: int, int, float, float, float.

---

u/Dwedit는 이렇게 썼다:

One thing with integer math is that it becomes much faster to precalculate a reciprocal and use that instead. The compiler automatically does that for you for constant values, but not for variable values.

uint32_t reciprocal = (uint32_t)(0x100000000ULL / divisor + 1);  //divisor must be > 1

answer = (number * (uint64_t)reciprocal) >> 32;

나누는 수가 여러 번의 나눗셈에 걸쳐 재사용된다면, 나눗셈 자체를 한 번의 곱셈으로 바꿀 수 있다. 나는 이를 여기서 마이크로벤치마크했고, float(divsd) 최적화와 같은 수준의 성능 향상을 얻었다.

u/vip17은 C의 libdivide 라이브러리를 언급했다. 나는 이에 대응하는 go 구현으로 github.com/bmkessler/fastdiv를 찾았다. 내가 벤치마크한 것은 Uint32 버전이라는 점에 유의하자. 전체 64비트 범위에서 정확성을 유지하려면 Uint64 버전은 128비트 연산을 사용해야 하므로 곱셈을 한 번이 아니라 두 번 수행한다. 반면 Uint32 버전은 한 번만 곱하므로, 벤치마크한 다른 최적화들과 더 비슷하다 (대신 범위가 2^32 미만의 숫자로 제한되는 대가가 있다).

마지막으로, 위에서 언급한 교차 배치 기법과 공정하게 비교할 수 있도록 모든 최적화에 대해 5배 언롤 버전도 추가했다. 커밋.

수치들. 5배 언롤 버전만 포함했다:

따라서 u/Dwedit가 제안한 reciprocal multiply가 5배 언롤 루프에서는 가장 좋은 결과를 냈다. int+float split은 재미있는 트릭이지만, 다른 버전들(예: 5x DIVSD)을 단순히 언롤하는 편이 오히려 더 빨랐다.

SIMD는 어떨까? u/Masztufa와 u/vip17이 제안했다. SIMD가 내 divsd 버전보다 더 빠를 것이라는 점에는 동의한다. 하지만 내가 최적화한 함수 optimizeHuffmanCountsForRLE의 핫 루프는 상태 기계처럼 생겨 있어서 벡터화하기가 어렵다. 루프 언롤도 먹히지 않으므로, 언롤하지 않은 버전들 중에서 가장 좋은 것을 골라야 한다.

← 이전 2026년의 웹 압축: brotli, zstd, 그리고 압축 패턴