[gcc r117372] libstdc++: More efficient last day of month
Jonathan Wakely
redi@gcc.gnu.org
Wed Feb 24 18:52:24 GMT 2021
https://gcc.gnu.org/g:8265ab07f3bbeb672488fdfc6418e0bce89dff9c
commit r117372g8265ab07f3bbeb672488fdfc6418e0bce89dff9c
Author: Cassio Neri <cassio.neri@gmail.com>
Date: Wed Feb 24 18:12:47 2021 +0000
libstdc++: More efficient last day of month
This patch reimplements std::chrono::year_month_day_last:day() which yields the
last day of a particular month. The current implementation uses a lookup 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 bittwiddling 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 lookup table might allow performance
improvements elsewhere.
References:
[1] https://github.com/cassioneri/calendar
libstdc++v3/ChangeLog:
* include/std/chrono (year_month_day_last:day): New
implementation.
Diff:

libstdc++v3/include/std/chrono  24 ++++++++++++++++++
1 file changed, 18 insertions(+), 6 deletions()
diff git a/libstdc++v3/include/std/chrono b/libstdc++v3/include/std/chrono
index 3ba35a5bc86..feb2c2a1fad 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
@@ 2576,9 +2573,24 @@ _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 lookup tables being on the L1 cache.
+ return chrono::day{__m != 2 ? ((__m ^ (__m >> 3)) & 1)  30
+ : _M_y.is_leap() ? 29 : 28};
}
constexpr
More information about the Libstdc++cvs
mailing list