Use a better algorithm to calculate n % 7, taking into account that the divisor is a Mersenne number. This is explained in this two-part lightning talk at CppCon 2024 [1, 2].
Roughly speaking, the algorithm is used for n = sys_days but it has a precondition that doesn't hold for all values of sys_days. However, it does hold for every value coming out of year_month_day::operator sys_days(). Nevertheless, there's an issue because the conversion is done in two steps: year_month_day -> sys_days -> weekday and in the second step the information that the input sys_days was obtained from the first step (so the precondition holds) is lost. In the talk a single function performs the two steps and uses the optimization. Unless the standard adds a similar function (e.g. a weekday constructor) or this is added as an extension (not done here), this is not an option for libstdc++. The issue is adressed in the following way. At the end of the fist step, the code informs the compiler, through an [[assume]] attribute that the precondition holds. Then, at the beginning of the second step, the code checks, through __builtin_constant_p, if the precondition holds, in which case, it uses the better algorithm or, otherwise, it falls back to n % 7. The idea is illustrated in [3] which compares code generation (with and without the optimization) and provides an exhaustive test of correctness. A benchmark is shown in [4]. References: [1] https://youtu.be/64mTEXnSnZs [2] https://youtu.be/bnVkWEjRNeI [3] https://godbolt.org/z/TMMcKj8Gv [4] https://quick-bench.com/q/VPtEBjGDmmB4QEG2IDjIvfU6WzA libstdc++-v3/ChangeLog: * include/std/chrono: Add postcondition to year_month_date::operator sys_days and check this condition in weekday::_S_from_days. * testsuite/std/time/weekday/1.cc: Add tests for special values. --- The approach might be somewhat controversial and might need to be discussed. The problem is that passing information from [[assume]] to __builtin_constant_p is quite fragile in 3 different ways. 1) The distance in source code between [[assume]] and __builtin_constant_p makes hard to understand why they are there in the first place. A reader who doesn't know the full picture might feel tempted to remove either of these lines. 2) Even cosmetic changes in the conditions of [[assume]] or __builtin_constant_p might break the compiler's chain of thought and thus, the optimization. 3) Similarly to 2, changes in the compiler code that handles [[assume]] or __builtin_constant_p might break the optimization. If any of the issues above happens, the result will still be right but a performance regression will appear. Comments can mitigate the issues but a performance test or a test for code generation would be more effective to prevent performance regressions. Unfortunately, I don't know how either of these can be done. Version history: v2. Fix bug in v1, add tests and improve comments. v1. Initial patch. libstdc++-v3/include/std/chrono | 29 ++++++++++++++++++-- libstdc++-v3/testsuite/std/time/weekday/1.cc | 19 +++++++++++++ 2 files changed, 46 insertions(+), 2 deletions(-) diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 8eb9fd9baac..b747f46c13f 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -984,7 +984,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION static constexpr weekday _S_from_days(const days& __d) { - return weekday{__detail::__add_modulo<7>(4, __d.count())}; + const auto __days = __d.count(); + using _Up = make_unsigned_t<decltype(__days)>; + const auto __n = static_cast<_Up>(__days) + 12'687'434u; + + // This condition holds when __d = sys_days(__ymd).time_since_epoch(), + // where __ymd's type is year_month_day. + const auto __use_fast_mod7 = __n < 178'956'973u; + + if (__builtin_constant_p(__use_fast_mod7) && __use_fast_mod7) + { + // https://youtu.be/64mTEXnSnZs and https://youtu.be/bnVkWEjRNeI + const auto __wd = 613'566'757u * static_cast<uint32_t>(__n) >> 29; + [[assume(__wd != 7)]]; + return weekday{__wd}; + } + return weekday{__detail::__add_modulo<7>(4, __days)}; } public: @@ -1652,7 +1667,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION constexpr operator sys_days() const noexcept - { return sys_days{_M_days_since_epoch()}; } + { + const auto __days = _M_days_since_epoch(); + + // The assume attribute below allows weekday::_S_from_days to use a + // faster algorithm for modulus 7. + const auto __n = static_cast<unsigned>(__days.count()) + 12'687'434u; + const auto __use_fast_mod7 = __n < 178'956'973u; + [[assume(__use_fast_mod7)]]; + + return sys_days{__days}; + } explicit constexpr operator local_days() const noexcept diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc b/libstdc++-v3/testsuite/std/time/weekday/1.cc index ac05f728a55..5c98cd84a64 100644 --- a/libstdc++-v3/testsuite/std/time/weekday/1.cc +++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc @@ -66,6 +66,25 @@ constexpr_weekday() static_assert(weekday{local_days{1970y/January/1}} == Thursday); static_assert(weekday{local_days{2020y/August/21}} == Friday); + constexpr ymd_min = year::min()/January/1; + static_assert(weekday{ymd_min} == Saturday); + static_assert(weekday{sys_days{ymd_min}} - days{1} == Friday); + static_assert(weekday{local_days{ymd_min}} - days{1} == Friday); + + constexpr ymd_max = year::max()/December/31; + static_assert(weekday{ymd_max} == Sunday); + static_assert(weekday{sys_days{ymd_max}} + days{1} == Monday); + static_assert(weekday{local_days{ymd_max}} + days{1} == Monday); + + static_assert(weekday{sys_days::min()} == Wednesday); + static_assert(weekday{local_days::min()} == Wednesday); + + static_assert(weekday{sys_days::max()} == Thursday); + static_assert(weekday{local_days::max()} == Thursday); + + static_assert(weekday{sys_days{days{int64_t{1} << 32}}} == Monday); + static_assert(weekday{local_days{days{int64_t{1} << 32}}} == Monday); + static_assert(++weekday{3} == weekday{4}); static_assert(weekday{3}++ == weekday{3}); static_assert(--weekday{3} == weekday{2}); -- 2.48.1
