[PATCH 1/4] libstdc++: More efficient date from days.

[PATCH 1/4] libstdc++: More efficient date from days.

[Cassio Neri]

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

Re: [PATCH 1/4] libstdc++: More efficient date from days.

[Jonathan Wakely]

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.

Re: [PATCH 1/4] libstdc++: More efficient date from days.

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1722 bytes --]

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.


[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 974 bytes --]

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.

Re: [PATCH 1/4] libstdc++: More efficient date from days.

[Cassio Neri]

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

Re: [PATCH 1/4] libstdc++: More efficient date from days.

[Jonathan Wakely]

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

Re: [PATCH 1/4] libstdc++: More efficient date from days.

[Jonathan Wakely]

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.

Re: [PATCH 1/4] libstdc++: More efficient date from days.

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 830 bytes --]

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.



[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 947 bytes --]

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;