[1/4] libstdc++: More efficient date from days.
diff mbox series

Message ID CAOfgUPi_S8_Cind-6zLtQmQMMSWB5hqSLVS7exhnFiSUckVZVA@mail.gmail.com
State New
Headers show
Series
  • [1/4] libstdc++: More efficient date from days.
Related show

Commit Message

Marek Polacek via Gcc-patches Feb. 23, 2021, 1:24 p.m. 
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

Comments

Marek Polacek via Gcc-patches Feb. 24, 2021, 5:28 p.m. | #1 
On 23/02/21 13:24 +0000, Cassio Neri via Libstdc++ wrote:
>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.


Thanks! I'm committing this to trunk (it only changes new C++20
material so OK during stage 4 ... and anyway it's both faster and
better tested than the old code).

I've tweaked it slightly to keep some lines below 80 columns, but no
changes except whitespace.
Marek Polacek via Gcc-patches Feb. 25, 2021, 11:56 a.m. | #2 
On 24/02/21 17:28 +0000, Jonathan Wakely wrote:
>On 23/02/21 13:24 +0000, Cassio Neri via Libstdc++ wrote:

>>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.

>

>Thanks! I'm committing this to trunk (it only changes new C++20

>material so OK during stage 4 ... and anyway it's both faster and

>better tested than the old code).

>

>I've tweaked it slightly to keep some lines below 80 columns, but no

>changes except whitespace.


I've made the attached tweak, to avoid a narrowing conversion from
long to int. Tested x86_64-linux, committed to trunk.
commit 75c74a83acee3f51e6753b8159fa600fe2d86810
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Feb 25 11:48:18 2021

    libstdc++: Fix narrowing conversion in year_month_day [PR 99265]
    
    libstdc++-v3/ChangeLog:
    
            PR libstdc++/99265
            * include/std/chrono (year_month_day::_S_from_days): Cast long
            to int explicitly.

diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index feb2c2a1fad..eef503af274 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -2481,8 +2481,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       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}};
+      return year_month_day{chrono::year{static_cast<int>(__y1 + __z2)},
+			    chrono::month{__m1}, chrono::day{__d1}};
     }
 
     // Days since 1970/01/01.
Marek Polacek via Gcc-patches Feb. 25, 2021, 1:46 p.m. | #3 
Hi Jonathan,

The issue is that I didn't cast __dp.count() to uint32_t:

-      const auto __r0 = __dp.count() + __r2_e3;
+      const auto __r0 = static_cast<uint32_t>(__dp.count()) + __r2_e3;

The above would be a better fix. Indeed, __r0 belongs to [0, 2^32[ which allows
all arithmetics that follow to be performed on uint32_t values. For performance
this is better than using signed integers.

I wrongly assumed __dp.count() was int32_t which would make __r0 also uint32_t.
It turns out, it is int64_t so are __r0 and other expressions including
__y1 + __z2. Hence, we're losing a bit of performance. I'm glad the compiler
warned us. (Although I don't understand why I didn't get the warning.)

Thanks,
Cassio.

On Thu, Feb 25, 2021 at 11:56 AM Jonathan Wakely <jwakely@redhat.com> wrote:
>

> On 24/02/21 17:28 +0000, Jonathan Wakely wrote:

> >On 23/02/21 13:24 +0000, Cassio Neri via Libstdc++ wrote:

> >>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.

> >

> >Thanks! I'm committing this to trunk (it only changes new C++20

> >material so OK during stage 4 ... and anyway it's both faster and

> >better tested than the old code).

> >

> >I've tweaked it slightly to keep some lines below 80 columns, but no

> >changes except whitespace.

>

> I've made the attached tweak, to avoid a narrowing conversion from

> long to int. Tested x86_64-linux, committed to trunk.

>
Marek Polacek via Gcc-patches Feb. 25, 2021, 2:02 p.m. | #4 
On 25/02/21 13:46 +0000, Cassio Neri via Libstdc++ wrote:
>Hi Jonathan,

>

>The issue is that I didn't cast __dp.count() to uint32_t:

>

>-      const auto __r0 = __dp.count() + __r2_e3;

>+      const auto __r0 = static_cast<uint32_t>(__dp.count()) + __r2_e3;

>

>The above would be a better fix. Indeed, __r0 belongs to [0, 2^32[ which allows

>all arithmetics that follow to be performed on uint32_t values. For performance

>this is better than using signed integers.


OK, I'll make that change shortly, thanks.

>I wrongly assumed __dp.count() was int32_t which would make __r0 also uint32_t.

>It turns out, it is int64_t so are __r0 and other expressions including

>__y1 + __z2. Hence, we're losing a bit of performance. I'm glad the compiler

>warned us. (Although I don't understand why I didn't get the warning.)


You won't see it without -Wsystem-headers because warnings are
suppressed by default in libstdc++ headers.

There are a few annoyances in <chrono> due to the unnecessary use of
64-bit integers, which then causes narrowing conversions because some
constructors take int parameters.
e.g. https://github.com/cplusplus/draft/pull/4184
Marek Polacek via Gcc-patches Feb. 25, 2021, 2:19 p.m. | #5 
On 25/02/21 14:02 +0000, Jonathan Wakely wrote:
>On 25/02/21 13:46 +0000, Cassio Neri via Libstdc++ wrote:

>>Hi Jonathan,

>>

>>The issue is that I didn't cast __dp.count() to uint32_t:

>>

>>-      const auto __r0 = __dp.count() + __r2_e3;

>>+      const auto __r0 = static_cast<uint32_t>(__dp.count()) + __r2_e3;

>>

>>The above would be a better fix. Indeed, __r0 belongs to [0, 2^32[ which allows

>>all arithmetics that follow to be performed on uint32_t values. For performance

>>this is better than using signed integers.

>

>OK, I'll make that change shortly, thanks.


We still need to cast to int for the return value though, because
converting from uint32_t to int is still narrowing.
Marek Polacek via Gcc-patches Feb. 25, 2021, 4:57 p.m. | #6 
On 25/02/21 14:19 +0000, Jonathan Wakely wrote:
>On 25/02/21 14:02 +0000, Jonathan Wakely wrote:

>>On 25/02/21 13:46 +0000, Cassio Neri via Libstdc++ wrote:

>>>Hi Jonathan,

>>>

>>>The issue is that I didn't cast __dp.count() to uint32_t:

>>>

>>>-      const auto __r0 = __dp.count() + __r2_e3;

>>>+      const auto __r0 = static_cast<uint32_t>(__dp.count()) + __r2_e3;

>>>

>>>The above would be a better fix. Indeed, __r0 belongs to [0, 2^32[ which allows

>>>all arithmetics that follow to be performed on uint32_t values. For performance

>>>this is better than using signed integers.

>>

>>OK, I'll make that change shortly, thanks.

>

>We still need to cast to int for the return value though, because

>converting from uint32_t to int is still narrowing.


I've committed this now.

Tested powerpc64le-linux, committed to trunk.
commit a47cec4ca7302e65f63490ad7f251c5a469bc0e0
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Feb 25 16:57:20 2021

    libstdc++: Use uint32_t for all year_month_day::_S_from_days arithmetic
    
    libstdc++-v3/ChangeLog:
    
            * include/std/chrono (year_month_day::_S_from_days): Perform
            all calculations with type uint32_t.

diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index eef503af274..fcdaee7328e 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -2455,7 +2455,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       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 __r0 = static_cast<uint32_t>(__dp.count()) + __r2_e3;
 
       const auto __n1 = 4 * __r0 + 3;
       const auto __q1 = __n1 / 146097;

Patch
diff mbox series 

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;
+}