メルセンヌ数で%7を消す高速曜日計算、コンパイラとJITの最適化にどこまで勝てるかM4で実測した

Xを眺めていたら、Ben Joffeが2026年8月17日に公開した A faster way to calculate the day-of-the-week の話が流れてきた。7が $2^3-1$ のメルセンヌ数であることを使って、曜日計算の剰余を乗算・加算・シフトの数命令に置き換えるアルゴリズムで、Rustの日時ライブラリJiffに採用されて nth_weekday_of_month などの呼び出し元の関数が40%速くなったとある。

clangは % 7 をとっくにマジックナンバーによる乗算とシフト（コンパイラがよくやる定数除算の最適化）へ変形しているのに、手書きのビットハックでまだ勝てるのか。気になったのでM4でベンチを書いて回してみた。

Quake IIIの高速逆平方根をM4で回したときと同じように、正しさの全数チェックから生成コードの中身まで一通り確かめた。ついでに、clangだけでなく、そもそも「CPU数命令」という話が成り立つのか怪しいV8とCPythonでも同じ比較を回した。

アルゴリズムの中身

入力は1970年1月1日を0日目とする通し日数（Rata Die）で、負の値は1970年より前の日付を表す。
普通に書くとこんな感じ。曜日は0=日曜〜6=土曜。

uint32_t weekday(int32_t rd) {
    return ((rd % 7) + 11) % 7;
}

Cの % は負の被除数で負の余りを返すので、+ 11（曜日を合わせる4と、負の余りを正へ戻す7）を足してもう一度 % 7 する、という定番の書き方。

Joffeの手法は n % 7 を直接求めない。
恒等式 n % 7 = floor(n * 8 / 7) % 8 を使って、7日周期を「8日目が架空の1日」の8日周期に読み替える。
8で割った余りは下位3bitだけで決まるので、残るのは n * 8 / 7 の近似だけで、これは固定小数点の定数乗算1回で済む。

実用範囲（±約89,434,796日 = 約±245,000年）だけでよければ、ここまで短くなる。

uint32_t weekday_joffe(int32_t rd) {
    const uint32_t M = 613566757;   // (1 << 32) / 7 + 1
    const uint32_t Z = 0x94920000;  // 1970年エポックの曜日オフセット込み
    return ((uint32_t)rd * M + Z) >> 29;
}

M は $2^{32} \cdot \frac{8}{7} \cdot \frac{1}{8}$ を固定小数点で近似した値で、乗算のオーバーフローがそのまま「mod $2^{32}$」として働く。
定数 Z は出力を1970年エポックの木曜日に合わせるための値で、計算が最初から最後まで符号なし32bit演算だけで済むため、負の日付の分岐も、+11 を足して正に戻す手間もいらない。
上位3bitが架空の8日週の中の曜日になっていて、>> 29 で取り出す。

int32全域で正しい完全版は、近似による誤差を補う項が2つ増える。

uint32_t weekday_joffe_full(int32_t rd) {
    const uint32_t M = 613566756;   // (1 << 32) / 7
    const uint32_t Z = 0x95000000;
    const uint32_t a = (uint32_t)rd * M + Z;
    const uint32_t b = (uint32_t)((rd >> 1) + (rd >> 4));
    return (a + b) >> 29;
}

原典には8bit・16bit・64bit版、ISO曜日（1=月曜）版、エポック違いまで何十種類もあり、GitHubのfast-world-calendars に一式置いてある。
今回はこの2つを普通の書き方と比べた。

ベンチの作り

計測は全部手元のM4 Mac miniで、同じ入力データ・同じ計り方に揃えた。

項目	値
機種	Mac mini (Apple M4, 10コア)
メモリ	16 GB unified memory
OS	macOS 26.5.2
C	Apple clang 21.0.0、-O2
Rust	rustc 1.92.0、-O
JavaScript	Node.js 25.3.0 (V8 14.1)
Python	CPython 3.14.4
データ	±89,000,000日の一様乱数 200万件（Pythonのみ20万件）
計測	各7回実行の最良値、ns/op

スループット（配列を流し込んで独立に計算）とレイテンシ（前の結果を次の入力へ混ぜて数珠つなぎにする）を分けて測った。
配列処理ならスループット、単発呼び出しの体感はレイテンシに近い。

速度を測る前に、C版はint32の全43億値で完全版と ((rd % 7) + 11) % 7 の一致を突き合わせ、範囲限定版は仕様範囲（-89,434,796〜89,522,175）の全数を照合して、全実装が一致した。
ちなみにこの検証では、Joffe側より先に、比較用に自分で書いた方が不一致を出した。rd + 4 がINT32_MAX近辺でオーバーフローする未定義動作で、int64で受けるよう直してから通した。

計測コード一式は LiltingChannelLabo/2026/08/20/fast-day-of-week-mersenne-benchmark に置いた。

