マジックナンバー化による高速な days_from_civil
年月日をUnix epochからの通算日へ変換する方法として、Howard Hinnantの days_from_civil がよく知られています。
この記事では対象年を1年から9999年に限定し、days_from_civil に含まれる /400、/100、/4、/5 を、互いに独立した二つの32-bit整数乗算、シフト、12要素のテーブルに置き換えます。
Apple Silicon上でBun、Rust、Cのインライン・バッチ処理を測定したところ、通常のHinnant実装に対して、今回の環境では約37〜80%の実行時間短縮を確認しました。
最初に完成した実装を示し、その後で 1461 が平年項と4年項をまとめられる理由、定数 5243 が /100 と /400 の両方に使える理由、epochオフセットを月テーブルへ畳み込む方法を説明します。
実装例
前提は次のとおりです。
year:1..9999month:0..11（0が1月）day:1..31
この関数は日付の妥当性を検証しません。たとえば2月31日も計算できます。
TypeScript
const EPOCH_MONTH_TABLE = new Int32Array([
-719_163, -719_132, -719_469, -719_438,
-719_408, -719_377, -719_347, -719_316,
-719_285, -719_255, -719_224, -719_194,
]);
/** Returns days since 1970-01-01. */
export function ymdToEpochDays(
year: number,
month: number,
day: number,
): number {
const adjustedYear = year - (month <= 1 ? 1 : 0);
const centuryProduct = Math.imul(adjustedYear, 5_243);
return (
(Math.imul(adjustedYear, 1_461) >>> 2) -
(centuryProduct >>> 19) +
(centuryProduct >>> 21) +
EPOCH_MONTH_TABLE[month] +
day
);
}TypeScriptでは32-bit整数乗算を明示するために Math.imul を使います。対象値は常に非負なので、右シフトには符号なしの >>> を使用しています。
Rust
const EPOCH_MONTH_TABLE: [i32; 12] = [
-719_163, -719_132, -719_469, -719_438,
-719_408, -719_377, -719_347, -719_316,
-719_285, -719_255, -719_224, -719_194,
];
/// Returns days since 1970-01-01.
///
/// Preconditions:
/// - year: 1..=9999
/// - month: 0..=11
/// - day: 1..=31
#[inline]
pub fn ymd_to_epoch_days(year: u32, month: u32, day: u32) -> i32 {
let adjusted_year = year - u32::from(month <= 1);
let century_product = adjusted_year * 5_243;
((adjusted_year * 1_461) >> 2) as i32
- (century_product >> 19) as i32
+ (century_product >> 21) as i32
+ EPOCH_MONTH_TABLE[month as usize]
+ day as i32
}C
#include <stdint.h>
/*
* Returns days since 1970-01-01.
*
* Preconditions:
* - year: 1..9999
* - month: 0..11
* - day: 1..31
*/
static inline int32_t ymd_to_epoch_days(
uint32_t year,
uint32_t month,
uint32_t day
) {
static const int32_t epoch_month_table[12] = {
-719163, -719132, -719469, -719438,
-719408, -719377, -719347, -719316,
-719285, -719255, -719224, -719194
};
const uint32_t adjusted_year = year - (month <= 1u);
const uint32_t century_product = adjusted_year * 5243u;
return (int32_t)((adjusted_year * 1461u) >> 2)
- (int32_t)(century_product >> 19)
+ (int32_t)(century_product >> 21)
+ epoch_month_table[month]
+ (int32_t)day;
}通常の days_from_civil
Howard Hinnantの実装を、0始まりの月へ合わせて書くと次のようになります。
function daysFromCivil(year: number, month: number, day: number): number {
year -= month <= 1 ? 1 : 0;
const era = Math.floor(year / 400);
const yearOfEra = year - era * 400;
const marchMonth = month + (month > 1 ? -2 : 10);
const dayOfYear =
Math.floor((153 * marchMonth + 2) / 5) + day - 1;
const dayOfEra =
yearOfEra * 365 +
Math.floor(yearOfEra / 4) -
Math.floor(yearOfEra / 100) +
dayOfYear;
return era * 146_097 + dayOfEra - 719_468;
}1月と2月を前年の末尾として扱うことで、うるう日を計算年の最後へ移します。その後、400年周期、周期内の年、3月から数えた年内日へ分解します。
今回の変形
最適化は大きく三つです。
まず、平年の日数と /4 のうるう年項をまとめます。
Math.imul(adjustedYear, 1_461) >>> 2次に、一度の乗算から /100 と /400 の両方を取得します。
const product = Math.imul(adjustedYear, 5_243);
product >>> 19; // adjustedYear / 100
product >>> 21; // adjustedYear / 400最後に、月項、-1、Unix epochオフセットを一つのテーブルへ畳み込みます。月初までの日数は12通りしかないため、(153 * month + 2) / 5 も同時にテーブルへ置き換えられます。
const EPOCH_MONTH_TABLE = new Int32Array([
-719_163, -719_132, -719_469, -719_438,
-719_408, -719_377, -719_347, -719_316,
-719_285, -719_255, -719_224, -719_194,
]);365日項と4年項を一つにする
年に関する先頭部分は次の形です。
365 * adjustedYear + floor(adjustedYear / 4)1461 = 4 * 365 + 1 なので、
floor(1461 * adjustedYear / 4)
= 365 * adjustedYear + floor(adjustedYear / 4)となります。入力は非負なので、4除算は符号なし右シフトにできます。
Math.imul(adjustedYear, 1_461) >>> 2これにより、乗算、独立したシフト、その加算を、一つの乗算とシフトへ置き換えられます。
epochオフセットを月テーブルへ畳み込む
元の式の末尾は次の形です。
DOY_TABLE[month] + day - 1 - 719468月ごとに変わらない定数部分をあらかじめ計算します。
EPOCH_MONTH_TABLE[month]
= DOY_TABLE[month] - 719469実行時の末尾は次だけになります。
EPOCH_MONTH_TABLE[month] + dayたとえば1月は 306 - 719469 = -719163 です。テーブルの大きさは48バイトのままで、格納する値だけが変わります。
なぜ 5243 で100除算できるのか
1月と2月の調整後も、年は次の範囲です。
0 <= adjustedYear <= 9999少し広く adjustedYear <= 9999 として証明します。
adjustedYear = 100q + r
0 <= r < 100また、
5243 * 100
= 524300
= 2^19 + 12なので、
5243 * adjustedYear
= 2^19 * q + 12q + 5243rです。対象範囲では q <= 99、r <= 99 であり、余分な部分の最大値は、
12 * 99 + 5243 * 99
= 520245
< 2^19となります。19ビット目への桁上がりがないため、
(Math.imul(adjustedYear, 5243) >>> 19)は対象範囲で常に floor(adjustedYear / 100) と一致します。
同じ積で400除算できる理由
今度は、
adjustedYear = 400q + r
0 <= r < 400とします。
5243 * 400
= 2097200
= 2^21 + 48なので、
5243 * adjustedYear
= 2^21 * q + 48q + 5243rです。q <= 24、r <= 399 より、余分な部分は最大でも、
48 * 24 + 5243 * 399
= 2093109
< 2^21です。したがって、
(Math.imul(adjustedYear, 5243) >>> 21)は対象範囲で常に floor(adjustedYear / 400) と一致します。
以上から、一度の乗算結果を共有できます。
const product = Math.imul(adjustedYear, 5243);
const century = product >>> 19;
const era = product >>> 21;月の除算をテーブルへ置き換える
March-based calendarで使われる月項は次の式です。
floor((153 * marchMonth + 2) / 5)marchMonth は 0..11 の12値しか取りません。元の0始まり月へ対応させて展開すると、
Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
306 337 0 31 61 92 122 153 184 214 245 275です。
このテーブルにより、月の分岐、乗算、加算、/5 を一つのテーブル読み出しへ置き換えられます。最終実装ではさらに各値から 719469 を引き、Unix epochオフセットと日番号の補正も同じテーブルへ畳み込んでいます。
テーブルは48バイトです。一般的なPCでは小さいですが、cold cache、コードサイズ、bounds check、JITの扱いによって算術式との性能関係は変わります。
32-bit整数の範囲
広い上限 9999 を使った二つの積の最大値は、
9999 * 5243
= 52424757
< 2^31
9999 * 1461
= 14608539
< 2^31です。したがって、TypeScriptの Math.imul で符号付き32-bitの折り返しは発生しません。
その他の中間値も32-bit整数へ十分収まります。最終結果は、指定された入力集合で次の範囲でした。
-719162 <= result <= 2932896全入力での検証
対象となるすべての入力について、通常のHinnant実装と比較しました。
for (let year = 1; year <= 9_999; year++) {
for (let month = 0; month < 12; month++) {
for (let day = 1; day <= 31; day++) {
const expected = daysFromCivil(year, month, day);
const actual = ymdToEpochDays(year, month, day);
if (actual !== expected) {
throw new Error(
`mismatch: ${year}-${month}-${day}: ` +
`${actual} !== ${expected}`,
);
}
}
}
}比較した入力数は、
9999 * 12 * 31
= 3,719,628です。TypeScript、Rust、Cの各実装で全件一致しました。
day は各月の実際の日数によらず31まで検証しています。そのため、2月31日のような実在しない日付も含まれます。関数は入力を拒否せず、通算日として連続的に計算します。実在する日付かどうかの検証は呼び出し側の責務です。
ベンチマーク
Apple Silicon ARM64上で、事前生成した 2^20 件の年月日を32回処理しました。入力位置はラウンドごとに回転させ、同一ループの巻き上げを防いでいます。
入力は次の範囲から決定的な疑似乱数で生成しました。
- 年:
1..9999 - 月:
0..11 - 日:
1..28
7回測定した最小値を採用しています。コンパイル・実行条件は次のとおりです。
Bun 1.4.0
rustc 1.96.0 -C opt-level=3 -C target-cpu=native
Apple clang 21.0.0 -O3 -march=native結果は次のとおりでした。
| 環境 | 通常のHinnant | 今回の限定範囲版 | 時間短縮 | スループット |
|---|---|---|---|---|
| Bun | 14.738 ns/件 | 3.018 ns/件 | 79.5% | 4.88倍 |
| Rust | 2.001 ns/件 | 1.192 ns/件 | 40.4% | 1.68倍 |
| C | 1.923 ns/件 | 1.205 ns/件 | 37.3% | 1.60倍 |
Bunでは、通常の浮動小数点除算と Math.floor を Math.imul とシフトへ置き換える効果が特に大きく出ました。
CとRustのコンパイラは定数除算をもともと乗算とシフトへ変換できます。それでも、365日項と /4 をまとめ、一つの積を /100 と /400 に共有し、残りの定数を月テーブルへ移した限定範囲版が、この環境では約37〜40%高速でした。
ただし、これは特定のCPU、コンパイラ、JIT、入力分布に対する結果です。Intel x86-64、別世代のApple Silicon、Node.js/V8、ブラウザ、異なるRust/Clangバージョンで同じ差になるとは限りません。
先行研究と今回の位置づけ
この実装はHoward Hinnantの days_from_civil を基礎にしています。また、整数の定数除算を乗算とシフトへ置き換えるstrength reductionは既知の技法です。
5243 による、0以上9999以下の整数の100除算も既知です。
(value * 5243) >> 19今回の構成は、先の記事「マジックナンバー化による高速な曜日計算」で使用した限定範囲向けの共有積を、days_from_civil へ展開したものです。
ポイントは次の組み合わせです。
- 同じ積
adjustedYear * 5243から/100と/400を取得する 365 * adjustedYear + floor(adjustedYear / 4)をfloor(1461 * adjustedYear / 4)にまとめる- March-basedの月項を、epochオフセットも含む12要素テーブルへ置き換える
- JavaScriptでは
Math.imulと符号なしシフトを明示する - 年を
1..9999に限定し、32-bit範囲内で完結させる
NeriとSchneiderはEuclidean affine functionとして、Gregorian calendar変換の乗算・シフト化と依存鎖短縮を体系的に扱っています。したがって、構成要素や一般的な最適化方針を新しいものとして主張するものではありません。
一方、年1〜9999の days_from_civil に対して、1461 の年積、/100 と /400 を共有する 5243 の積、epoch補正済み月テーブルを組み合わせる同一構成については、調査した公開実装の範囲では確認できませんでした。
これは、あらゆるCPU、言語、式の形の中で最速または最適であることを意味しません。対象範囲と実行環境を固定した高速化です。
逆変換について
この記事が扱う days_from_civil は、年月日を連続した通算日へ変換します。逆向きの変換は通常 civil_from_days と呼ばれます。
civil date -- days_from_civil --> serial day
civil date <-- civil_from_days --- serial day両者は逆関数ですが、最適化の構造はかなり異なります。civil_from_days は一つの整数からera、年、月、日を復元する必要があり、使う除算、補正、マジックナンバーも異なります。そのため、別の記事として扱うのが適切です。
まとめ
年を1〜9999に限定することで、Hinnant型 days_from_civil の定数除算を、互いに独立した二つの乗算とシフトへ置き換えられました。
中心となる変換は次の二つです。
Math.imul(adjustedYear, 1_461) >>> 2;
const centuryProduct = Math.imul(adjustedYear, 5_243);
centuryProduct >>> 19; // adjustedYear / 100
centuryProduct >>> 21; // adjustedYear / 400EPOCH_MONTH_TABLE[month] + day;Apple Silicon上の今回の測定では、通常のHinnant実装より、Bunで約80%、RustとCで約37〜40%実行時間を短縮しました。
一般的なアプリケーションでは、読みやすく広い年範囲を扱える通常の days_from_civil で十分です。今回の実装は、年月日変換がホットパスにあり、入力年の範囲が明確で、対象環境で性能差を実測できる場合に向いています。
参考資料
- Howard Hinnant, chrono-Compatible Low-Level Date Algorithms
- Cassio Neri and Lorenz Schneider, Euclidean Affine Functions and Applications to Calendar Algorithms
- Cassio Neri, EAF supplementary material
- マジックナンバー化による高速な曜日計算