为什么gmtime被实现成这样？

Question

我偶然发现了Minix的gmtime函数源代码。我对计算自纪元以来的天数得出年份的部分很感兴趣。以下是该部分的核心代码：

http://www.raspberryginger.com/jbailey/minix/html/gmtime_8c-source.html

http://www.raspberryginger.com/jbailey/minix/html/loc__time_8h-source.html

#define EPOCH_YR 1970
#define LEAPYEAR(year) (!((year) % 4) && (((year) % 100) || !((year) % 400)))
#define YEARSIZE(year) (LEAPYEAR(year) ? 366 : 365)

int year = EPOCH_YR;

while (dayno >= YEARSIZE(year)) {
    dayno -= YEARSIZE(year);
    year++;
}

看起来算法的时间复杂度为O(n)，其中n是距离纪元的距离。此外，似乎必须为每一年单独计算LEAPYEAR-对于当前日期需要计算数十次，对于将来的日期需要计算更多次。我有一个类似的算法可以实现相同的功能（在这种情况下是从ISO-9601纪元（Year 0 = 1 BC）而不是UNIX纪元开始）：

#define CYCLE_1   365
#define CYCLE_4   (CYCLE_1   *  4 + 1)
#define CYCLE_100 (CYCLE_4   * 25 - 1)
#define CYCLE_400 (CYCLE_100 *  4 + 1)

year += 400 * (dayno / CYCLE_400)
dayno = dayno % CYCLE_400

year += 100 * (dayno / CYCLE_100)
dayno = dayno % CYCLE_100

year +=   4 * (dayno / CYCLE_4)
dayno = dayno % CYCLE_4

year +=   1 * (dayno / CYCLE_1)
dayno = dayno % CYCLE_1

这个操作对于任何日期都是O(1)，即使是在1970年附近的日期，看起来速度应该更快。

因此，假设Minix开发人员是聪明的人，他们按照自己的方式进行操作并且有充分的理由，而且可能比我更了解C语言，那么为什么呢？

- Thom Smith

---

看起来应该会更快。你需要考虑你的架构，以及像乘法这样的特定指令有多快，以及你的分支预测器有多好（大多数都非常好）。@jim mcnamara 有一些有趣的结果。 - BobbyShaftoe

Answer 1

我将您的代码作为y2 minix代码和y1 Solaris 9 v245运行，并获得了以下性能分析数据：

 %Time Seconds Cumsecs  #Calls   msec/call  Name
  79.1    0.34    0.34   36966      0.0092  _write
   7.0    0.03    0.37 1125566      0.0000  .rem
   7.0    0.03    0.40   36966      0.0008  _doprnt
   4.7    0.02    0.42 1817938      0.0000  _mcount
   2.3    0.01    0.43   36966      0.0003  y2
   0.0    0.00    0.43       4      0.      atexit
   0.0    0.00    0.43       1      0.      _exithandle
   0.0    0.00    0.43       1      0.      main
   0.0    0.00    0.43       1      0.      _fpsetsticky
   0.0    0.00    0.43       1      0.      _profil
   0.0    0.00    0.43   36966      0.0000  printf
   0.0    0.00    0.43  147864      0.0000  .div
   0.0    0.00    0.43   73932      0.0000  _ferror_unlocked
   0.0    0.00    0.43   36966      0.0000  memchr
   0.0    0.00    0.43       1      0.      _findbuf
   0.0    0.00    0.43       1      0.      _ioctl
   0.0    0.00    0.43       1      0.      _isatty
   0.0    0.00    0.43   73932      0.0000  _realbufend
   0.0    0.00    0.43   36966      0.0000  _xflsbuf
   0.0    0.00    0.43       1      0.      _setbufend
   0.0    0.00    0.43       1      0.      _setorientation
   0.0    0.00    0.43  137864      0.0000  _memcpy
   0.0    0.00    0.43       3      0.      ___errno
   0.0    0.00    0.43       1      0.      _fstat64
   0.0    0.00    0.43       1      0.      exit
   0.0    0.00    0.43   36966      0.0000  y1

也许这就是一个答案。

- jim mcnamara

---

循环实现似乎在0秒内运行，而取模实现在0.01秒内运行。 - Lefteris E

绝对需要进行基准测试。在看到这些结果之前，我本来会打赌询问者的代码更快。 - ryyker

Answer 2

这纯属猜测，但也许MINIX的要求比执行速度更重要，例如简单性、易理解性和简洁性？毕竟有些代码已经在教科书上打印出来了。

- bk1e

Answer 3

你的方法看起来很可靠，但是对于EPOCH_YR = 1970，要让它工作起来就有点困难了，因为你现在处于几个周期的中间。

你能否查看是否有相应的解决方案，并查看它是否仍然更好？

你当然是正确的，值得商榷的是，gmtime()实现是否应该用于任何高性能代码。这是在任何紧密循环中要做的大量繁琐工作。

- Cade Roux

---

只需将天数从0年到1970年的年数中减去即可。这将是一个常量，可以存储为另一个# define。 - Adam Shiemke

正如Adam所说，简单地减去偏移量就可以解决这个问题，尽管它会溢出32位时间戳。将纪元设置为公元2000年将解决这两个问题，需要在主要计算之前和之后进行一次额外的操作。如果有64位时间戳可用，ISO零年可能更好，因为它a）节省了一个操作，b）更明显，c）易于日历无关的星期几计算。另一方面，如果你被困在一个带有现代纪元的32位时间戳中，你可能会忘记100年和400年的周期，因为2000年已经是闰年，而1900年和2100年已经超出范围。 - Thom Smith

@Thom Smith，2000年的天数（约为730k）远远低于2^32。两个代码片段都不涉及秒数。 - Adam Shiemke

我剪掉了其他部分，它们在链接中。gmtime函数接受一个标准的UNIX时间戳，从中派生出dayno。 - Thom Smith

@Thom Smith：你可能会认为“ISO零年可能更好”，但在POSIX系统上的现有做法是将time_t重新定义为具有相同纪元的64位类型，因为这样可以使旧程序继续工作。 - caf

如果您有64位时间戳，那么两个时代的性能几乎相同，因此不应影响相关代码。 - Thom Smith

Answer 4

正确的方法。你肯定想要选择一个O(1)算法。它可以在玛雅日历中毫不费力地工作。检查最后一行：dayno被限制在0..364之间，尽管在闰年中需要范围为0..365。前面的一行也有类似的缺陷。

- frankencode