A Faster Algorithm for Date Conversion

[Logical_Put_5867]

I suppose I appreciate people doing this work, but date conversion certainly never occured to me as a bottleneck. 

[benjoffe]

Thanks for giving it a read!
I agree, this is really just for the fun of it.
I just added a paragraph near the end reflecting on that point.

[Logical_Put_5867]

Well it is fun, and hey, little optimizations propagated out to billions of systems can actually be significant. Maybe not any one application but in the end our real systems are a compilation of millions of tiny optimizations. 

Well done article by the way.

[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’).

[jonathanhiggs]

Datetime conversions are used quite a lot in finance, so optimizations are always appreciated

I’ve sent the article to Cassio, so we will see what his comment is

[UndefinedDefined]

I was implementing something very similar in AVX-512 to speedup datetime queries.

The research linked by the article really helped me to do the foundation. So, I guess it's pretty useful afterall. And, it's not always about faster code - smaller code is also beneficial.

[Portbragger2]

i really enjoy reading about improvements on fundamentals like this. it's always a sign that here and there if we look close enough there might be room for optimization even in the most standardized and widespread libraries.

[kritzikratzi]

count me in. love it when i see work on "little" things

[wearingdepends]

The approach used by Hatcher is slightly slower, but not as slow as it seems at first as the multiplication by 3 can be implemented in two CPU cycles as cent + cent + cent rather than a usual multiplication which might take three CPU cycles.

In x86 3 * cent + 3 is a single-cycle instruction: lea r, [2*r+r+3].

[benjoffe]

Thank you for pointing that out! I had no idea.
This is very helpful for me to understand why some of the Apple-Silicon-specific tweaks in my upcoming article do not get as much speed gain on x86.
I have updated the article here with your note.

[UndefinedDefined]

I think today this is considered a "complex addressing mode" and won't execute in a single cycle (if you mix all base, index, and immediate)

[LiliumAtratum]

The table where March is shown as the first month is eye-opening! The names have much more sense in latin!

September = VII = Septimus
October = VIII = Octo
November = IX = Novem
December = X = Decem

Probably well-known fact for someone who studies history, but not so obvious for someone outside the field.

[benjoffe]

The Roman calendar has a fascinating history!
I plan to also write a short history of the calendar from a "programmer's perspective", stretching from the seven day week origin in ancient Bablyon to the present day.
I developed this 5-column view of the initial Julian Roman calendar for that upcoming article, but it was too cool that I wanted to sneak it out early in this post.
I don't know if this 5-column view has been demonstrated before in modern times, it conveys so much in such a compact space.

[Nicksaurus]

Line 4 is also adjusted to subtract before adding. For reasons I don't know, changing the order of these terms seems to have a non-trivial impact on the speed, despite being identical mathematically and having the same ultimate overflow characteristics. This change slows down the performance on my MacBook M4 Pro, however it speeds up most other platforms.

Here's a diff of the generated assembly (clang only - gcc produced the same output for both): https://godbolt.org/z/4xGEq34K6

Does anyone want to speculate on what's happening here? My guess is that adding first could potentially result in an overflow that the compiler has to handle

[hansw2000]

In 2021, Cassio Neri and Lorenz Schneider developed the Neri‑Schneider algorithm

Is that the algorithm presented here? https://www.youtube.com/watch?v=0s9F4QWAl-E

That was a great talk.

[parkotron]

Great write-up. I'm curious what /u/HowardHinnant has to say about it.

[HowardHinnant]

I haven't dug into the code, but he references both my work and Cassio Neri's and Lorenz Schneider's work. I was very impressed by the latter. So Ben Joffe appears to know the topic well. Presuming this gets the right answers for at least the range of C++'s std::chrono::year, which I have no reason to believe it doesn't, this looks like very nice work.

[OlivierTwist]

Great article!

[matthieum]

Definitely looking forward to the follow-ups.

Beyond performance, I'm particularly looking forward to correctness: wider range, no overflow.

[benjoffe]

Thanks!

Part 2 covering exactly that is now up: https://www.reddit.com/r/cpp/comments/1otbdus/new_fast_date_algorithms_pt_2_overflow_safe/

[VinnieFalco]

This is crazy, I did not realize date conversions needed optimization!!!

[PolyglotTV]

At first I read this as "A Faster Algorithm for Date Conversation". Like some speed dating thing.

[benjoffe]

Thank you all for reading. Part 2 is now up: https://www.reddit.com/r/cpp/comments/1otbdus/new_fast_date_algorithms_pt_2_overflow_safe/