Perché gmtime è implementato in questo modo?

Question

Mi sono imbattuto nel sorgente per la funzione gmtime di Minix. Mi interessava il bit che calcolava il numero dell'anno da giorni a partire dall'epoca. Qui ci sono le budella di quel po ':

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

Sembra che l'algoritmo è O (n), dove n è la distanza dal dell'epoca. Inoltre, sembra che LEAPYEAR debba essere calcolato separatamente per ogni anno – decine di volte per le date attuali e molte altre per date lontane nel futuro. Ho avuto il seguente algoritmo per fare la stessa cosa (in questo caso dall'epoca ISO-9601 (anno 0 = 1 aC), piuttosto che UNIX epoca):

#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 

Questo viene eseguito in O (1) per qualsiasi data e sembra che dovrebbe essere più veloce anche per date ragionevolmente vicine al 1970.

Quindi, partendo dal presupposto che gli sviluppatori Minix sono persone intelligenti che hanno fatto a modo loro un motivo, e probabilmente conoscono un po 'più di C rispetto a me , perché?

Answer 1

Questa è pura speculazione, ma forse MINIX aveva i requisiti che sono stati più importante della velocità di esecuzione, come semplicità, facilità di comprensione e concisione? Parte del codice era stampato in un libro di testo, dopotutto.

Answer 2

Il tuo metodo sembra valido, ma è un po 'più difficile farlo funzionare per EPOCH_YR = 1970 perché ora sei a metà ciclo su più cicli.

Puoi vedere se hai un equivalente per quel caso e vedere se è ancora meglio?

Hai certamente ragione che è discutibile se tale implementazione gmtime() debba essere utilizzata in qualsiasi codice ad alte prestazioni. Questo è un lavoro molto impegnativo da fare in tutti i loop stretti.

Answer 3

Ran il codice come codice di y2 Minix come Y1 Solaris 9 V245 & ottenuto questi dati profiler:

%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 

Forse è una risposta

Answer 4

Approccio corretto. Sicuramente vuoi andare per un algo O (1). Lavorerebbe nel calendario Maya senza indugi. Controlla l'ultima riga: dayno è limitato a 0,364, anche se negli anni bisestili deve essere pari a 0,365. La linea prima ha un difetto simile.