¿Por qué se implementa gmtime de esta manera?

Question

Me encontré en la fuente de la función gmtime de Minix. Me interesó el bit que calculó el número de años desde la época. Aquí son las tripas de que bits:

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++; 
} 

Parece que el algoritmo es O (n), donde n es la distancia desde la época. Además, parece que LEAPYEAR se debe calcular por separado para cada año – docenas de veces para las fechas actuales y muchas más para fechas muy lejanas en el futuro. Yo tenía el siguiente algoritmo para hacer lo mismo (en este caso desde la época ISO-9601 (año 0 = 1 antes de Cristo) en lugar de Unix Epoch):

#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 

Esto se ejecuta en O (1) para cualquier fecha , y parece que debería ser más rápido incluso para fechas razonablemente cercanas a 1970.

Entonces, suponiendo que los desarrolladores de Minix sean Smart People que lo hicieron por su Reason, y probablemente conozcan un poco más sobre C que yo , ¿por qué?

Answer 1

Esto es pura especulación, pero quizás MINIX tenían requisitos que eran más importante que la velocidad de ejecución, como la simplicidad, la facilidad de comprensión y la concisión? Parte del código fue impreso en un libro de texto, después de todo.

Answer 2

Su método parece correcto, pero es un poco más difícil hacer que funcione para EPOCH_YR = 1970 porque ahora está a mitad de ciclo en varios ciclos.

¿Puedes ver si tienes un equivalente para ese caso y ver si aún es mejor?

Sin duda tiene razón en que es discutible si la implementación de gmtime() debe usarse en cualquier código de alto rendimiento. Eso es mucho trabajo ocupado para hacer en cualquier bucle apretado.

Answer 3

Ran su código como código y2 Minix como y1 Solaris 9 V245 & obtuvo estos datos de perfiles:

%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 

Tal vez es una respuesta

Answer 4

Enfoque correcto. Definitivamente quieres ir por un O (1) algo. Trabajaría en el calendario maya sin preámbulos. Verifique la última línea: dayno está limitado a 0..364, aunque en los años bisiestos debe ser de 0..365. La línea anterior tiene un defecto similar.