Почему 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 (год 0 = 1 г. до н.э.), а не эпохи 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 - это умные люди, которые сделали это по-своему, и, вероятно, знают немного большеС чем я занимаюсь, почему?

Answer 1

Запустил ваш код как код минимального значения y2 как 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

Возможно, это ответ

Answer 2

Это чисто предположение, но, возможно, у MINIX были требования, которые были важнее скорости выполнения, такие как простота, простота понимания и краткость? В конце концов, часть кода была напечатана в учебнике.

Answer 3

Ваш метод кажется надежным, но немного сложнее заставить его работать для EPOCH_YR = 1970, потому что вы находитесь в середине цикла на нескольких циклах.

Можете ли вы увидеть, есть ли у вас аналог для этого случая, и посмотреть, все ли еще лучше?

Вы, конечно, правы, что это спорный вопрос, следует ли, что реализация gmtime () можно использовать в любом коде высокопроизводительным. Это большая занятая работа, которую нужно выполнять в любых узких петлях.

Answer 4

Правильный подход.Вы определенно хотите пойти на O (1) алгоритм.Будет работать в календаре майя без шума.Проверьте последнюю строку: dayno ограничен значением 0..364, хотя в високосные годы он должен находиться в диапазоне 0..365Линия перед имеет аналогичный недостаток.