Speeding Date: Implementing Fast Calendar Algorithms
Given that N days have elapsed since 1st January 1970, what day is today?
Hummm... Since years and months have variable number of days, this problem seems difficult. Breaking down time is easier though: given that N seconds have elapsed since midnight, what time is it? A couple of divisions and modulus operations by 60 gives the answer. What if I tell you the first problem is quite similar to the second one? Indeed using a simple mathematical generalisation of division allows solving both problems in the same way.
That's what I did: I used mathematical results to developed calendar algorithms that, in addition to the cool maths, proved to be faster than alternatives in libc++, boost, OpenJDK, Android phones and other popular open source libraries. So much that these algorithms -- the subject of this talk -- now feature in the Linux Kernel, libstdc++ (<chrono>) and Microsoft's .NET.
We shall see a gentle introduction to the underlying mathematical results and how the optimisations based on them make these algorithms so suited for modern CPUs. The same optimisations might be useful elsewhere. Also in the talk:
1) An implementation of the humble std::chrono::year::is_leap that's usually 3x faster than virtually every other implementation out there.
2) A one-line C/C++ expression that yields the last day of the month M for 1 <= M <= 12 and M != 2 (i.e., disregards February -- the ugly duckling of the months). It doesn't use either branches (if or switch) or look-up tables just... (Shush! No spoilers here.)
3) A brief history of our most used calendar, from its Roman origins, its Greek and Egyptian influences, up to its final form taken in the 16th century. Decisions made hundreds of years ago have a deep impact on the performance of calendar algorithms that run today. A fascinating subject, full of story telling that can amuse guests at any dinner party.
I hold a PHD in Applied Mathematics from University of Paris Dauphine. I have been professionally coding in C++ for more than 15 years but my coding experience has started far earlier. I currently work on the financial industry in London but had previously worked in academia for more than a decade.
I am the author of a few research articles and I have published them on peer-reviewed journals on Mathematics (there's an equation named after me), Finance, Computer Science and C++.