Date Time - Seconds Difference

Question

For trivial reasons, I decided to have a go at differentiating dates. Low and behold having no idea how much of a non-trivial task it was to become.

It was originally a small sidetrack from a project I'm doing.

And, whilst performance isn't a huge concern here, the code I've posted below performs highly optimally in comparison to its alternative (shown below it). This is preferred, as originally this was used in a real-time program, and without other changes to the high-level algorithm, the cost of re-calculating the date difference every frame (up to 60FPS) was creating a significant run-time penalty.

But what I'm looking for in my solution, is algorithmic improvements, not optimizations (it runs more than fast enough). Such as removing the for loop for calculating which years are leap years (perhaps using 365.242199 constant?).

And especially techniques on how to get rid of that huge tree of comparisons for the initial swap; that just doesn't look like good practice... ever. I'm sure it can be done in the algorithm, but my attempts failed and I ran out of time.

long calculate_seconds_between(
    uint Y1, uint M1, uint D1, uint H1, uint m1, uint S1,
    uint Y2, uint M2, uint D2, uint H2, uint m2, uint S2
)
{
    bool invert = false;
    if (Y1 > Y2) {
        invert = true;
    } else if (Y1 == Y2) {
        if (M1 > M2) {
            invert = true;
        } else if (M1 == M2) {
            if (D1 > D2) {
                invert = true;
            } else if (D1 == D2) {
                if (H1 > H2) {
                    invert = true;
                } else if (H1 == H2) {
                    if (m1 > m2) {
                        invert = true;
                    } else if (m1 == m2 && S1 > S2) {
                        invert = true;
                    }
                }
            }
        }
    }

    if (invert) {
        std::swap(Y1, Y2);
        std::swap(M1, M2);
        std::swap(D1, D2);
        std::swap(H1, H2);
        std::swap(m1, m2);
        std::swap(S1, S2);
    }

    static const int month_days_sum[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
    const uint Y1_days = month_days_sum[M1 - 1];
    const uint Y2_days = month_days_sum[M2 - 1];
    int years_days = (Y2 - Y1) * 365;

    // Leap Years
    for (uint i = Y1 + 1; i < Y2;) {
        if (is_leap_year(i)) {
            ++years_days;
            i += 4;
        } else {
            ++i;
        }
    }

    const bool lY1 = is_leap_year(Y1) && (M1 < 2 || (M1 == 2 && D1 < 29));
    const bool lY2 = is_leap_year(Y2) && (M2 > 2 || (M2 == 2 && D2 > 28));

    if (Y1 == Y2) {
        if (lY1 && lY2) ++years_days;
    } else {
        if (lY1) ++years_days;
        if (lY2) ++years_days;
    }

    // Convert years to seconds
    const long years_seconds = years_days * 86400;

    // Time difference in seconds
    const long S1s = ((Y1_days + D1) * 86400) + (H1 * 3600) + (m1 * 60) + S1;
    const long S2s = ((Y2_days + D2) * 86400) + (H2 * 3600) + (m2 * 60) + S2;

    const long total = years_seconds + (S2s - S1s);

    if (invert) return -total;
    else return total;
}

Standard C++ Alternative Note: very slow, up to (8000 / 35) 228x slower than the above.

time_t calculate_seconds_between2(
    const uint Y1, const uint M1, const uint D1, const uint H1, const uint m1, const uint S1, // YY/MM/DD HH:mm:SS
    const uint Y2, const uint M2, const uint D2, const uint H2, const uint m2, const uint S2
)
{
    time_t raw;
    time(&raw);

    struct tm t1, t2;

    gmtime_r(&raw, &t1);
    t2 = t1;

    t1.tm_year = Y1 - 1900;
    t1.tm_mon = M1 - 1;
    t1.tm_mday = D1;
    t1.tm_hour = H1;
    t1.tm_min = m1;
    t1.tm_sec = S1;

    t2.tm_year = Y2 - 1900;
    t2.tm_mon = M2 - 1;
    t2.tm_mday = D2;
    t2.tm_hour = H2;
    t2.tm_min = m2;
    t2.tm_sec = S2;

    time_t tt1, tt2;
    tt1 = mktime(&t1);
    tt2 = mktime(&t2);

    return (tt2 - tt1);
}

As shown in the Unit Testing, every single date (excluding tests on time) from 1990 to 2020 has been tested against every date from 1990 to 2020 (n^2) without failure, so the algorithm appears to be correct in terms of accuracy against the GNU implementation on my platform.

Unit Testing Code: http://pastie.org/2933904

Benchmark Code: http://pastie.org/2933893

Tagged with C as this is barely a far cry from being completely transferable.

Answer 1

I think if i was doing it, I'd try to structure it more like the standard code: turn each Y/M/D/H/m/S into seconds since some epoch, then use fairly straightforward subtraction to compute the difference.

unsigned calculate_seconds_between2(unsigned Y1, unsigned M1, unsigned D1, unsigned H1, unsigned m1, unsigned S1,
                                    unsigned Y2, unsigned M2, unsigned D2, unsigned H2, unsigned m2, unsigned S2)
{
    // JSN = seconds since some epoch:
    unsigned T1 = JSN(Y1, M1, D1, H1, m1, S1);
    unsigned T2 = JSN(Y2, M2, D2, H2, m2, S2);
    return T1>T2 ? T1-T2 : T2-T1;
}

For the seconds since epoch, I'd probably use something like a normal Julian Day Number, but with a more recent epoch (to reduce magnitudes, and with them the possibility of overflow), then calculate seconds into the day, something like this:

unsigned JSN(unsigned Y, unsigned M, unsigned D, unsigned H, unsigned m, unsigned S) {
    static const int unsigned secs_per_day = 24 * 60 * 60;
    return mJDN(Y-1900, M, D) * secs_per_day + H * 3600 + m * 60 + S;
}

That leaves only calculating the modified JDN. It's not exactly transparent, but:

unsigned mJDN(unsigned Y, unsigned M, unsigned D) { 
    return 367*Y - 7*(Y+(M+9)/12)/4 + 275*M/9 + D;
}

This formula is from a 1991 Usenet post by Tom Van Flandern, with an even more modified JDN (i.e., an even more recent epoch).

Another way to help avoid overflow would be to model it a bit more closely after your code: compute a difference in days, and a difference in seconds, and only then convert the days to seconds, and add on the difference in seconds within the day:

unsigned time_diff(/* ...*/) { 
    unsigned D1 = JDN(Y1, M1, D1);
    unsigned D2 = JDN(Y2, M2, D2);

    unsigned T1 = H1 * 3600 + m1 * 60 + S1;
    unsigned T2 = H2 * 3600 + m2 * 60 + S1;

    if (D1 == D2)
       return T1>T2 ? T1-T2 : T2-T1;
    return D1>D2 ? (D1-D2)*secs_per_day + T1-T2 : (D2-D1)*secs_per_day + T2-T1;
}

In particular, this would make it easier to avoid overflow while still using standard Julian day numbers. This would be useful if (for example) you were using standard Julian day numbers for other purposes, so you wanted to re-use those standard routines.

I haven't run full regression tests for accuracy (since the point is more about the overall structure than the actual code implementing it), but I'm reasonably certain the approach can/will produce accurate results. A quick test for speed indicates that it should be reasonably competitive in that regard as well -- at least with the compilers I have handy, it's fairly consistently somewhat faster. Even if (for example) I've messed something up in transcribing Tom's formula into C++, I doubt that fixing it will have any major effect on speed.

Readability is open to a bit more question. Most of this code is very simple and straightforward, with one line of nearly impenetrable "magic math". Yours "distributes" the complexity, so there's no one part that's terribly difficult, but also no part that's really easy, obvious, or reusable either.

Edit: As written this produces the absolute value of the difference. Eliminating that simplifies the code to something like this:

int mJDN(int Y, int M, int D) { 
    return 367*Y - 7*(Y+(M+9)/12)/4 + 275*M/9 + D;
}

int JSN(ull Y, ull M, ull D, ull H, ull m, ull S) {
    static const int secs_per_day = 24 * 60 * 60;
    return mJDN(Y-1900, M, D) * secs_per_day + H * 3600 + m * 60 + S;
}

int calculate_seconds_between3(int Y1, int M1, int D1, int H1, int m1, int S1,
                               int Y2, int M2, int D2, int H2, int m2, int S2)
{
    int T1 = JSN(Y1, M1, D1, H1, m1, S1);
    int T2 = JSN(Y2, M2, D2, H2, m2, S2);
    return T2-T1;
}

Answer 2

Both methods have bugs:

• The first method takes no account of leap seconds, whereas the second might (depending on the platform).

• The second method isn't guaranteed to return its result in units of seconds (although the use of gmtime_r(), suggests you're targeting POSIX, which does make that guarantee).

