From patchwork Sat Nov 11 22:59:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cassio Neri X-Patchwork-Id: 1862751 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=m5a5tEt7; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SSWPc6ntkz1yRV for ; Sun, 12 Nov 2023 10:00:34 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 659143858439 for ; Sat, 11 Nov 2023 23:00:32 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by sourceware.org (Postfix) with ESMTPS id 6EDF23858D1E; Sat, 11 Nov 2023 23:00:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6EDF23858D1E Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 6EDF23858D1E Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::333 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699743620; cv=none; b=RM98KfO/AQMH9izotzSWMlxoA/VE4CRLOEgCkJB7FnNBI5SL0SEExpAuzM/ayZyEBnJ/85DsMiDPICB/iREC7AvkvsjAVIGg5gmi4sGMVopep0SvGirk2/jHEBHInGO/bx2/XMWBU5QyeiLjloz4aTX817RwYf13UCEVaZq/3MA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699743620; c=relaxed/simple; bh=PELz5zxia0lyyoYgqwb5lXJ0yLt18MGHS77NqHnZSDI=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=iMnUOVrLOFUPpuTF4eCJczFJdt+rTkD1oJjF21PxFG6dklumI1NSlJCCw/YAS1sTrh5Di4bPubMpFOIZ+DkDLXKV2y3pVNn/jPZhKSYWY+Hyj78+/UCPXQi0inhr84innvV457Rf3XOTNMQGZYDkuvo+yGMPNFN+fFC05VU2+PI= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x333.google.com with SMTP id 5b1f17b1804b1-40790b0a224so24507455e9.0; Sat, 11 Nov 2023 15:00:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1699743616; x=1700348416; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=ktApP3lcJ8qijh8/HnK/qTtxcdHFJm3PSdslZqHWgJY=; b=m5a5tEt7ZxQAtEaC0MOdWen5YRDahKvO6wykNMVBsc+KhdNG+WpsTkG413RcqQMZYz wdxmtrNKjkJDcsC9yhDaTWU/zRL7H5S3gq3rldcl7qzoLpfaG6YnWqsPFRhHX/ZsfTRX iQPNk7+y4RODSPSNvSU045YUqXGvn+s4UR1ICK1RznhU4c2RqIFtQwMgsgPMsl0okeqV u4F0dPOhtdNnoRTEAd+UAyfzlPCgeSROd3uJQ0azdIHZR+2tRy8W8T+HEwMyWXP/xFcs 8F76Xb6ncGAdctNcyhvQhfI78vdnrVORV1Wwq4UssnuqOz1NF2QVrQNsp0615Pud4FqU d/wg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699743616; x=1700348416; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=ktApP3lcJ8qijh8/HnK/qTtxcdHFJm3PSdslZqHWgJY=; b=oZ1U5/oeRoYVZ9vmXXpyE8YCyBIjysmHyn5i/MN/GTJKhw7R8iH1HVgfTaSYZtiqTk 3Iru+PSwdBrGop3Tx2q4fWMnz8wSMeXb/MOsQr9FhJTUw2lgR/baqj/Bu+AglWqPyZBA iH3UcA0Fa5qXtI/y9z7sS3vQtjfxgEHEuhtnu1wCZ4DmAvIdzTq53AuDzmHRhKGQUePY sskWqZctnOa9y+1ywA3e3nSYzlOBq6LKmSEmbkoJxtijOEgp8tFDYWQM+E5T+8HhoSSP VGVo7q7tPtu43wcGb9f1/4CvOIDpSjpu1bmP6DjUltYr7MTiRYgH2gbI/p31jL9CRej7 AxwQ== X-Gm-Message-State: AOJu0YyCczg8QLITnpN2BrimHrFwyaKLwBElG74T/QYkyMWsz6rBCEyF U7MhtnxUQ8PEhl1BoaRXZTo09t6NbTg= X-Google-Smtp-Source: AGHT+IEC/NLUeNO8q0V2g+0RZUYpsz8s3L8cfrHQeXsMXfQ+Rlp/y1D5uJDzMmUmqwirsl+QDyXkCA== X-Received: by 2002:a1c:7206:0:b0:3fe:4cbc:c345 with SMTP id n6-20020a1c7206000000b003fe4cbcc345mr2383564wmc.41.1699743615611; Sat, 11 Nov 2023 15:00:15 -0800 (PST) Received: from othello.cust.communityfibre.co.uk ([2a02:6b64:8086:0:f9dd:28dd:c9b9:d8f4]) by smtp.gmail.com with ESMTPSA id z22-20020a1c4c16000000b00403b63e87f2sm3295103wmf.32.2023.11.11.15.00.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 11 Nov 2023 15:00:15 -0800 (PST) From: Cassio Neri To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Cc: Cassio Neri Subject: [PATCH v3] libstdc++: Simplify year::is_leap(). Date: Sat, 11 Nov 2023 22:59:50 +0000 Message-ID: <20231111225950.4989-1-cassio.neri@gmail.com> X-Mailer: git-send-email 2.41.0 MIME-Version: 1.0 X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org 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 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