Lemire, 64비트 환경의 signed 32비트 상수 나눗셈 보정 축소·fastmod 분기 제거

본문

Daniel Lemire가 64비트 프로세서에서 부호 있는(signed) 32비트 정수의 나눗셈을 최적화하는 두 방법을 소개했습니다. 나누는 수인 제수가 컴파일 시 정해지면 곱셈 뒤 보정 단계를 줄이고, 실행 중 제수가 정해지는 fastmod에는 부호 분기를 없앤 구현을 넣어 0.2.0으로 배포했습니다.

앞서 소개한 Ben Joffe의 방식이 signed floor 나눗셈을 다뤘다면, Lemire의 글은 C의 signed 나눗셈처럼 결과를 0 방향으로 버리는 32비트 연산을 다룹니다. 제수가 상수면 GCC와 LLVM은 나눗셈을 대개 곱셈과 시프트로 바꿉니다. 제수 7의 경우 GCC 14는 필요한 곱셈 상수가 signed 32비트에 들어가지 않아 다른 상수를 쓰고 보정 연산을 덧붙입니다. Lemire의 방법은 signed 32비트 입력과 곱셈 상수의 범위를 이용해 64비트 signed 곱셈을 수행하므로 그 보정을 생략합니다. 입력이 음수이면 곱셈·시프트 결과에 1을 더해 C의 0 방향 절단에 맞춥니다. 이 방법은 양수이면서 2의 거듭제곱이 아닌 상수를 대상으로 하며, 기존 컴파일러 코드에 보정 단계가 있을 때 성능 이득을 기대할 수 있습니다.

Lemire는 무작위 signed 정수 16,384개로 Intel Xeon Gold 6548N에서 GCC 14와 Clang 21을, Apple M4 Max에서 Apple Clang 17을 시험했습니다. 처리량 측정은 서로 독립적인 나눗셈을, 지연시간 측정은 앞 계산 결과에 다음 나눗셈을 의존시키는 방식을 사용했고 자동 벡터화는 껐습니다. 제수 7, 60, 365의 지연시간은 Intel에서 GCC 기준 10사이클에서 8사이클로 줄었고, Clang은 약 10.4~10.6사이클에서 8사이클로 줄었습니다. 이 지연시간에는 의존성 측정용 오버헤드 2사이클이 포함됩니다. M4에서는 지연시간이 12% 줄었고, Intel 처리량은 Clang에서 20% 넘게 개선됐지만 GCC에서는 달라지지 않았습니다. 제수 1000처럼 기존 상수에 보정이 필요 없는 경우 M4에서 새 코드의 지연시간은 1.77ns로 기존 코드의 1.57ns보다 길었습니다.

제수가 실행 중에 정해지면 컴파일러는 상수 나눗셈 최적화를 적용하지 못하고 나눗셈 명령을 내보냅니다. Lemire의 fastmod 라이브러리는 미리 계산한 곱셈 상수로 나누는 방식인데, 기존 signed 함수는 미리 계산한 곱셈 상수 M을 unsigned, 즉 부호 없는 정수로 다뤘고, 입력이 음수일 때 곱셈 결과를 보정하기 위해 입력의 부호에 따라 분기했습니다. Lemire의 시험에서는 부호가 무작위일 때 이 분기가 36~48%의 나눗셈에서 예측에 실패했습니다. 새 구현은 M을 signed로 해석한 곱셈 결과의 상위 비트를 쓰고, 제수의 절댓값이 2인 경우의 보정도 비트 연산으로 처리해 분기를 없앴고, fastmod 0.2.0에 반영했습니다.

실행 중 제수를 7로 전달하고 입력의 부호를 무작위로 한 독립 나눗셈 처리량 시험에서 새 버전은 Intel 프로세서에서 이전 fastmod보다 4배, 하드웨어 나눗셈 명령보다 2배 넘는 처리량을 기록했습니다. M4에서는 컴파일러가 기존 분기를 두 경우 계산 후 선택하는 코드로 바꿔 스칼라 성능 차이가 작았습니다. 자동 벡터화를 허용하면 새 함수를 호출하는 루프를 부분적으로 벡터화해 나눗셈당 0.22ns를 기록했습니다.

자료: Daniel Lemire / 정리·해설: Trawling