Fast Time Struct from Seconds

Question

I am looking for the fastest way to determine date components for a vector of NTP Timestamps.

The input in this case are NTP Timestamps or seconds measured since 1900-01-01, going to and from unix time is trivial by adding 2208988800 or subtracting if going the other way. I need to break down the timestamps into the date components for other APIs that only accept dates as their components specifically year, month and day.

Using the ANSI C methods from time.h (glibc) I can easily derive the components but it's too slow for larger vectors. A smaller vector may contain 172800 values but more realistically I'd like to be able to crunch a vector with 1314000 values as quickly as possible.

I was thinking that I could crunch the time myself and eliminate a small amount of glibc overhead by iteratively subtracting the timestamp input by the second divisors for each date component until I arrived at the date, essentially what glibc does but without timezones and some additional (small) overhead.

I'm quickly finding that it's still slow to go about it this way.

I'm working with something like this:

typedef struct simple_time_ {
    int year;
    int month;
    int day;
} simple_time;

size_t time_cruncher(const time_t *ntp_vector, simple_time *out, size_t len)
{
    size_t i;
    time_t corrected;
    struct tm cal;
    for(i=0;i<len;i++) {
        corrected = ntp_vector[i] - 2208988800; /* NTP Offset */
        gmtime_r(&corrected, &cal);
        simple_time[i].year = cal.tm_year + 1900;
        simple_time[i].month = cal.tm_mon + 1;
        simple_time[i].day = cal.tm_mday;
    }
    return i;
}

Is there an algorithm lurking about that can help me derive the computations quicker? Something like Zeller's algorithm but going from seconds to date components?

Thanks!

Answer 1

Given that there is a great likelihood many of your consecutive timestamps are in the same month, use that to your advantage.

Pseudo code
1) Calculate the y,m,d for the given timestamp 't' as you have above.
2) now calculate the t0 = gmtime(y, m, 1) and t1 = gmtime(y, m+1, 1).  (Dec + 1 is OK)
3) As long as your timestamps are t0 <= t < t1, a simple add/divide is need to determine the day of the month.
4) Should 't' fall outside the range,  go to step 1.

One could also determine the start and end time for the current day, see if that applies to the next timestamps.

Answer 2

If your timestamps is within the date range 1901 to 2099 you can take advantage of the fact that every fourth year is leap-year (this can be further extended to include dates within 1900 since it's not a leap year).

I derived this code from a date c library I'm working on with the difference in this code I'm using the "shifted-month" approach as in Zeller's congruence.

#include <stdio.h>
#include <assert.h>
#include <stdint.h>

void
dt_to_ymd(unsigned int n, int *yp, int *mp, int *dp) {
    unsigned int z, c;
    int y, m, d;

    assert(n <= 73107); /* 2100-02-28 */

    z = n + 307;                    /* 1 + 306 (306 days between March 1 and December 31) */
    y = (4 * z) / 1461;
    c = z - (1461 * y - 1) / 4;     /* day of the year [1, 366]  */
    m = (5 * c + 456) / 153;        /* month of the year [1, 12] */
    d = c - (153 * m - 457) / 5;    /* day of the month [1, 31]  */

    if (m > 12)
        y++, m -= 12;

    if (yp) *yp = y + 1899;
    if (mp) *mp = m;
    if (dp) *dp = d;
}

const struct test {
    int year;
    int month;
    int day;
    uint64_t timestamp;
} tests[] =  {
    { 1900,  1,  1,          0 },
    { 1970,  1,  1, 2208988800 },
    { 1972,  1,  1, 2272060800 },
    { 1999, 12, 31, 3155587200 },
    { 2013,  7,  4, 3581884800 },
    { 2100,  2, 28, 6316444800 },
};

int 
main() {
    int i, ntests;

    ntests = sizeof(tests) / sizeof(*tests);
    for (i = 0; i < ntests; i++) {
        const struct test t = tests[i];

        {
            unsigned int n;
            int y, m, d;

            n = t.timestamp / 86400;
            dt_to_ymd(n, &y, &m, &d);
            if (t.year != y || t.month != m || t.day != d) {
                printf("dt_to_ymd(%u)\n", n);
                printf("  got: %.4d-%.2d-%.2d\n", y, m, d);
                printf("  exp: %.4d-%.2d-%.2d\n", t.year, t.month, t.day);
            }
        }
    }
    return 0;
}