---

I had to infer some definitions, because the review is incomplete (and the linked code was inaccessible when I attempted to access it):

#include <ctime>
#include <utility>

using uint = unsigned int;

I also needed to add a definition of is_leap_year in the first function:

auto const is_leap_year = [](uint y){ return y%4 ? 0 : y%100 ? 1 : y%400 == 0; };

I could then add a benchmark, and a main() to run it:

template<typename F>
struct benchmark
{
    const F func;
    benchmark(F func) : func{std::move(func)} {}

    auto operator()() const  
    {
        decltype(func(0,0,0,0,0,0,0,0,0,0,0,0)) sum = 0;
        for (auto year = 1900; year <= 2000;  ++year)
            for (auto month = 1; month <= 12; ++month)
                sum += func(year, month, 20, 12, 0, 0,
                            2000, 6, 1, 8, 0, 0);
        return sum;
    }
};

#include <chrono>
#include <ostream>

template<typename T>
struct time_printer
{
    T func;

    friend std::ostream& operator<<(std::ostream& os, const time_printer& p)
    {
        using Duration
            = std::chrono::duration<double, std::chrono::milliseconds::period>;
        auto begin = std::chrono::steady_clock::now();
        p.func();
        auto end = std::chrono::steady_clock::now();
        Duration time_taken = end - begin;
        return os << time_taken.count();
    }
};

