날짜를 요일로 바꾸는 일은 언뜻 사소해 보인다. 1970년 1월 1일을 기준(rata-die, 일자 카운트)으로 삼아 경과한 날 수를 7로 나눈 나머지를 구하면 그만이기 때문이다. 그러나 이 계산을 하드웨어 명령어 수준까지 파고들면 의외로 까다로운 문제가 드러난다. 벤 조프(Ben Joffe)가 정리한 이 글은 컴파일러가 자동으로 만들어내는 코드보다 더 빠른 요일 계산 함수들을 사용 목적별로 제시한다. 어떤 함수는 곱셈 한 번에 두 사이클 남짓의 지연으로 결과를 낸다. 날짜·시간 라이브러리나 데이터베이스 엔진처럼 이 연산이 초당 수백만 번 반복되는 환경에서는 이런 미세 최적화가 실제 처리량 차이로 이어진다.
나눗셈이 느린 이유
7로 나누는 나눗셈이 왜 문제가 되는지부터 짚을 필요가 있다. 현대 CPU에서 정수 나눗셈은 곱셈보다 훨씬 느리기 때문에, 컴파일러는 나눗셈을 '매직 상수' 곱셈과 시프트 조합으로 바꿔 처리한다. 그런데 7은 이 변환에 비협조적인 제수다. 7의 역수 근사값을 담으려면 32비트 레지스터로는 정밀도가 부족해, GCC와 Clang이 만들어내는 코드는 초기 근사값을 바로잡는 보정 항 여러 개를 직렬로 덧붙인다. 이 보정 단계가 서로 의존적으로 이어지면서 지연이 쌓인다. 러스트의 양수 나머지 함수 rem_euclid를 C 스타일로 풀어 보면 예상보다 훨씬 많은 단계를 거친다는 사실이 이를 잘 보여준다.
이 분야에는 이미 정평 있는 접근들이 있다. 하워드 히넌트(Howard Hinnant)가 2014년 제시한 방식은 단순함과 이식성을 노려 여러 날짜 라이브러리에 채택됐다. 부호 캐스팅이나 오버플로에 의존하지 않고 8비트부터 64비트까지 동일한 논리로 동작하며, 최상위 4개 입력값(약 580만 년 후)을 제외한 부호 있는 32비트 전 범위를 다룬다. 라즈베리 파이 제로 같은 구형 칩에서는 오히려 매우 빠르다. 카시오 네리(Cassio Neri)가 2024년 발표한 함수는 전 범위를 깔끔하게 처리하는 현대적 기준점으로, 연산 전에 부호 있는 값을 부호 없는 값으로 캐스팅해 오버플로를 피하는 것이 핵심이다.
메르센 수가 여는 지름길
글의 백미는 7이 메르센 수, 즉 2의 N제곱에서 1을 뺀 형태라는 성질을 이용하는 대목이다. 이런 수에는 N % 7 = floor(N × 8 / 7) % 8 같은 항등식이 성립한다. 여기서 × 8 / 7은 약 1.142857을 곱하는 것과 같은데, 이를 곱셈 한 번과 오른쪽 시프트 한 번으로 근사한다. 보통은 곱셈 결과의 상위 비트를 취하지만, 이 기법은 하위 비트를 취해 레지스터 크기보다 정확히 3 적은 만큼 시프트한다. 그러면 남는 3비트가 곧 % 8 결과가 되어 마지막 나머지 연산이 공짜로 처리된다. 곱셈·덧셈·시프트 세 명령이면 요일이 나온다.
여기서 흥미로운 지점은 상수 하나의 역할이다. 시프트 전에 특정 값 Z를 더하면 결과값들이 원 위에서 '회전'하며 유닉스 기준일이 목요일이라는 사실에 맞춰 정렬된다. 이 상수만 바꾸면 같은 명령어로, 속도 손해 전혀 없이 결과를 유닉스 형식 0~6이 아니라 ISO 형식 1~7로 낼 수 있다. 다만 이 방식은 근사에 기반하므로 오차가 서서히 누적되어 정확히 동작하는 입력 범위가 제한된다. ISO 형식에서는 32비트 공간의 24분의 1에 해당하는 약 ±8,900만 일 안에서만 정확하다. 이는 약 ±24만 년에 해당하므로, ±1만 년 범위를 지원하는 러스트 Jiff 라이브러리 같은 곳에는 충분하다. 실제로 Jiff는 이 기법을 도입해 nth_weekday_of_month 같은 상위 함수에서 40% 속도 향상을 얻었다.
전 범위와 아키텍처별 최적화
전 범위 지원이 필요하면 64비트로 확장하거나, 헨리 워런의 고전 『해커의 기쁨(Hacker's Delight)』 2판에서 소개된 보정 항을 활용한다. 이상적인 곱수 2³²/7의 소수부는 정확히 4/7인데, (x >> 1) + (x >> 4) 즉 0.5625가 이 부족분을 근사한다. 핵심은 이 보정 값 b가 이전 계산이 아니라 입력값에만 의존한다는 점이다. 덕분에 곱셈 rd × M이 진행되는 동안 b를 병렬로 계산할 수 있다. x86의 슈퍼스칼라 구조에서는 곱셈(대개 3사이클)이 끝나는 시점에 시프트로 얻은 b도 준비되고, LEA 명령어가 둘과 Z를 한 번에 더한다. 보정 계산을 넣든 빼든 지연이 같게 측정된다는 벤치마크가 이 병렬성을 뒷받침한다.
ARM에서는 상황이 더 낫다. 많은 명령어가 오른쪽 시프트를 같은 사이클에 융합하므로 b를 단 두 사이클에 구할 수 있고, 곱셈과 덧셈이 MADD 하나로 합쳐진다. 여기에 마지막 시프트까지 후속 코드의 덧셈·뺄셈과 융합되면, 월의 N번째 요일을 구하는 것 같은 전형적 작업에서는 사실상 단일 명령에 가깝게 컴파일될 여지가 있다. 참고로 하위 몇 바이트를 0으로 맞춘 곱수는 ARM 어셈블리를 더 짧게 만들어 소소한 이득을 준다.
실무자 입장에서 명심할 한계도 분명하다. 이 기법들 상당수는 부호 캐스팅, 오버플로의 정의되지 않은 동작, 특정 비트 폭에 의존하므로 이식성과 유지보수성을 희생한다. 대부분의 일반 코드라면 네리의 전 범위 함수처럼 읽기 쉬운 쪽을 택하는 편이 낫고, 극단적 최적화는 지원 범위가 명확히 좁은 라이브러리나 성능이 임계인 엔진에서만 값어치를 한다. 또한 이 곱셈-시프트 나머지 기법은 요일 계산에만 국한되지 않는다. x % (2ᴺ − 1) 형태 일반으로 확장되며, 글은 시각 계산에 필요한 x % 24나 x % 60 같은 제수에도 적용되는 새 기법을 함께 소개한다. 결국 '7로 나눈 나머지'라는 단순한 문제 하나가 저수준 비트 조작이 왜 여전히 흥미로운 최적화 영역인지를 압축해 보여주는 셈이다.