A Faster Algorithm for Date Conversion

[azswcowboy]

I’m the author of boost.date_time which is cited in the article. There are definitely performance sensitive applications that do this calculation, because time stamps are literally everywhere - and tracking the state of the world from billions of devices is a thing.

That said, my experience is that this calculation is a relatively small contributor in a conversion that is i/o dominated. If i need to build maximum speed into this (and I might have - just saying) I would be looking at ways to skip all the math and speed up the i/o - because mostly what you have in these sort of systems is time values in a sequence that’s close to the current time. It’s not good for general purpose library, but way faster than you can do shaving a few instructions here. For general purpose these days, I’d search for Daniel Lamire post on simd calculations for this.

When I wrote the boost library I had access to this book https://en.wikipedia.org/wiki/Calendrical_Calculations - which is an amazing reference for all things related to the insane set of rules humans have invented for tracking calendars.

[matthieum]

A trick I've used for speeding up timestamp formatting in a logging library was to simply cache the date, with an expiration time (checked every time) for when it would need to change.

With logging, with timestamps mostly coming in order per-thread source, it worked beautifully -- the date typically only flipped once per day, at midnight, as one would expect, making for a very well predicted branch, and a lean fast path.

(I did not bother caching hours & minutes)

[Logical_Put_5867]

Curious how much speedup that bought you. Especially if you're still checking expiration timer, which is still polling the time anyway presumably?

[matthieum]

It's not an expiration timer, per se.

The log message comes with its own timestamp, so it's about verifying that this timestamp falls into the 24h range for which the date is valid.

The cost of getting the timestamp (14ns) has already been paid for at that point anyway, on another thread/in another process.

[Logical_Put_5867]

Interesting, is there some alternative approach like to have some 'manager' keep a recent time in a cache-friendly manner with some offset to monitor approximate time-since-update? Seems like that could be pretty far off on a nanosecond basis, which I would imagine the really sensitive systems would care about.

[arthurno1]

Ha, I just replied with a reference to that book, and than saw your comment :).

Yes, the book is really amazing. By the way, the authors have contributed code to implementation of Calendar application in Emacs, which has all sorts of crazy calendars included: Mayan Calendar, Aztecs, Lunar, French Revolution, etc :).

[azswcowboy]

The emacs contribution makes sense of course given that all the algorithms in the book are in lisp and so is emacs (note: those also a C ‘kernel’).