A faster way to calculate the day-of-the-week

Calculating the day of the week from a day-count (rata-die) may seem like an elementary task, but it proves to be a surprisingly complex problem upon closer inspection. This article delves into various fast functions designed to compute the weekday, optimized for different use cases including throughput, latency, and performance across diverse platforms. Each of these functions outperforms existing solutions, with many boasting a single multiplication and just two cycles of latency.

An intriguing discovery is that the weekday can be computed in ISO format (1-7 instead of 0-6), using the same instructions but with tweaked constants, without any penalty in speed. A standout function, consisting of a three-instruction sequence (plus a constant load), remains accurate across the full signed 32-bit range and offers the highest throughput for x86 processors.

To understand the workings of the code mentioned above, you don't need prior knowledge of assembly language. By the end of this article, you'll grasp the logic behind the code and appreciate the power of bit manipulation in optimizing date libraries and database engines. This technique extends to generalizing the formula x % (2^N - 1) and devising faster modulus techniques for other divisors such as x % 24 and x % 60, which are applicable to timekeeping as well.

The article provides an overview of the relative speeds of the fastest algorithms tested on AMD Ryzen 9 and Apple M4 Pro processors, with smaller numbers indicating faster performance. The selection of a recommended algorithm for non-library code emphasizes maintenance over micro-optimizations. The Rust example, while not handling the highest inputs, is assumed to be acceptable for practical purposes, given the Unix epoch (1970-01-01) is a Thursday.

While some approaches may seem slow, Howard Hinnant's technique (2014) adopted by numerous date libraries, offers a simple and flexible solution. This method, applicable to all bit-widths, covers the full signed 32-bit range with the exception of the highest four inputs, which may result in undefined behavior. It's important to note that on 2's complement machines, the algorithm usually still works for those values, despite compiler guarantees being uncertain.

Cassio Neri's work, published in 2024, stands out as the modern gold standard for a full-range solution. Designed to be fast, full-range, and not overly low-level, this approach uses a cast from signed to unsigned before processing, avoiding potential overflow issues. An interesting observation in the 32-bit version is the addition of zero for negative numbers, dictated by the property 2^32 % 7 = 4, which already incorporates the addition of 4.

To determine the second constant for different bit-widths, use the formula: - ((3 + 2^BIT_WIDTH) % 7).

For those seeking even faster performance, the article explores the assembly-level techniques used by GCC and Clang, which involve computing the following sequence of operations. The libdivide technique, introduced by ridiculousfish in 2011, eliminates the correction line by making a saturating increment to the input and using a round-down multiplier. While this approach measures around 10% faster, there exist even faster methods that involve reducing the range requirement and leveraging the properties of Mersenne numbers.