[ntp:questions] Converting from Y-m-d h:m:s
"terje.mathisen at tmsw.no" at ntp.org
Sat May 15 21:05:35 UTC 2010
> Terje Mathisen<"terje.mathisen at tmsw.no"> wrote:
>> Going from YMDHMS to unix (or ntp) seconds is really quite trivial,
>> while the opposite direction is much harder!
>> My most efficient algorithm for the reverse function needs somewhere
>> between 30 and 50 clock cycles (compare with 40 cycles for a single DIV
>> opcode...), while the forward function is about twice as fast:
> Have you seen how glibc approaches this conversion?
No, but as I noted in the source code, my algorithm turned out to be
quite similar to what IBM developed for mainframes. I wouldn't be
surprised to learn that other programmers have ended up with similar code.
The key idea is to realize that when you have a function and its much
slower inverse, then you can implement the slow function by making a
fast guess of what the answer should be, test the guess using the fast
forward function, and then correct if needed.
From offtime.c (glibc 2.1.3):
#define DIV(a, b) ((a) / (b) - ((a) % (b) < 0))
#define LEAPS_THRU_END_OF(y) (DIV (y, 4) - DIV (y, 100) + DIV (y, 400))
while (days < 0 || days >= (__isleap (y) ? 366 : 365))
/* Guess a corrected year, assuming 365 days per year. */
long int yg = y + days / 365 - (days % 365 < 0);
/* Adjust DAYS and Y to match the guessed year. */
days -= ((yg - y) * 365
+ LEAPS_THRU_END_OF (yg - 1)
- LEAPS_THRU_END_OF (y - 1));
y = yg;
The code here is actually both significantly slower and larger (in code
space) than mine. :-)
It knows that time zone offsets are less than 24 (actually 13 or 14?)
hours, which means that most adjustments will stay within the same day
or worst case add/subtract a day.
However, since the latter happens on average 25%+ of the calls (at least
for those of you in the US), it would be faster to simply convert the
struct tm array to seconds, add/subtract the offset, then convert back.
This also gets rid of pretty much all of the offset calculation code. :-)
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
More information about the questions