clangのマジックナンバーによる除算と比べる

まずはCで、普通の書き方2種とJoffeの実装2種を -O2 でコンパイルして単体関数のアセンブリを出した。

普通に書いた ((rd % 7) + 11) % 7 は21命令になった。
clangは1回目の % 7 をマジックナンバーによる乗算（smull + シフト + msub 相当の列）へ変換している。
2回目はさらに凝っていて、clangは「(rd % 7) + 11 は5〜17の範囲になる」という値域解析までやった上で、8bit幅に縮めた同じ形の乗算（37を掛けて8bitシフト）を選んでいた。
それでも % 7 は2回とも残る。単純に1回へまとめた (rd + 11) % 7 は負の入力で結果が変わってしまうので、clangはこの形のまま最適化している。

Rust風に rem_euclid 相当（余りを計算して負なら+7）で書いた版は14命令で、分岐は csel に置き換わっていた。
Joffe完全版は8命令。
範囲限定版は定数ロードを除けば madd（乗算加算）と lsr（右シフト）の2命令 で、原典の言う「乗算・加算・シフトの3演算」よりさらに少ない。madd は乗算と加算を1命令で一度にやる。

_joffe_narrow:
    mov  w8, #18725             ; M = 613566757 (下位)
    movk w8, #9362, lsl #16     ; M (上位)
    mov  w9, #-1802371072       ; Z = 0x94920000
    madd w8, w0, w8, w9         ; rd * M + Z
    lsr  w0, w8, #29            ; 上位3bit
    ret

実測するとこんな感じだった。

実装	命令数	スループット (ns/op)	レイテンシ (ns/op)
((rd%7)+11)%7	21	0.379	5.89
rem_euclid風	14	0.320	2.98
Joffe完全版	8	0.104	1.82
Joffe範囲限定版	5	0.059	1.81

範囲限定版のスループット0.059 ns/opは、M4のクロックでおよそ0.26サイクル/要素。
逆平方根の記事と同じ現象で、ループ全体がNEONへ自動ベクトル化されている（アセンブリにベクトルレジスタ演算が323箇所）。
これは普通の書き方も同じ条件で、それでも6.4倍の差がついた。単発呼び出しに近いレイテンシでも3.2倍ある。

コンパイラは確かに % 7 を最適化している。ただしclangが守っているのは「Cの % の結果」で、この数値が曜日だとは知らない。
人間の側は、エポックのオフセットと負数の折り返しを定数 Z へ埋め込んでよいし、7日週を8日週として扱ってよいと決められる。この自由度が21命令と5命令の差になっている。

最適化を切った -O0 も測ってみた。マジックナンバーによる乗算は消えて実際の sdiv 除算命令が出るが、M4の整数除算は速く、普通の書き方1.27に対してJoffe範囲限定版0.92 ns/op（関数呼び出しコスト込み）で、差は1.4倍まで小さくなった。
M4の整数除算命令が速いぶん、マジックナンバーの恩恵がなくても差はこの程度にしかならない。

RustでJiffの置き換えを再現する

Jiffは rem_euclid(7) を使う経路をこのトリックへ置き換えたので、Rustでも同じ3実装を測った。

fn naive_rem_euclid(rd: i32) -> u32 {
    ((rd as i64 + 4).rem_euclid(7)) as u32
}

fn joffe_narrow(rd: i32) -> u32 {
    ((rd as u32).wrapping_mul(613_566_757).wrapping_add(0x9492_0000)) >> 29
}

実装	スループット (ns/op)	レイテンシ (ns/op)
rem_euclid(7)	0.307	2.95
((rd%7)+11)%7	0.376	5.92
Joffe範囲限定版	0.059	1.58

数字はCとほぼ同じだった。rustcもclangも最後は同じLLVMがコードを生成するので、この規模の関数では言語の違いが出ない。
マイクロベンチのスループット5.2倍・レイテンシ1.9倍が、日付オブジェクトの分解や月初計算と混ざった実際のライブラリ関数で40%に薄まったとすれば、Jiffの実測とも矛盾しない。

V8のJITはどこまでやるか

JavaScriptでも同じ3実装を書いた。

function naive(rd) {
  return ((rd % 7) + 11) % 7;
}

function naiveBranch(rd) {
  const r = (rd + 4) % 7;
  return r < 0 ? r + 7 : r;
}

function joffe(rd) {
  return ((Math.imul(rd, 613566757) + 0x94920000) | 0) >>> 29;
}

Math.imul で32bit乗算のオーバーフロー切り捨てが、>>> 29 で符号なしシフトが書けるので、u32演算の意味はJavaScriptでもそのまま表現できる。

計測結果はこの表で、1関数ずつ別プロセスで測った（理由は後述）。

実装	スループット (ns/op)	レイテンシ (ns/op)
((rd%7)+11)%7	0.90	5.67
分岐で補正 (rd+4)%7	34.0	39.4
Joffe範囲限定版	0.58	1.35

