public inbox for libstdc++-cvs@sourceware.org
help / color / mirror / Atom feed
From: Jonathan Wakely <redi@gcc.gnu.org>
To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org
Subject: [gcc r12-10210] libstdc++: Simplify year::is_leap()
Date: Wed, 13 Mar 2024 09:52:59 +0000 (GMT)	[thread overview]
Message-ID: <20240313095259.3CABF3857C75@sourceware.org> (raw)

https://gcc.gnu.org/g:a7c37987a57f551794294518c6f6670690e1aad2

commit r12-10210-ga7c37987a57f551794294518c6f6670690e1aad2
Author: Cassio Neri <cassio.neri@gmail.com>
Date:   Sat Nov 11 22:59:50 2023 +0000

    libstdc++: Simplify year::is_leap()
    
    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 (year::is_leap): Clear code.
    
    (cherry picked from commit 86a0df1a6c7fe4a835620b868e76ea78d42d6620)

Diff:
---
 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 5c1b7a8daf4..0d3c0819439 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -476,29 +476,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

                 reply	other threads:[~2024-03-13  9:52 UTC|newest]

Thread overview: [no followups] expand[flat|nested]  mbox.gz  Atom feed

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20240313095259.3CABF3857C75@sourceware.org \
    --to=redi@gcc.gnu.org \
    --cc=gcc-cvs@gcc.gnu.org \
    --cc=libstdc++-cvs@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).