public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] Simplify year::is_leap().
@ 2023-11-05 18:01 Cassio Neri
  0 siblings, 0 replies; only message in thread
From: Cassio Neri @ 2023-11-05 18:01 UTC (permalink / raw)
  To: libstdc++, Gcc-patches

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

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 mathematically 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:

diff --git a/libstdc++-v3/include/std/chrono
b/libstdc++-v3/include/std/chrono
index 10e868e5a03..a34b3977d59 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -835,29 +835,27 @@ _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 y % 100 == 0 ? y % 400 == 0 : y % 16 == 0;
+ // Furthermore, if y % 100 == 0, then y % 400 == 0 is equivalent to
+ // y % 16 == 0, so we can simplify it to
+ //     return y % 100 == 0 ? y % 16 == 0 : y % 4 == 0. // #1
+ // Similarly, we can replace 100 with 25 (which is good since y % 25 == 0
+ // requires one fewer instruction than y % 100 == 0 [2]):
+ //     return y % 25 == 0 ? y % 16 == 0 : y % 4 == 0. // #2
+ // Indeed, first assume y % 4 != 0. Then y % 16 != 0 and hence, y % 4 == 0
+ // and y % 16 == 0 are both false. Therefore, #2 returns false as it
+ // should (regardless of y % 25.) Now assume y % 4 == 0. In this case,
+ // y % 25 == 0 if, and only if, y % 100 == 0, that is, #1 and #2 are
+ // equivalent. Finally, #2 is equivalent to
+ //     return (y & (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

^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2023-11-05 18:01 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-11-05 18:01 [PATCH] Simplify year::is_leap() Cassio Neri

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).