64비트 floor 나눗셈, 부호별 상수 선택으로 더 빠르게 계산한다

본문

signed 정수 나눗셈은 보통 결과를 0 방향으로 버립니다. 예를 들어 -1을 86400으로 나누면 0이 되지만, floor 나눗셈은 음의 무한대 방향으로 내려 -1을 반환합니다. Unix 시간을 날짜 단위로 바꾸거나 타일 좌표와 반복 주기를 계산할 때 이 차이가 결과에 반영됩니다.

새 방식은 부호에 따라 상수를 고릅니다

제수가 컴파일 시점에 고정되면 컴파일러는 흔히 나눗셈을 미리 계산한 곱셈 상수와 비트 시프트로 바꿉니다. 기존 signed 나눗셈 최적화는 음수 입력을 보정하는 연산을 덧붙이고, floor 나눗셈 구현은 나머지 부호 등을 이용해 추가 보정을 하는 경우가 있습니다. 새 방식의 요점은 입력의 부호에 따라 서로 다른 곱셈 상수를 선택해 음수와 양수의 결과를 맞추는 것입니다. 제수 3의 예에서는 부호 비트를 이용해 상수를 조정한 뒤 넓은 정수 곱셈 결과를 시프트합니다. 이 방식은 제수에 따라 적용 가능한 형태가 달라지며, 컴파일 시점에 제수가 알려져야 합니다.

곱셈에 덧셈과 시프트를 결합하는 Robison 방식은 2005년 논문에 설명된 기존 기법입니다. Joffe의 제안은 상수 나눗셈을 곱셈 기반으로 바꾸는 발상 자체보다, signed 전체 범위의 floor 결과를 위해 제수별로 부호에 맞는 상수를 선택하는 데 차이가 있습니다.

성능은 CPU와 측정 지표에 따라 달라집니다

Joffe는 MacBook Pro M4 Pro와 Snapdragon X1-26-100 등 ARM 기기, AMD Ryzen 9 9950X3D와 2016년형 MacBook Pro 등 x86 기기에서 여러 컴파일러로 측정했습니다. 제수별 벤치마크에서 새 방식은 ARM 64비트의 다수 사례에서 기존 알고리즘보다 처리량이 10~20% 높았고 지연시간도 같거나 낮았다고 보고했습니다. x86에서는 양수 제수의 약 80%, 음수 제수의 약 60%에서 처리량이 5~10% 높았지만 나머지 사례에서는 느렸으며, 지연시간은 대체로 Robison 방식이 앞섰습니다.

측정은 반복 계산 처리량과 앞 계산 결과를 다음 나눗셈에 넣는 지연시간을 따로 다뤘습니다. 글에 적힌 권고도 용도별로 나뉩니다. 저자는 8·16·32비트에는 Robison 방식을 일반적으로 권하고, ARM 64비트 최적화에는 새 방식을 추천합니다. x86 64비트에서는 처리량을 우선할지 지연시간을 우선할지에 따라 선택이 달라집니다. 벤치마크는 특정 기기와 컴파일러, 선택된 제수 집합의 결과이므로 다른 코드와 환경에서 같은 차이가 난다는 보장은 자료에 없습니다.

자료: Ben Joffe / 정리·해설: Trawling

참고 자료

• ARITH17_Robison.pdf — https://www.acsel-lab.com/arithmetic/arith17/papers/ARITH17_Robison.pdf