一种更快的星期几计算方法

# 更快的星期几计算方法 来源：https://www.benjoffe.com/fast-day-of-week **其他日期/时间相关文章：** - 文章 1：儒略映射（https://www.benjoffe.com/fast-date） - 文章 2：溢出安全性（32 位）（https://www.benjoffe.com/safe-date） - 文章 3：极速日期（64 位）（https://www.benjoffe.com/fast-date-64） - 文章 4：快速闰年计算（https://www.benjoffe.com/fast-leap-year） - **文章 5：快速星期几计算** - Smoital 系统——火星时间（https://www.benjoffe.com/smoitus） - Weekle——星期几猜谜游戏（https://www.benjoffe.com/weekle） ## *一系列超越编译器输出的快速模运算技术* 将*日期计数（“rata-die”）*转换为*星期几（“weekday”）*听起来是如此简单，似乎没什么可说的。但事实上，深入探究后会发现这是一个异常复杂的问题。 本文将介绍一系列*极速*函数来解决此问题，针对不同场景（吞吐量与延迟、不同平台等）进行优化。每个函数都优于现有解决方案，且许多函数的延迟仅为一次乘法加上两个时钟周期。一个令人惊喜的结果是：星期几可以按 ISO 格式（\[1..7\] 而非 \[0..6\]）计算，使用完全相同的指令，仅调整常数（且速度无损失）。 为让您感受这种疯狂，这里重点介绍我最喜欢的函数。这个看似怪异的 3 指令序列（加上常量加载）在**完整有符号 32 位范围**内均有效*（它可能不是本文中延迟最低的全范围算法，但在 x86 平台上具有最高**吞吐量**）*： Unix 星期几 \[0..6\] ISO 星期几 \[1..7\] **给定：`input`*（rd = 有符号 32 位 Unix 日期计数）*；计算`weekday [0..6]`：** 1. `mov eax, 613566756` u32 M = (1 << 32) / 7 2. `imul ecx rd * M` 3. `lea eax, [eax-1828716544+edx*4]` u32 r = a + 4 * b + (Z = 0x93000000) 4. `shr eax, 29` weekday = r >> 29 **您无需事先了解汇编知识即可理解本文。** 读完本文后，您将明白上述代码为何有效。 上述函数如何产生所需输出的可视化图示。第 3 行的常数充当旋转角度。 本文面向对底层位操作感兴趣的人、优化高性能日期库/数据库引擎的工程师、编译器开发者以及广义上的“极客”。此处使用的技术可**推广**到`x % (2^N - 1)`，并为**其他除数**（如`x % 24`和`x % 60`）引入了新的快速模运算技术——适用于时间计算。 如果您只是想复制粘贴代码并在库中进行基准测试，可直接跳转至“函数浏览器（https://www.benjoffe.com/fast-day-of-week#fn）”，其中提供了本页所有代码示例的 C++ 可复制版本。 **最快算法的近似相对速度** 在 AMD Ryzen 9 和 Apple M4 Pro 处理器上测试（数值越小 = 越快）。具体结果请参阅基准测试部分（https://www.benjoffe.com/fast-day-of-week#benchmarks）。 **其他算法***（取双模、Rust: rem_euclid、Hinnant）* **~1.5–3+ 倍慢** **文章章节：** - 简单方法（https://www.benjoffe.com/fast-day-of-week#simple） - Hinnant 算法（https://www.benjoffe.com/fast-day-of-week#hinnant） - Neri 算法（https://www.benjoffe.com/fast-day-of-week#neri） - 不合理的极速乘-加-移位算法（https://www.benjoffe.com/fast-day-of-week#unreasonable） - 通过 64 位扩展实现快速全范围计算（https://www.benjoffe.com/fast-day-of-week#widen） - 快速全范围计算（变体 1：*移位*）（https://www.benjoffe.com/fast-day-of-week#v1） - 快速全范围计算（变体 2：*双乘法*）（https://www.benjoffe.com/fast-day-of-week#v2） - 快速全范围计算（变体 3：*高低位组合*）（https://www.benjoffe.com/fast-day-of-week#v3） - **函数浏览器**（https://www.benjoffe.com/fast-day-of-week#fn） - 推广（https://www.benjoffe.com/fast-day-of-week#generalisation） - 结语（https://www.benjoffe.com/fast-day-of-week#closing） - 附录 A. 基准测试结果（https://www.benjoffe.com/fast-day-of-week#benchmarks） - 附录 B. 基于 2 的幂填充的模运算证明（https://www.benjoffe.com/fast-day-of-week#proof） ## 简单方法 深度链接（https://www.benjoffe.com/fast-day-of-week#simple） 给定：`rd = rata-die`*（日期计数，有符号 32 位整数）*，纪元为`1970-01-01` = 星期四（`4`），则： **双取模法（支持有符号“%”的语言，如 C/C++）** 1. `weekday = ((rd % 7) + 7 + 4) % 7` **支持正向取模的语言（如 Rust）** 1. `weekday = (rd + 4) POSMOD 7` — 其中：`weekday ∈ [0..6]`*（0 = 星期日）* 对于大多数非库代码（维护性比微优化更重要时），我会推荐此方法。注意 Rust 示例在最高 4 个输入值时会溢出，但假设我们不关心这些情况。 添加`4`（或`11 = 7 + 4`）是因为 Unix 纪元`1970-01-01`是*星期四*。如果您对星期几的编号不同，或使用其他纪元，此值可能不同。 这些“简单方法”能完成任务，但速度相当慢，即使是 Rust 的正向取模函数（`rem_euclid`）也如此。其编译后的伪代码如下： **Rust 的 rem_euclid（编译后伪代码等效） 在 Godbolt 上查看（https://godbolt.org/z/qoexEsz6b）** 1. `i32 a = (i64(rd + 4) * -1840700269) >> 32` 2. `i32 b = rd + 4 + a` 3. `i32 c = (b >> 2) + (u32(b) >> 31)` 4. `i32 d = rd - c * 7` 5. `i32 e = d + 4` 6. `u32 weekday = e >= 0 ? e : d + 11` 步骤比您预期的多得多，对吧？ ## Hinnant 算法 深度链接（https://www.benjoffe.com/fast-day-of-week#hinnant） Howard Hinnant 的技术（2014 年）被许多日期库采用（参见原文（https://howardhinnant.github.io/date_algorithms.html#weekday_from_days））。 **Hinnant 算法（与位宽无关）范围：INT32_MIN → INT32_MAX − 4** 1. `weekday = rd >= -4 ? (rd + 4) % 7` 2. `: (rd + 5) % 7 + 6` 此方法似乎设计为简洁且灵活。它是本文后续中唯一不依赖符号转换或溢出，且不特定位宽的算法。其逻辑在 8 位到 64 位系统上均相同。 Hinnant 在文中指出，此算法覆盖完整的有符号 32 位范围，除了最高的 4 个输入值（在 C/C++ 中，这些极端值会导致未定义行为，相当于未来超过 580 万年）。实际上，在 2 的补码机器上，这些值通常仍有效，但编译器不保证这一点。 尽管在开头柱状图中未显示为*极速*，但该算法在 Raspberry Pi Zero（以及可能更旧的芯片）上运行极快。 ## Neri 算法 深度链接（https://www.benjoffe.com/fast-day-of-week#neri） 一如既往，Cassio Neri 的作品是现代黄金标准。2024 年，Neri 发表了一个非常简洁的全范围解决方案（参见帖子（https://lnkd.in/gwN46bWd））： **Cassio Neri：32 位版本（范围：完整有符号 32 位）** 1. `weekday = (u32(rd) + (rd >= 0 ? 4 : 0)) % 7` **Cassio Neri：64 位版本（范围：完整有符号 64 位）** 1. `weekday = (u64(rd) + (rd >= 0 ? 4 : -5)) % 7` 如果您需要一个相当快、全范围且不太底层的函数，那么这就是您的选择。 这里避免溢出的关键在于在操作前将有符号转换为无符号。有趣的是，在 32 位版本中，由于性质：`2^32 % 7 = 4`，负数时会加零，因此`4`的加法已内置。注意，如果此值非零（例如，您不将星期日视为`0`），速度也不会变慢。要计算不同位宽下的第二个常数，请使用：`- ((3 + 2^BIT_WIDTH) % 7)` *看起来应该能尽可能快了，对吧？* 要加速，我们需要查看汇编。GCC 和 Clang 生成的汇编计算如下： **Neri，32 位（编译后伪代码等效） 在 Godbolt 上查看（https://godbolt.org/z/fG6EhzvP5）** 1. `u32 a = u32(rd) + (rd >= 0 ? 4 : 0)` 2. `u32 b = ((u64) a * 613566757) >> 32` 3. `u32 c = (((a - b) >> 1) + b) >> 2` 4. `u32 weekday = a - c * 7` 注意第 3 行包含四个串行依赖操作，仅用于将初始近似值`a / 7`修正。需要此类修正项是因为`7`是*不友好除数*，其魔法倒数乘数需要超过 32 位，无法放入 32 位寄存器。 有更快的方法，使用 ridiculousfish 在 2011 年提出的“libdivide”技术（https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html）。它通过饱和增量输入并使用向下取整乘数消除了整个修正行。我们可以使用它，对我而言测量结果约快 10%，但还有更快的方法，我们将首先通过缩小范围要求来探索... ## 不合理的极速*乘-加-移位*算法 深度链接（https://www.benjoffe.com/fast-day-of-week#unreasonable） 事实证明，我们可以仅用一次乘法、加法和右移计算受限但实用范围内的星期几： Unix 星期几 \[0..6\] ISO 星期几 \[1..7\] **32 位版本（受限范围）输入范围：`-89,434,796`到`89,522,175`有效日期：`-242,895-11-06 (星期一: 1)`到`247,073-05-23 (星期五: 5)`** 1. `const u32 M = (1 << 32) / 7 + 1` 2. `const u32 Z = 0x94920000` 3. `weekday = (u32(rd) * M + Z) >> 29` *C++ 版本请参见函数浏览器中的 #fn=32unix_narrow（https://www.benjoffe.com/fast-day-of-week#fn=32unix_narrow）。* 仅三个操作。显然这将运行得非常快，但它究竟是如何工作的？ 左侧函数产生所需输出的可视化图示。常数“*Z*”充当旋转角度。 模运算通常需要更多步骤。我们能用如此少操作的原因是`7`是梅森数，即形式为：`2^N − 1`。对于此类数字，我们可以利用恒等式：`N % 7 = floor(N * 8 / 7) % 8`（参见附录 B（https://www.benjoffe.com/fast-day-of-week#proof）查看此等式的证明）。 然后我们通过乘以`~1.142857...`（通过单次乘法和右移近似）来实现`* 8 / 7`。通常乘法-移位取高位，但我们取低位，确保右移量恰好比寄存器大小少 3。最终的`% 8`则免费获得，因为只剩下 3 位。 在右移前将`Z`的值加到结果中，我们有效地旋转输出值以匹配 Unix 纪元为星期四。`Z = 0x90000000`会将其旋转为 ISO 格式 \[1..7\]，输入范围在`±89,478,489`（32 位空间的 1/24）内平衡。对于 Unix 格式 \[0..6\] 变体，我选择`Z = 0x94920000`，这给出*几乎但不完美平衡*的范围，但通过低两个字节为零在 ARM 上带来轻微速度优势。 代码右侧的图示直观展示了此乘数如何打击圆的 8 个不同段（高 3 位），每个周期跳过一个值。箭头轻微“扇出”；这代表我们的乘数只是`2^29 * 8 / 7`的近似。最终这种扇出导致错误返回值，因此范围受限。 此算法在任何地方都超快，但在 ARM 上特别快，因为乘法和加法融合为单个`MADD`汇编操作。此外，ARM 上许多操作允许融合右移，因此下游代码也很可能与`\>> 29`项融合。**这意味着在实践中，它可能编译为有效的单个 ARM 汇编操作！** 此技术有效性的替代可视化指南如下表所示，您可以看到在 Unix 模式下每个周期跳过输出值`111 (7)`，在 ISO 模式下跳过`000`： Unix 星期几 \[0..6\] ISO 星期几 \[1..7\] 如果您的日期库仅需支持小于 ±242,000 年的范围，那么您可能可以直接使用上述技术。一个例子是 Rust Jiff 日期/时间库（https://github.com/BurntSushi/jiff），支持 ±10,000 年范围。采用（https://github.com/BurntSushi/jiff/pull/591）此算法为上游函数（如`nth_weekday_of_month`）带来了 40% 的速度提升（此前使用 Rust 的`rem_euclid`函数）。 本文剩余部分将旨在为全范围日期库实现类似速度。 ### 通过 64 位扩展实现快速全范围计算 深度链接（https://www.benjoffe.com/fast-day-of-week#widen） 扩展到完整 32 位输入域的最简单方法是扩展至 64 位： Unix 星期几 \[0..6\] ISO 星期几 \[1..7\] **64 位扩展版本输入范围：完整 32 位：`-2^31`到`2^31-1`有效日期：`-5,877,641-06-23 (星期二: 2)`到`5,881,580-07-11 (星期五: 5)`** 1. `const u64 M = 0x2492492493000000` 2. `const u64 Z = 0x9400 << 48` 3. `weekday = (u64(rd) * M + Z) >> 61` *C++ 版本请参见函数浏览器中的 #fn=32unix_widen（https://www.benjoffe.com/fast-day-of-week#fn=32unix_widen）。* 左侧函数产生所需输出的可视化图示。常数“*Z*”充当旋转角度。 **64 位扩展版本**调整了乘数，我使用`ceil(2^40 / 7) × 2^24`代替了`ceil(2^64 / 7)`。同样，低位被清零以便更紧凑的 ARM 汇编：通过试错找到所需最小字节数。 注意圆图中的箭头不再扇出？这是由于此技术提供的额外精度位。 *函数浏览器*有一个针对 64 位输入调整的变体（*参见 #fn=64unix_narrow（https://www.benjoffe.com/fast-day-of-week#fn=64unix_narrow）*），其中使用未舍入的乘数以获得更宽范围，覆盖超过一千万亿年（*这对任何人都足够了*）。 ### “不合理的极速” - 先前工作 在为本文研究时，我发现我并非第一个认识到此梅森数技巧的人。类似技术最早出现在*《Hacker's Delight, 第二版》*（§10–20，*Remainder by Multiplication and Shifting Right*）中。书中有如下示例： **《Hacker's Delight》 - 无符号 N mod 7 技术（部分范围）在无符号 32 位范围的 3.125% 内有效给定：`x`整数`[0 .. 134,217,734]`——则：** 1. `u32 n = u32(x * 613566756) >> 29` 2. `x_mod_7 = n & (i32(n - 7) >> 31)` 书中在所有情况下使用向下取整乘数，而非向上取整乘数。不仅此乘数在许多情况下（包括 mod 7）给出更差范围，而且它还需要第 2 行的修正，这消除了该技术的大部分速度优势。 不过我很高兴遇到这本书，因为我学到了以下扩展到全范围的技术： **《Hacker's Delight》 - 无符号 N mod 7 技术（全范围）给定：`x`*（无符号 32 位整数）*——则：** 1. `u32 n = u32(x * 613566756 + (x >> 1) + (x >> 4)) >> 29` 2. `x_mod_7 = n & (i32(n - 7) >> 31)` 高亮的修正项与“理想”乘数`2^32 / 7 = 613566756.5714...`的小数部分相关。此小数部分恰好是`4/7`。修正`\(x >> 1) + (x >> 4) = 1/2 + 1/16 = 0.5625`近似“理想”缺口。 我们将利用这些修正项，但不再使用第 2 行的修正映射，而是...