[PATCH 4/4] libstdc++: More efficient last day of month.

[PATCH 4/4] libstdc++: More efficient last day of month.

[Cassio Neri]

This patch reimplements std::chrono::year_month_day_last:day() which yields the
last day of a particular month.  The current implementation uses a look-up table
implemented as an unsigned[12] array.  The new implementation instead
is based on
the fact that a month m in [1, 12], except for m == 2 (February), is
either 31 or
30 days long and m's length depends on two things: m's parity and whether m >= 8
or not. These two conditions are determined by the 0th and 3th bit of m and,
therefore, cheap and straightforward bit-twiddling can provide the right result.

Measurements in x86_64 [1] suggest a 10% performance boost.  Although this does
not seem to be huge, notice that measurements are done in hot L1 cache
conditions which might not be very representative of production runs. Also
freeing L1 cache from holding the look-up table might allow performance
improvements elsewhere.

References:
[1] https://github.com/cassioneri/calendar

libstdc++-v3/ChangeLog:

    * include/std/chrono:
---
 libstdc++-v3/include/std/chrono | 23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)

diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index 7840099d743..35a7a5e4382 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -1269,9 +1269,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

       inline constexpr unsigned __days_per_month[12]
     = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
-
-      inline constexpr unsigned __last_day[12]
-    = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
     }

     // DAY
@@ -2526,9 +2523,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       constexpr chrono::day
       day() const noexcept
       {
-    if (!_M_mdl.ok() || (month() == February && _M_y.is_leap()))
-      return chrono::day{29};
-    return chrono::day{__detail::__last_day[unsigned(month()) - 1]};
+        const auto __m = static_cast<unsigned>(month());
+
+        // Excluding February, the last day of month __m is either 30 or 31 or,
+        // in another words, it is 30 + b = 30 | b, where b is in {0, 1}.
+
+        // If __m in {1, 3, 4, 5, 6, 7}, then b is 1 if, and only if
__m is odd.
+        // Hence, b = __m & 1 = (__m ^ 0) & 1.
+
+        // If __m in {8, 9, 10, 11, 12}, then b is 1 if, and only if
__m is even.
+        // Hence, b = (__m ^ 1) & 1.
+
+        // Therefore, b = (__m ^ c) & 1, where c = 0, if __m < 8, or c = 1 if
+        // __m >= 8, that is, c = __m >> 3.
+
+        // The above mathematically justifies this implementation whose
+        // performance does not depend on look-up tables being on the L1 cache.
+        return chrono::day{__m != 2 ? ((__m ^ (__m >> 3)) & 1) | 30 :
_M_y.is_leap() ? 29 : 28};
       }

       constexpr
-- 
2.29.2

Re: [PATCH 4/4] libstdc++: More efficient last day of month.

[Matthias Kretz]

I like the idea.

On Dienstag, 23. Februar 2021 14:25:10 CET Cassio Neri via Libstdc++ wrote:
> ((__m ^ (__m >> 3)) & 1) | 30

Note that you can drop the `& 1` part. 30 in binary is 0b11110. ORing with a 
value in [0, 0b01101] will only toggle the last bit.

-- 
──────────────────────────────────────────────────────────────────────────
 Dr. Matthias Kretz                           https://mattkretz.github.io
 GSI Helmholtz Centre for Heavy Ion Research               https://gsi.de
 std::experimental::simd              https://github.com/VcDevel/std-simd
──────────────────────────────────────────────────────────────────────────

Re: [PATCH 4/4] libstdc++: More efficient last day of month.

[Jonathan Wakely]

On 23/02/21 23:13 +0100, Matthias Kretz wrote:
>I like the idea.
>
>On Dienstag, 23. Februar 2021 14:25:10 CET Cassio Neri via Libstdc++ wrote:
>> ((__m ^ (__m >> 3)) & 1) | 30
>
>Note that you can drop the `& 1` part. 30 in binary is 0b11110. ORing with a
>value in [0, 0b01101] will only toggle the last bit.

Yeah looks right to me.

I've committed all Cassio's patches unchanged (except for whitespace
and the dates on the tests) but we can make this additional
improvement too.

Thanks, Cassio. Nice first contributions to libstdc++!