template<typename T>
time_printer<T> print_time(T fun) { return {fun}; }

#include <iostream>
int main()
{
    std::clog << "Method 1: "
              << print_time(benchmark(calculate_seconds_between)) << std::endl;
    std::clog << "Method 2: "
              << print_time(benchmark(calculate_seconds_between2)) << std::endl;
}

This gives me a baseline ratio of about 100 between the two methods (after removing the unnecessary call to std::time in the second function). std::mktime() is always likely to be slower, as it must update tm_yday and (significantly) tm_wday in the passed structure.

---

Let's now have a look at the function:

The big if/else chain is ugly, as you noticed. The usual fix is to include <tuple>:

auto t1 = std::tie(Y1, M1, D1, H1, m1, S1),
    t2  = std::tie(Y2, M2, D2, H2, m2, S2);

auto invert = t2 < t1;
if (invert) std::swap(t1, t2);

As an alternative to recording invert, we can simply recurse with the arguments swapped:

auto t1 = std::tie(Y1, M1, D1, H1, m1, S1),
    t2  = std::tie(Y2, M2, D2, H2, m2, S2);

if (t2 < t1)
    return - calculate_seconds_between(Y2, M2, D2, H2, m2, S2,
                                       Y2, M2, D2, H2, m2, S2);

Both of these changes are below the noise floor in my performance measurements.

---

We can simplify the calculation of lY1 and lY2 given that we've almost calculated the day-in-year just before. Move the addition of Yn_days and Dn, then we can just use that day number:

const uint Y1_days = month_days_sum[M1 - 1] + D1;
const uint Y2_days = month_days_sum[M2 - 1] + D2;


static const uint feb_29th = 60;
const bool lY1 = is_leap_year(Y1) && Y1_days < feb_29th;
const bool lY2 = is_leap_year(Y2) && M2 > 2;

// Time difference in seconds
const long S1s = ((Y1_days) * 86400) + (H1 * 3600) + (m1 * 60) + S1;
const long S2s = ((Y2_days) * 86400) + (H2 * 3600) + (m2 * 60) + S2;

(I fixed the logic for lY2 - it's a shame you didn't include the unit tests, as I think you have missed at least one, with the end date being 29 February).

---

We can also simplify the calculation of first and last leap day to avoid branching:

years_days += lY1 + lY2 - (Y1 == Y2);

Alternatively, we could just conditionally include the first and/or last year into the loop:

for (uint i = Y1 + (Y1_days < feb_29th);  i <= Y2 - (M2 > 2);) {
    if (is_leap_year(i)) {
        ++years_days;
        i += 4;
    } else {
        ++i;
    }
}

---

We can remove two of the multiplications by 86400, by summing days first. We can eliminate all the paired multiplications like this:

// compute total seconds
const long days = years_days + Y2_days - Y1_days;
const long hours = days*24 + H2 - H1;
const long minutes = hours*60 + m2 - m1;
return minutes*60 + S2 - S1;

Here, we avoid the subtle bug in the original, where years_days * 86400 (int * int => int) could overflow (remember, INT_MAX can be as low as 65536) before being widened to long years_seconds`.

---

My version

#include <ctime>
#include <tuple>
#include <utility>

using uint = unsigned int;

long calculate_seconds_between(
    const uint Y1, const uint M1, const uint D1,
    const uint H1, const uint m1, const uint S1,
    const uint Y2, const uint M2, const uint D2,
    const uint H2, const uint m2, const uint S2)
{
    auto const
        t1 = std::tie(Y1, M1, D1, H1, m1, S1),
        t2 = std::tie(Y2, M2, D2, H2, m2, S2);

    if (t2 < t1)
        return - calculate_seconds_between(Y2, M2, D2, H2, m2, S2,
                                           Y2, M2, D2, H2, m2, S2);

    int years_days = (Y2 - Y1) * 365;

    // Leap Years
    auto const is_leap_year
        = [](uint y){ return y%4 ? 0 : y%100 ? 1 : y%400 == 0; };
    for (uint i = Y1 + (M1 > 2);  i < Y2 + (M2 > 2);) {
        if (is_leap_year(i)) {
            ++years_days;
            i += 4;
        } else {
            ++i;
        }
    }

    static const uint month_days_sum[] =
        {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
    const uint Y1_days = month_days_sum[M1 - 1] + D1;
    const uint Y2_days = month_days_sum[M2 - 1] + D2;

    // compute total seconds
    const long days = years_days + Y2_days - Y1_days;
    const long hours = days*24 + H2 - H1;
    const long minutes = hours*60 + m2 - m1;
    return minutes*60 + S2 - S1;
}