日付計算の定番アルゴリズムを、年の範囲を 1..9999 に限定して高速化する記事を3本書きました。
扱ったのは次の処理です。
- 年月日から曜日を求める
- 年月日をUnix epochからの通算日へ変換する
- 通算日を年月日へ戻す
共通する方針は、定数除算や剰余を乗算・シフト・小さなテーブルへ置き換えることです。
この記事では、それぞれの内容をざっと紹介します。
1. マジックナンバー化による高速な曜日計算
最初の記事では、Tomohiko Sakamotoの曜日計算を対象にしました。
通常のSakamoto式に含まれる /100、/400、% 7 を、年 1..9999 の範囲で次の形へ変換しています。
const uint32_t product = year * 5243u;
product >> 19; // year / 100
product >> 21; // year / 400
((value * 74899u) >> 16) & 7u; // value % 7
さらに月補正値をあらかじめ 74899 倍しておき、最終乗算の後へ加算を移しました。
Apple Silicon／Clangのインライン・バッチ処理では、通常のSakamoto実装より約30%高速になりました。
2. マジックナンバー化による高速な days_from_civil
次は、年月日をUnix epochからの通算日へ変換する days_from_civil です。基準にはHoward Hinnantのアルゴリズムを使いました。
年に関する項は、次の二つの積へまとめられます。
Math.imul(adjustedYear, 1_461) >>> 2;
const centuryProduct = Math.imul(adjustedYear, 5_243);
centuryProduct >>> 19; // adjustedYear / 100
centuryProduct >>> 21; // adjustedYear / 400
1461 = 4 * 365 + 1 を使い、
365 * year + floor(year / 4)
を一つの乗算とシフトへまとめています。
月項、日番号の補正、Unix epochのオフセットは12要素のテーブルへ畳み込みました。
Apple Silicon上の測定結果は次のとおりです。
| 環境 | Hinnant比の実行時間短縮 |
|---|---|
| Bun | 79.5% |
| Rust | 40.4% |
| C | 37.3% |
3. Julian mapとpacked tableによる高速な civil_from_days
最後は逆変換です。
civil date -- days_from_civil --> epoch day
civil date <-- civil_from_days --- epoch day
こちらは同じ式を逆向きに計算すればよいわけではありません。通算日から年、月、日を順に復元する必要があるため、最適化の構造もかなり異なります。
年の復元にはBen JoffeのJulian mapを使い、March-basedの年内日 0..365 から、年補正・月・日を366要素のテーブルで取得します。
MONTH_DAY[dayOfMarchYear] =
(Number(janOrFeb) << 9) | (month << 5) | day;
テーブルは Uint16Array で732 bytesです。year bumpもbit 9へ埋め込むことで、ホットパス上の比較と加算を削除しました。
Bunでは、範囲内で正しさを確認した上方丸めbinary64逆数と | 0 も使用しています。
const century = (q * INV_146097) | 0;
const julian = q + century * 3 + (century & 3);
const year = (julian * INV_1461) | 0;
const dayOfMarchYear = (julian - year * 1_461) >>> 2;
return year * 512 + MONTH_DAY[dayOfMarchYear];
Apple Silicon上の測定結果は次のとおりです。
| 環境 | Hinnant比の実行時間短縮 |
|---|---|
| Bun | 79.1% |
| Rust | 73.8% |
| C | 69.8% |
正しさについて
高速化では、入力範囲を限定していることが重要です。
- 年:
1..9999 - 月、日: 各関数で定義した範囲
-
civil_from_days:0001-01-01〜9999-12-31に対応するepoch day
曜日計算と days_from_civil は、年・月・日の3,719,628入力を基準実装と比較しました。civil_from_days は、対象となる3,652,059個のepoch dayを全数比較しています。TypeScript、Rust、Cで一致を確認しました。
一方、範囲を外れる入力へそのまま使えることは保証していません。
既知の技法を、限定範囲向けに組み合わせる
今回使ったstrength reduction、マジックナンバーによる定数除算、Sakamoto、Hinnant、Neri–Schneider、Ben Joffeのアルゴリズムは既知のものです。
新しい一般アルゴリズムを主張するというより、年 1..9999 という実用上よくある範囲へ限定し、既知の技法を短い実装へ組み合わせ、全数検証と実測を行ったものです。
また、最速性はCPU、コンパイラ、JIT、入力分布によって変わります。今回の結果はApple Silicon上の特定環境で、比較した実装の中では速かった、という位置づけです。
まとめ
3記事を並べると、同じグレゴリオ暦でも変換方向によって有効な最適化が違うことが分かります。
- 曜日計算:
/100、/400、% 7を共有積とbit抽出へ変換 -
days_from_civil: 年項を二つの積へまとめ、月とepoch補正を12要素テーブルへ格納 -
civil_from_days: Julian mapで年を復元し、年補正・月・日を366要素のpacked tableから取得
moment.jsと(極限まで)100%互換のmmnt.jsではこれらの高速化も取り込んでいます
一般的なユーザーにはあまり関係ありませんが、日付計算ライブラリに関心があれば参考にしてみてください