以下是三条判断闰年的指令: 1. 如果年份能被 4 整除但不能被 100 整除,那么这一年是闰年。 2. 如果年份能被 400 整除,那么这一年也是闰年。 3. 除了上述两种情况,其他年份都不是闰年。

主要观点:通过特定的代码可以用约 3 条 CPU 指令检查 0 ≤ y ≤ 102499 的年份是否为闰年,介绍了优化标准闰年检查方法、寻找位操作方法及扩展到其他位宽等内容,并进行了基准测试。
关键信息:

  • 标准闰年检查方法:通过判断年份对 4、100、400 的余数来确定是否为闰年。
  • 优化方法:将模运算替换为位掩码,如用 (y % 25)!= 0 替换 (y % 100)!= 0,用 (y % 16) == 0 替换 (y % 400) == 0,还利用特定的乘法和常量来降低模运算的开销。
  • 位操作方法:通过 ((y * f) & m) <= t 的形式,利用 z3 求解器找到合适的常量,实现快速判断闰年,其原理是通过对不同位范围的比较来统一多个条件。
  • 扩展到其他位宽:通过搜索合适的常量来扩展到 64 位,找到的最佳常量在 64 位下能正确判断到 y = 5965232499 的年份。
  • 基准测试:在 i7 - 8700K 上测试不同闰年检查函数的性能,is_leap_year_fast 比标准实现在随机数据上快 3.8 倍,在可预测输入上慢约 6%。
    重要细节:
  • 给出了各种优化和位操作方法的原理及相关数学计算,如乘法常量的来源、不同条件下对年份的判断等。
  • 解释了基准测试中出现的一些奇怪现象,如 is_leap_year2 在随机情况下比 is_leap_year 慢,is_leap_year3 在随机数据下比固定值慢等。
  • 提到若要完全证明替换现有实现的合理性,需要有包含闰年检查子例程的实际数据基准测试。
阅读 58
0 条评论