[PATCH 1/4] libstdc++: More efficient date from days.
Cassio Neri
cassio.neri@gmail.com
Tue Feb 23 13:24:50 GMT 2021
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
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<unsigned>(__z - __era * 146097);
- const auto __yoe
- = (__doe - __doe / 1460 + __doe / 36524 - __doe / 146096) / 365;
- const auto __y = static_cast<days::rep>(__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<uint32_t>(-1468000);
+ constexpr auto __r2_e3 = static_cast<uint32_t>(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<uint64_t>(1) << 32;
+ const auto __n2 = 4 * __r1 + 3;
+ const auto __u2 = static_cast<uint64_t>(2939745) * __n2;
+ const auto __q2 = static_cast<uint32_t>(__u2 / __p32);
+ const auto __r2 = static_cast<uint32_t>(__u2 % __p32) / 2939745 / 4;
+
+ constexpr auto __p16 = static_cast<uint32_t>(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
+// <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;
+
+ // [-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;
+}
--
2.29.2
More information about the Gcc-patches
mailing list