Why is gmtime implemented this way?

Question

I accidentally came across a source for the minix gmtime function. I was interested in a bit that counted a year from the days from the era. Here is the courage of this bit:

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

It seems that the algorithm is O (n), where n is the distance from the era. In addition, it seems that LEAPYEAR should be calculated separately for each year; dozens of times for current dates and much more for dates far in the future. I had the following algorithm to do the same (in this case, from the ISO-9601 era (year 0 = 1 BC), and not from the UNIX era):

 #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 

This is done in O (1) for any date and looks as if it should be faster even for dates close to 1970.

So, assuming the Minix developers are smart people who did it for the mind and probably know a little more about C than I do, why?

Answer 1

This is pure speculation, but perhaps MINIX had requirements that were more important than execution speed, such as simplicity, ease of understanding, and brevity? In the end, some of the code was printed in a tutorial.

Answer 2

Change your code as y2 minix code as y1 Solaris 9 v245 and get the profiler data:

  %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 

Maybe this is the answer

Answer 3

Your method seems sound, but a little harder to get it working on EPOCH_YR = 1970, because now you are in the middle of a loop on several loops.

You see, do you have an equivalent for this case and see if it is even better?

You are certainly right in discussing whether to use this implementation of gmtime () in any high-performance code. This is a lot of work that needs to be done in any hard loops.

Answer 4

The right approach. You definitely want to go on O (1) algo. Will work on the Mayan calendar without noise. Check the last line: dayno is limited to 0..364, although in leap years it should be in the range 0..365. The line before this has a similar drawback.