libstdc++: More efficient date from days
authorCassio Neri <cassio.neri@gmail.com>
Wed, 24 Feb 2021 17:23:56 +0000 (17:23 +0000)
committerJonathan Wakely <jwakely@redhat.com>
Wed, 24 Feb 2021 17:58:47 +0000 (17:58 +0000)
commit3dfd5493cf9798d46dd24ac32becc54d5074271e
treec9b8755d65ee0af83804c0fd5ebab7e12f1a33e2
parent9e0d8a375bae07486c839228a520eaed9004a4f3
libstdc++: More efficient date from days

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 [-1268742811248737],
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 (year_month_day::_S_from_days): New
implementation.
* testsuite/std/time/year_month_day/3.cc: New test.
libstdc++-v3/include/std/chrono
libstdc++-v3/testsuite/std/time/year_month_day/3.cc [new file with mode: 0644]