| Message ID | 20231111225950.4989-1-cassio.neri@gmail.com |
|---|---|
| State | New |
| Headers | show |
| Series | [v3] libstdc++: Simplify year::is_leap(). | expand |
On Sat, 11 Nov 2023 at 23:00, Cassio Neri <cassio.neri@gmail.com> wrote: > > The current implementation returns > (_M_y & (__is_multiple_of_100 ? 15 : 3)) == 0; > where __is_multiple_of_100 is calculated using an obfuscated algorithm which > saves one ror instruction when compared to _M_y % 100 == 0 [1]. > > In leap years calculation, it's correct to replace the divisibility check by > 100 with the one by 25. It turns out that _M_y % 25 == 0 also saves the ror > instruction [2]. Therefore, the obfuscation is not required. > > [1] https://godbolt.org/z/5PaEv6a6b > [2] https://godbolt.org/z/55G8rn77e > > libstdc++-v3/ChangeLog: > > * include/std/chrono: Clear code. > --- > > Previous versions of this patch failed to apply. Hope this one works. > > Good for trunk? Yes, thanks - pushed to trunk. > > libstdc++-v3/include/std/chrono | 40 ++++++++++++++++----------------- > 1 file changed, 20 insertions(+), 20 deletions(-) > > diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono > index 10e868e5a03..e18f57229e8 100644 > --- a/libstdc++-v3/include/std/chrono > +++ b/libstdc++-v3/include/std/chrono > @@ -835,29 +835,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > constexpr bool > is_leap() const noexcept > { > - // Testing divisibility by 100 first gives better performance, that is, > - // return (_M_y % 100 != 0 || _M_y % 400 == 0) && _M_y % 4 == 0; > - > - // It gets even faster if _M_y is in [-536870800, 536870999] > - // (which is the case here) and _M_y % 100 is replaced by > - // __is_multiple_of_100 below. > + // Testing divisibility by 100 first gives better performance [1], i.e., > + // return _M_y % 100 == 0 ? _M_y % 400 == 0 : _M_y % 16 == 0; > + // Furthermore, if _M_y % 100 == 0, then _M_y % 400 == 0 is equivalent > + // to _M_y % 16 == 0, so we can simplify it to > + // return _M_y % 100 == 0 ? _M_y % 16 == 0 : _M_y % 4 == 0. // #1 > + // Similarly, we can replace 100 with 25 (which is good since > + // _M_y % 25 == 0 requires one fewer instruction than _M_y % 100 == 0 > + // [2]): > + // return _M_y % 25 == 0 ? _M_y % 16 == 0 : _M_y % 4 == 0. // #2 > + // Indeed, first assume _M_y % 4 != 0. Then _M_y % 16 != 0 and hence, > + // _M_y % 4 == 0 and _M_y % 16 == 0 are both false. Therefore, #2 > + // returns false as it should (regardless of _M_y % 25.) Now assume > + // _M_y % 4 == 0. In this case, _M_y % 25 == 0 if, and only if, > + // _M_y % 100 == 0, that is, #1 and #2 are equivalent. Finally, #2 is > + // equivalent to > + // return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0. > > // References: > // [1] https://github.com/cassioneri/calendar > - // [2] https://accu.org/journals/overload/28/155/overload155.pdf#page=16 > - > - // Furthermore, if y%100 == 0, then y%400==0 is equivalent to y%16==0, > - // so we can simplify it to (!mult_100 && y % 4 == 0) || y % 16 == 0, > - // which is equivalent to (y & (mult_100 ? 15 : 3)) == 0. > - // See https://gcc.gnu.org/pipermail/libstdc++/2021-June/052815.html > - > - constexpr uint32_t __multiplier = 42949673; > - constexpr uint32_t __bound = 42949669; > - constexpr uint32_t __max_dividend = 1073741799; > - constexpr uint32_t __offset = __max_dividend / 2 / 100 * 100; > - const bool __is_multiple_of_100 > - = __multiplier * (_M_y + __offset) < __bound; > - return (_M_y & (__is_multiple_of_100 ? 15 : 3)) == 0; > + // [2] https://godbolt.org/z/55G8rn77e > + // [3] https://gcc.gnu.org/pipermail/libstdc++/2021-June/052815.html > + > + return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0; > } > > explicit constexpr > -- > 2.41.0 >
diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 10e868e5a03..e18f57229e8 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -835,29 +835,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION constexpr bool is_leap() const noexcept { - // Testing divisibility by 100 first gives better performance, that is, - // return (_M_y % 100 != 0 || _M_y % 400 == 0) && _M_y % 4 == 0; - - // It gets even faster if _M_y is in [-536870800, 536870999] - // (which is the case here) and _M_y % 100 is replaced by - // __is_multiple_of_100 below. + // Testing divisibility by 100 first gives better performance [1], i.e., + // return _M_y % 100 == 0 ? _M_y % 400 == 0 : _M_y % 16 == 0; + // Furthermore, if _M_y % 100 == 0, then _M_y % 400 == 0 is equivalent + // to _M_y % 16 == 0, so we can simplify it to + // return _M_y % 100 == 0 ? _M_y % 16 == 0 : _M_y % 4 == 0. // #1 + // Similarly, we can replace 100 with 25 (which is good since + // _M_y % 25 == 0 requires one fewer instruction than _M_y % 100 == 0 + // [2]): + // return _M_y % 25 == 0 ? _M_y % 16 == 0 : _M_y % 4 == 0. // #2 + // Indeed, first assume _M_y % 4 != 0. Then _M_y % 16 != 0 and hence, + // _M_y % 4 == 0 and _M_y % 16 == 0 are both false. Therefore, #2 + // returns false as it should (regardless of _M_y % 25.) Now assume + // _M_y % 4 == 0. In this case, _M_y % 25 == 0 if, and only if, + // _M_y % 100 == 0, that is, #1 and #2 are equivalent. Finally, #2 is + // equivalent to + // return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0. // References: // [1] https://github.com/cassioneri/calendar - // [2] https://accu.org/journals/overload/28/155/overload155.pdf#page=16 - - // Furthermore, if y%100 == 0, then y%400==0 is equivalent to y%16==0, - // so we can simplify it to (!mult_100 && y % 4 == 0) || y % 16 == 0, - // which is equivalent to (y & (mult_100 ? 15 : 3)) == 0. - // See https://gcc.gnu.org/pipermail/libstdc++/2021-June/052815.html - - constexpr uint32_t __multiplier = 42949673; - constexpr uint32_t __bound = 42949669; - constexpr uint32_t __max_dividend = 1073741799; - constexpr uint32_t __offset = __max_dividend / 2 / 100 * 100; - const bool __is_multiple_of_100 - = __multiplier * (_M_y + __offset) < __bound; - return (_M_y & (__is_multiple_of_100 ? 15 : 3)) == 0; + // [2] https://godbolt.org/z/55G8rn77e + // [3] https://gcc.gnu.org/pipermail/libstdc++/2021-June/052815.html + + return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0; } explicit constexpr
The current implementation returns (_M_y & (__is_multiple_of_100 ? 15 : 3)) == 0; where __is_multiple_of_100 is calculated using an obfuscated algorithm which saves one ror instruction when compared to _M_y % 100 == 0 [1]. In leap years calculation, it's correct to replace the divisibility check by 100 with the one by 25. It turns out that _M_y % 25 == 0 also saves the ror instruction [2]. Therefore, the obfuscation is not required. [1] https://godbolt.org/z/5PaEv6a6b [2] https://godbolt.org/z/55G8rn77e libstdc++-v3/ChangeLog: * include/std/chrono: Clear code. --- Previous versions of this patch failed to apply. Hope this one works. Good for trunk? libstdc++-v3/include/std/chrono | 40 ++++++++++++++++----------------- 1 file changed, 20 insertions(+), 20 deletions(-) -- 2.41.0