普通に書いた % 7 の0.90 ns/opをどう出しているのか、V8の最適化コードを --print-opt-code で覗くと、% 7 の位置に smull と msub が出てきた。
つまりTurboFanも、コンパイラと同じマジックナンバーによる除算をやっている。JITだからそのまま割り算しているだろう、という予想は外れた。
それでもJoffe版がスループットで1.6倍、レイテンシで4.2倍速かった。今回のV8の最適化コードにはNEONへの自動ベクトル化が見られなかったので、C側で効いていたベクトル化分の上乗せがなく、Cより差は小さい。

分岐で補正した書き方だけ極端に遅い

表の真ん中、分岐で補正した書き方だけが34 ns/opで、同じ意味の計算に普通の書き方の37倍かかっている。

原因はJavaScriptの -0 だった。
(rd + 4) % 7 は、rd + 4 が負の7の倍数のとき -0 を返す。JavaScriptの数値は仕様上すべてdoubleなので、0 と -0 は別の値として存在する。V8は小さい整数をSmiというポインタ埋め込みの内部表現で持つが、-0 はSmiにできなくて、ヒープ上のdoubleになる。
整数だと思って最適化したコードに -0 が混ざるたびに、型フィードバックが壊れて脱最適化（deopt。最適化コードを捨ててやり直すこと）が走る。--trace-deopt で見ると、実際に脱最適化と再最適化を延々と繰り返していた。

原因を絞り込むため、入力データを変えて同じ関数を測った。

入力データ	スループット (ns/op)
正負混在（-0 が出る）	34.0
正のみ	1.32
負を含むが -0 になる値を除外	3.28

-0 になる値は入力の7%程度しかないのに、そこで起きる脱最適化が全体を25倍遅くする。
Cの感覚で移植した「負なら+7」のイディオムは、JavaScriptでは剰余の書き方の差より二桁大きく速度を落としていた。

関数の並び順で数字が変わる

もうひとつ、結果より先に計測のやり方で問題が出た。
最初は1つのファイルで4実装を順番にベンチしていて、そのときは普通の %7 が0.9 ns/op、Joffe版が3.9 ns/opという数字だった。関数の順番を入れ替えると今度は普通の %7 が41 ns/opになった。

共通のベンチループに複数の関数を通すと、呼び出しサイトの型フィードバックが多態化して、後から来た関数がインライン化されないままだったり、前の関数向けの最適化コードごと脱最適化されたりする。
定数の書き方の差かと思って追いかけた4倍差も、順番を変えると消えた。
今回のように共通のベンチループへ複数の関数を渡す構成では、測る順番で結果が変わってしまう。だから上の表は、すべて1プロセス1関数に分けて測り直した数字だ。

CPythonでも同じ比較を回す

最後にCPythonを回した。Pythonの % は正の除数に対して常に非負を返すので、そもそも負数対応の追加コードがいらない。

def naive(rd):
    return (rd + 4) % 7

def joffe(rd):
    return ((rd * 613566757 + 2492596224) & 0xFFFFFFFF) >> 29

Pythonのintは多倍長整数なので、u32のオーバーフローを & 0xFFFFFFFF のマスクで自前再現する必要があり、手書き側の演算数はむしろ増える。

実装	ns/op（関数呼び出し）	ns/op（ループ内インライン）
(rd + 4) % 7	27.1	18.9
Joffe範囲限定版	70.8	63.1

手書きした方が3倍以上遅い。
CPythonでは % も * も「CPU命令1個」ではなくPyLongオブジェクトへの演算処理で、1演算あたり数ns〜十数nsかかる。普通の書き方は演算2個、手書きした方は演算4個で、しかも rd * 613566757 は56bit級の値になって多倍長の桁が増える。
CPU命令を削るという発想自体がCPythonでは成り立たなくて、演算の個数がそのまま速度差になる。

なおCPython 3.14には実験的JITがあるが、手元のPythonはJITが搭載されていないビルドだった。

処理系ごとの速度比

4つの処理系の結果を並べた。

処理系	普通の書き方に対するJoffe版の速度比	% 7 の最適化
clang -O2	3.2〜6.4倍	乗算とシフトに変換
rustc -O	1.9〜5.2倍	乗算とシフトに変換
V8 (TurboFan)	1.6〜4.2倍	乗算とシフトに変換
CPython 3.14	0.3倍（手書きした方が3倍遅い）	なし（そもそも対象外）

コンパイラもJITも % 7 単体はとっくに最適化していて、それでも手書きの方が1.6〜6.4倍速かった。入力は日数で範囲は±数十万年まで、エポックはずらしてよい、7日週は8日週として扱ってよい、と処理系が知り得ないことを決めて定数へ埋め込んでいるぶんの差になる。
CPythonだけは逆に、演算を2個から4個へ増やしたぶんそのまま遅くなった。