From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2181) id 63511387086A; Wed, 24 Feb 2021 18:52:14 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 63511387086A MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Jonathan Wakely To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r11-7370] libstdc++: More efficient days from date X-Act-Checkin: gcc X-Git-Author: Cassio Neri X-Git-Refname: refs/heads/master X-Git-Oldrev: 3dfd5493cf9798d46dd24ac32becc54d5074271e X-Git-Newrev: 97d6161f6a7fa712622fc4e384fcb07e2ff5a127 Message-Id: <20210224185214.63511387086A@sourceware.org> Date: Wed, 24 Feb 2021 18:52:14 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 24 Feb 2021 18:52:14 -0000 https://gcc.gnu.org/g:97d6161f6a7fa712622fc4e384fcb07e2ff5a127 commit r11-7370-g97d6161f6a7fa712622fc4e384fcb07e2ff5a127 Author: Cassio Neri Date: Wed Feb 24 17:33:45 2021 +0000 libstdc++: More efficient days from date 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 (year_month_day::_M_days_since_epoch): New implementation. * testsuite/std/time/year_month_day/4.cc: New test. Diff: --- libstdc++-v3/include/std/chrono | 38 +++++++----- .../testsuite/std/time/year_month_day/4.cc | 71 ++++++++++++++++++++++ 2 files changed, 94 insertions(+), 15 deletions(-) diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 085e487a7ed..b03167863cd 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -2466,26 +2466,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const auto __d1 = __d0 + 1; return year_month_day{chrono::year{__y1 + __z2}, chrono::month{__m1}, - chrono::day{__d1} - }; + chrono::day{__d1}}; } - // 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..c8a6768ad08 --- /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) 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; +}