From patchwork Tue Feb 23 13:24:50 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [1/4] libstdc++: More efficient date from days. X-Patchwork-Submitter: Paul Richard Thomas via Gcc-patches X-Patchwork-Id: 49667 Message-Id: To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Date: Tue, 23 Feb 2021 13:24:50 +0000 From: Cassio Neri via Gcc-patches List-Id: Gcc-patches mailing list This patch reimplements std::chrono::year_month_day::_S_from_days() which retrieves a date from the number of elapsed days since 1970/01/01. The new implementation is based on Proposition 6.3 of Neri and Schneider, "Euclidean Affine Functions and Applications to Calendar Algorithms" available at https://arxiv.org/abs/2102.06959. The aforementioned paper benchmarks the implementation against several counterparts, including libc++'s (which is identical to the current implementation). The results, shown in Figure 4, indicate the new algorithm is 2.2 times faster than the current one. The patch adds a test which loops through all integers in [-12687428, 11248737], and for each of them, gets the corresponding date and compares the result against its expected value. The latter is calculated using a much simpler and easy to understand algorithm but which is also much slower. The interval used in the test covers the full range of values for which a roundtrip must work [time.cal.ymd.members]. Despite its completeness the test runs in a matter of seconds. libstdc++-v3/ChangeLog: * include/std/chrono: * testsuite/std/time/year_month_day/3.cc: New test. --- libstdc++-v3/include/std/chrono | 46 ++++++++---- .../testsuite/std/time/year_month_day/3.cc | 71 +++++++++++++++++++ 2 files changed, 104 insertions(+), 13 deletions(-) create mode 100644 libstdc++-v3/testsuite/std/time/year_month_day/3.cc -- 2.29.2 diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 7840099d743..d224762fd3f 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -2429,22 +2429,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // TODO: Implement operator<<, from_stream. }; - // Construct from days since 1970/01/01. Magic. + // Construct from days since 1970/01/01. + // Proposition 6.3 of Neri and Schneider, "Euclidean Affine Functions and Applications to + // Calendar Algorithms". https://arxiv.org/abs/2102.06959 constexpr year_month_day year_month_day::_S_from_days(const days& __dp) noexcept { - const auto __z = __dp.count() + 719468; - const auto __era = (__z >= 0 ? __z : __z - 146096) / 146097; - const auto __doe = static_cast(__z - __era * 146097); - const auto __yoe - = (__doe - __doe / 1460 + __doe / 36524 - __doe / 146096) / 365; - const auto __y = static_cast(__yoe) + __era * 400; - const auto __doy = __doe - (365 * __yoe + __yoe / 4 - __yoe / 100); - const auto __mp = (5 * __doy + 2) / 153; - const auto __d = __doy - (153 * __mp + 2) / 5 + 1; - const auto __m = __mp < 10 ? __mp + 3 : __mp - 9; - return year_month_day{chrono::year(__y + (__m <= 2)), - chrono::month(__m), chrono::day(__d)}; + constexpr auto __z2 = static_cast(-1468000); + constexpr auto __r2_e3 = static_cast(536895458); + + const auto __r0 = __dp.count() + __r2_e3; + + const auto __n1 = 4 * __r0 + 3; + const auto __q1 = __n1 / 146097; + const auto __r1 = __n1 % 146097 / 4; + + constexpr auto __p32 = static_cast(1) << 32; + const auto __n2 = 4 * __r1 + 3; + const auto __u2 = static_cast(2939745) * __n2; + const auto __q2 = static_cast(__u2 / __p32); + const auto __r2 = static_cast(__u2 % __p32) / 2939745 / 4; + + constexpr auto __p16 = static_cast(1) << 16; + const auto __n3 = 2141 * __r2 + 197913; + const auto __q3 = __n3 / __p16; + const auto __r3 = __n3 % __p16 / 2141; + + const auto __y0 = 100 * __q1 + __q2; + const auto __m0 = __q3; + const auto __d0 = __r3; + + const auto __j = __r2 >= 306; + const auto __y1 = __y0 + __j; + const auto __m1 = __j ? __m0 - 12 : __m0; + const auto __d1 = __d0 + 1; + + return year_month_day{chrono::year{__y1 + __z2}, chrono::month{__m1}, chrono::day{__d1}}; } // Days since 1970/01/01. Magic. diff --git a/libstdc++-v3/testsuite/std/time/year_month_day/3.cc b/libstdc++-v3/testsuite/std/time/year_month_day/3.cc new file mode 100644 index 00000000000..eede649cd54 --- /dev/null +++ b/libstdc++-v3/testsuite/std/time/year_month_day/3.cc @@ -0,0 +1,71 @@ +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +// Copyright (C) 2020-2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Class year_month_day [time.cal.year_month_day] + +#include +#include + +// Slow but very clear way of advancing one day. +constexpr void +advance(std::chrono::year_month_day& ymd) noexcept { + + using namespace std::chrono; + + auto y = ymd.year(); + auto m = ymd.month(); + auto d = ymd.day(); + + if (d != year_month_day_last{year{y}, month_day_last{m}}.day()) + ++d; + else { + d = day{1}; + if (m != December) + ++m; + else { + m = January; + ++y; + } + } + ymd = year_month_day{y, m, d}; +} + +void test01() +{ + using namespace std::chrono; + + // [-12687428, 11248737] maps to [-32767y/January/1d, 32767y/December/31d] + + auto n = days{-12687428}; + auto ymd = -32767y/January/1d; + while (n < days{11248737}) { + VERIFY( year_month_day{sys_days{n}} == ymd ); + ++n; + advance(ymd); + } + // One more for n = 11248737 and ymd = 32767y/December/31d + VERIFY( 32767y/December/31d == year_month_day{sys_days{days{11248737}}} ); +} + +int main() +{ + test01(); + return 0; +} From patchwork Tue Feb 23 13:24:57 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [2/4] libstdc++: More efficient days from date. X-Patchwork-Submitter: Paul Richard Thomas via Gcc-patches X-Patchwork-Id: 49668 Message-Id: To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Date: Tue, 23 Feb 2021 13:24:57 +0000 From: Cassio Neri via Gcc-patches List-Id: Gcc-patches mailing list This patch reimplements std::chrono::year_month_day::_M_days_since_epoch() which calculates the number of elapsed days since 1970/01/01. The new implementation is based on Proposition 6.2 of Neri and Schneider, "Euclidean Affine Functions and Applications to Calendar Algorithms" available at https://arxiv.org/abs/2102.06959. The aforementioned paper benchmarks the implementation against several counterparts, including libc++'s (which is identical to the current implementation). The results, shown in Figure 3, indicate the new algorithm is 1.7 times faster than the current one. The patch adds a test which loops through all dates in [-32767/01/01, 32767/12/31], and for each of them, gets the number of days and compares the result against its expected value. The latter is calculated using a much simpler and easy to understand algorithm but which is also much slower. The dates used in the test covers the full range of possible values [time.cal.year.members]. Despite its completeness the test runs in matter of seconds. libstdc++-v3/ChangeLog: * include/std/chrono: * testsuite/std/time/year_month_day/4.cc: New test. --- libstdc++-v3/include/std/chrono | 34 +++++---- .../testsuite/std/time/year_month_day/4.cc | 71 +++++++++++++++++++ 2 files changed, 92 insertions(+), 13 deletions(-) create mode 100644 libstdc++-v3/testsuite/std/time/year_month_day/4.cc +} -- 2.29.2 diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 7840099d743..30203540f36 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -2447,22 +2447,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION chrono::month(__m), chrono::day(__d)}; } - // Days since 1970/01/01. Magic. + // Days since 1970/01/01. + // Proposition 6.2 of Neri and Schneider, "Euclidean Affine Functions and Applications to + // Calendar Algorithms". https://arxiv.org/abs/2102.06959 constexpr days year_month_day::_M_days_since_epoch() const noexcept { - const auto __y = static_cast(_M_y) - (_M_m <= February); - const auto __m = static_cast(_M_m); - const auto __d = static_cast(_M_d); - const auto __era = (__y >= 0 ? __y : __y - 399) / 400; - // Year of "era" [0, 399]. - const auto __yoe = static_cast(__y - __era * 400); - // Day of year [0, 365]. - const auto __doy = (153 * (__m > 2 ? __m - 3 : __m + 9) + 2) / 5 + __d - 1; - // Day of "era" [0, 146096]. - const auto __doe = __yoe * 365 + __yoe / 4 - __yoe / 100 + __doy; - const auto __days = __era * 146097 + static_cast(__doe) - 719468; - return days{__days}; + auto constexpr __z2 = static_cast(-1468000); + auto constexpr __r2_e3 = static_cast(536895458); + + const auto __y1 = static_cast(static_cast(_M_y)) - __z2; + const auto __m1 = static_cast(_M_m); + const auto __d1 = static_cast(_M_d); + + const auto __j = static_cast(__m1 < 3); + const auto __y0 = __y1 - __j; + const auto __m0 = __j ? __m1 + 12 : __m1; + const auto __d0 = __d1 - 1; + + const auto __q1 = __y0 / 100; + const auto __yc = 1461 * __y0 / 4 - __q1 + __q1 / 4; + const auto __mc = (979 *__m0 - 2919) / 32; + const auto __dc = __d0; + + return days{static_cast(__yc + __mc + __dc - __r2_e3)}; } // YEAR_MONTH_DAY_LAST diff --git a/libstdc++-v3/testsuite/std/time/year_month_day/4.cc b/libstdc++-v3/testsuite/std/time/year_month_day/4.cc new file mode 100644 index 00000000000..2194af17775 --- /dev/null +++ b/libstdc++-v3/testsuite/std/time/year_month_day/4.cc @@ -0,0 +1,71 @@ +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +// Copyright (C) 2020-2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Class year_month_day [time.cal.year_month_day] + +#include +#include + +// Slow but very clear way of advancing one day. +constexpr void +advance(std::chrono::year_month_day& ymd) noexcept { + + using namespace std::chrono; + + auto y = ymd.year(); + auto m = ymd.month(); + auto d = ymd.day(); + + if (d != year_month_day_last{year{y}, month_day_last{m}}.day()) + ++d; + else { + d = day{1}; + if (m != December) + ++m; + else { + m = January; + ++y; + } + } + ymd = year_month_day{y, m, d}; +} + +void test01() +{ + using namespace std::chrono; + + // [-32767y/January/1d, 32767y/December/31d] maps to [-12687428, 11248737] + + auto n = days{-12687428}; + auto ymd = -32767y/January/1d; + while (ymd < 32767y/December/31d) { + VERIFY( static_cast(ymd) == sys_days{n} ); + ++n; + advance(ymd); + } + // One more for ymd = 32767y/December/31d and n = 11248737. + VERIFY( sys_days{days{11248737}} == static_cast(32767y/December/31d) ); +} + +int main() +{ + test01(); + return 0; From patchwork Tue Feb 23 13:25:04 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [3/4] libstdc++: More efficient is_leap. X-Patchwork-Submitter: Paul Richard Thomas via Gcc-patches X-Patchwork-Id: 49669 Message-Id: To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Date: Tue, 23 Feb 2021 13:25:04 +0000 From: Cassio Neri via Gcc-patches List-Id: Gcc-patches mailing list This patch reimplements std::chrono::year::is_leap(). Leap year check is ubiquitously implemented (including here) as: y % 4 == 0 && (y % 100 != 0 || y % 400 == 0). The rationale being that testing divisibility by 4 first implies an earlier return for 75% of the cases, therefore, avoiding the needless calculations of y % 100 and y % 400. Although this fact is true, it does not take into account the cost of branching. This patch, instead, tests divisibility by 100 first: (y % 100 != 0 || y % 400 == 0) && y % 4 == 0. It is certainly counterintuitive that this could be more efficient since among the three divisibility tests (4, 100 and 400) the one by 100 is the only one that can never provide a definitive answer and a second divisibility test (by 4 or 400) is always required. However, measurements [1] in x86_64 suggest this is 3x more efficient! A possible explanation is that checking divisibility by 100 first implies a split in the execution path with probabilities of (1%, 99%) rather than (25%, 75%) when divisibility by 4 is checked first. This decreases the entropy of the branching distribution which seems to help prediction. Given that y belongs to [-32767, 32767] [time.cal.year.members], a more efficient algorithm [2] to check divisibility by 100 is used (instead of y % 100 != 0). Measurements suggest that this optimization improves performance by 20%. The patch adds a test that exhaustively compares the result of this implementation with the ubiquitous one for all y in [-32767, 32767]. Although its completeness, the test completes in a matter of seconds. References: [1] https://stackoverflow.com/a/60646967/1137388 [2] https://accu.org/journals/overload/28/155/overload155.pdf#page=16 libstdc++-v3/ChangeLog: * include/std/chrono: * testsuite/std/time/year/2.cc: New test. --- libstdc++-v3/include/std/chrono | 19 ++++++++- libstdc++-v3/testsuite/std/time/year/2.cc | 52 +++++++++++++++++++++++ 2 files changed, 70 insertions(+), 1 deletion(-) create mode 100644 libstdc++-v3/testsuite/std/time/year/2.cc -- 2.29.2 diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 7840099d743..b777acdd4a2 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -1597,7 +1597,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION constexpr bool is_leap() const noexcept - { return _M_y % 4 == 0 && (_M_y % 100 != 0 || _M_y % 400 == 0); } + { + // Testing divisibility by 100 first gives better performance, that is, + // return (_M_y % 100 != 0 || _M_y % 400 == 0) && _M_y % 4 == 0; + + // It gets even faster if _M_y is in [-536870800, 536870999] (which is the case here) and + // _M_y % 100 is replaced by __is_multiple_of_100 below. + + // References: + // [1] https://github.com/cassioneri/calendar + // [2] https://accu.org/journals/overload/28/155/overload155.pdf#page=16 + + constexpr uint32_t __multiplier = 42949673; + constexpr uint32_t __bound = 42949669; + constexpr uint32_t __max_dividend = 1073741799; + constexpr uint32_t __offset = __max_dividend / 2 / 100 * 100; + const bool __is_multiple_of_100 = __multiplier * (_M_y + __offset) < __bound; + return (!__is_multiple_of_100 || _M_y % 400 == 0) && _M_y % 4 == 0; + } explicit constexpr operator int() const noexcept diff --git a/libstdc++-v3/testsuite/std/time/year/2.cc b/libstdc++-v3/testsuite/std/time/year/2.cc new file mode 100644 index 00000000000..e22101e305a --- /dev/null +++ b/libstdc++-v3/testsuite/std/time/year/2.cc @@ -0,0 +1,52 @@ +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +// Copyright (C) 2020-2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// Class year [time.cal.year_month_day] + +#include +#include + +// Slow but clear test for leap year. +constexpr bool +is_leap_year(const std::chrono::year& y) noexcept +{ + const int n = static_cast(y); + return n % 4 == 0 && (n % 100 != 0 || n % 400 == 0); +} + +void test01() +{ + using namespace std::chrono; + + year y{-32767}; + while (y < year{32767}) { + VERIFY( y.is_leap() == is_leap_year(y) ); + ++y; + } + + // One more for y = 32767. + VERIFY( year{32767}.is_leap() == is_leap_year(year{32767}) ); +} + +int main() +{ + test01(); + return 0; +} From patchwork Tue Feb 23 13:25:10 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [4/4] libstdc++: More efficient last day of month. X-Patchwork-Submitter: Paul Richard Thomas via Gcc-patches X-Patchwork-Id: 49670 Message-Id: To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Date: Tue, 23 Feb 2021 13:25:10 +0000 From: Cassio Neri via Gcc-patches List-Id: Gcc-patches mailing list 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(-) } constexpr -- 2.29.2 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(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};