From patchwork Sat Nov 11 01:44:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cassio Neri X-Patchwork-Id: 1862644 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=V6P9466P; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; 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 [8.43.85.97]) (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 4SRz6C3Gsfz1yRV for ; Sat, 11 Nov 2023 12:45:23 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 71093385696A for ; Sat, 11 Nov 2023 01:45:21 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-yb1-xb31.google.com (mail-yb1-xb31.google.com [IPv6:2607:f8b0:4864:20::b31]) by sourceware.org (Postfix) with ESMTPS id 36CC23858413; Sat, 11 Nov 2023 01:45:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 36CC23858413 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 36CC23858413 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::b31 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699667111; cv=none; b=pd+Xl/YXGFBk+nVQOhyxsdIpXOubG4/rjroWVkEAf5DuFPMbfr7gMRLaj0goV1ji/2z/4nSMs6c/X14jqaw+G0fCE0Fbh4XMfDU2fHy8OSsbSuYRxetX8oaoo6IwnETqzoR//Jer9yT7UMthNO4Smiczw/hjslw9V0wk4q1/VFo= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699667111; c=relaxed/simple; bh=PQ4jhw/YQ16A5bfoiFQZII6MQG4c6LT8WAs6b3wnVi8=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=n8lWPVXyULzsYSZZrC1PWX6n2AErtZroOE34xRviaSm+EpSvRrBu7JtvgT5RCI7Ccb/S84GYXCXXSlUCBcJp4hDyg1tYTVF5hLQlFc3xbBsurnOAPyFE2aCiaH9xVuZcjmjfCalD14OBkeQZEVRLAevnl/QSUJca8dVnUq7tPe8= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-yb1-xb31.google.com with SMTP id 3f1490d57ef6-d852b28ec3bso2887981276.2; Fri, 10 Nov 2023 17:45:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1699667108; x=1700271908; darn=gcc.gnu.org; h=to:subject:message-id:date:from:reply-to:mime-version:from:to:cc :subject:date:message-id:reply-to; bh=KAbE5VVGmfsfRaOsdfFt508Si5KP0Bu+RnJIvUytKog=; b=V6P9466PyQpJ5CIzkM5yppEZbOkmddJM9xty1flzDJnRJxiDzWOr+D7n29KlFHBfNp +gIH5/Nb+R/hG599vgRgWhusPmVtWVC4kx73Qy0E7mnTgco+hmGbUBYBP1SGI9pEg9+C hJFlPj33pQ42JetDvm0+vymEB0JTRBM011Y32BHxKYgkxu3+QaiaGeC0ZP5/xeSojOa9 kLzc0YO2aDdoA9Y1k+KvxbubxlSI9Fy1vownTnCS3+i3kKXP44AcLefG7A2U/rJ9ISFZ SP7FrHkI9ou5D23o40yc3HacM03M2Gsj4ImCLD1ziBF9PsixnMHIzIZus1fuU9oY5slk Ft+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699667108; x=1700271908; h=to:subject:message-id:date:from:reply-to:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=KAbE5VVGmfsfRaOsdfFt508Si5KP0Bu+RnJIvUytKog=; b=J6rO7mJohnqg9PxIeGYefxZ+UoMg/JjSe8sNquPyD2pon38+UPTE9AJBSU/RigDZXl wGX1/fLTXvYFp/xEp3HQ9VDQSGCXPwYx1MkLzZXEqrqFn82/VkAP6+uBOEUI0mGonfR9 CFXzoLjl3nxZRjRqzFhETtzsuxgBXeb5hjHUPWZQw/Y6GtgJEL5xABUwa/Dr9JbiF8CT AlpYvb1XyUBARod2eCCthVAlrp7BHb8216ABeO/NmGwj1qQ/NlWej8oD28lyQQf3v2wY 759YUKkQnCBX63jkHYobWQBmbHw4eNL6fA5KuG8vAfRUki3E6+DpT0oECICIT/hHZTnG YIVw== X-Gm-Message-State: AOJu0Yyh63nBpcvyexjX5ACV+bk7Aoakq1pqZTTWl66LJ3LTrLYrUHU2 mY62tBtf1QLWeR269N5G784TpSnUKumn/XMboYvKnjgFrjw= X-Google-Smtp-Source: AGHT+IGjIjzD97x4LGu1SGNdKv8FFFE+3rvK9t980sh4tykaczfzLHOuqhxq+DXzqVRxwc6pIUxchz0fWggGNrf9rLw= X-Received: by 2002:a25:48a:0:b0:da0:46fa:cabe with SMTP id 132-20020a25048a000000b00da046facabemr764423ybe.7.1699667108291; Fri, 10 Nov 2023 17:45:08 -0800 (PST) MIME-Version: 1.0 From: Cassio Neri Date: Sat, 11 Nov 2023 01:44:57 +0000 Message-ID: Subject: [PATCH v2] Simplify year::is_leap(). To: "libstdc++" , Gcc-patches X-Spam-Status: No, score=-8.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, HTML_MESSAGE, 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: , Reply-To: cassio.neri@gmail.com 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 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: --- libstdc++-v3/include/std/chrono | 38 ++++++++++++++++++-------------------- 1 file changed, 18 insertions(+), 20 deletions(-) diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono index 10e868e5a03..5707ed002a2 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