This talk concerns calendar algorithms which I implemented in the Linux Kernel and in libstdc++ (＜chrono＞). One of them has been ported to C# and released in .NET 7. I show some optimisation results that explain why these algorithms are so suited for modern CPUs. These optimisations might be useful elsewhere since benchmark results show that our algorithms perform considerably faster than counterparts in libc++, boost, OpenJDK, Android phones and other popular open source libraries.
Most results are strength reduction techniques not used by any optimising compiler. Another technique breaks a data-dependency that commonly appears in division/modulus calculations and by doing so, we improve instruction level parallelism in superscalar CPUs. 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. 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.
View Slides