public inbox for libstdc++-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc r11-7370] libstdc++: More efficient days from date
@ 2021-02-24 18:52 Jonathan Wakely
0 siblings, 0 replies; only message in thread
From: Jonathan Wakely @ 2021-02-24 18:52 UTC (permalink / raw)
To: gcc-cvs, libstdc++-cvs
https://gcc.gnu.org/g:97d6161f6a7fa712622fc4e384fcb07e2ff5a127
commit r11-7370-g97d6161f6a7fa712622fc4e384fcb07e2ff5a127
Author: Cassio Neri <cassio.neri@gmail.com>
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<int>(_M_y) - (_M_m <= February);
- const auto __m = static_cast<unsigned>(_M_m);
- const auto __d = static_cast<unsigned>(_M_d);
- const auto __era = (__y >= 0 ? __y : __y - 399) / 400;
- // Year of "era" [0, 399].
- const auto __yoe = static_cast<unsigned>(__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<int>(__doe) - 719468;
- return days{__days};
+ auto constexpr __z2 = static_cast<uint32_t>(-1468000);
+ auto constexpr __r2_e3 = static_cast<uint32_t>(536895458);
+
+ const auto __y1 = static_cast<uint32_t>(static_cast<int>(_M_y)) - __z2;
+ const auto __m1 = static_cast<uint32_t>(_M_m);
+ const auto __d1 = static_cast<uint32_t>(_M_d);
+
+ const auto __j = static_cast<uint32_t>(__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<int32_t>(__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
+// <http://www.gnu.org/licenses/>.
+
+// Class year_month_day [time.cal.year_month_day]
+
+#include <chrono>
+#include <testsuite_hooks.h>
+
+// 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<sys_days>(ymd) == sys_days{n} );
+ ++n;
+ advance(ymd);
+ }
+ // One more for ymd = 32767y/December/31d and n = 11248737.
+ VERIFY( sys_days{days{11248737}} == static_cast<sys_days>(32767y/December/31d) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2021-02-24 18:52 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-02-24 18:52 [gcc r11-7370] libstdc++: More efficient days from date Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).