From patchwork Sun Nov 5 18:01:43 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Cassio Neri X-Patchwork-Id: 161748 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:8f47:0:b0:403:3b70:6f57 with SMTP id j7csp2244827vqu; Sun, 5 Nov 2023 10:02:22 -0800 (PST) X-Google-Smtp-Source: AGHT+IGcCe7qdzAKCy8OmqxXVXo48dV29pi2jrAvtKlaVL9oLaw5rQFFylLZnEOxydkopXtwf4V7 X-Received: by 2002:a05:6102:104c:b0:452:6178:642c with SMTP id h12-20020a056102104c00b004526178642cmr22739052vsq.1.1699207342052; Sun, 05 Nov 2023 10:02:22 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1699207342; cv=pass; d=google.com; s=arc-20160816; b=dLeATIRqj667/PdE1T19FbK5x4DAYlGPurKyKRDDrgAjnyORW4t+xgE2qimxTEhv1/ AEldyr0SZIZw1XowUBeTIvp2S+LK0YzCgeW5Io6zTWhYbo0pd7OOpU23ApsLCeFR/9CW xaOoxfG1ZBjJGEqJQMN+qiqRStx7lxl/uRtGjAkaI8ZbgFsGQ0FXHaK05aJcx4ba1XnJ tp+eh3nq5SSoi9+Cj4v0B+IUu0Huuqgzf3YsV7+rir8lEvvH60b68clnYy9UQymv3n4G cESU7wjC1aqJYVLb8RuylUo5Z/6IvaWu18VrFTmBcGqmrYHZrwRXKnP0qmzu2TTYweDu UK+g== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:reply-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:to:subject:message-id:date:from :mime-version:dkim-signature:arc-filter:dmarc-filter:delivered-to; bh=Bwnc0uQjAra3ahjrVh5uUVOwQDLGLy33IFPCGYUE0ew=; fh=dtVPMtB1ZqFgz1AUDGKdMG+YGuFxP/9Zc658CfWYEP0=; b=u8uTVdP0ndIkpoYbVKnlbbJmRI/O+bCC/CuGn4q/cpeC4JmjawST0gkWeoD1VIeR4T /2noJAgTRYJaasEqFMihS4AOshYaDX/ae+JAB4OG23gC1KUbQQQZeeyNfZ5MT2C/6jS/ 2FQiXgLY54XNOUYuwO2fLXlkSzYZpjXNavkDGp49cPQmOxQ9M5FpnYFwBYuoSdFQIh7F mqI6dSOMJU1dmuRIHhF4soIRhi/h5tOmkyfJFxXitFD11aDeGSp/7szh7LOsb094TfPb JKe2QIzjMH3JICv/KnaSzW/7OK+Jt80GCZWseRBNBLe3YXslHL3Fc/kfqJGzViUNd9KK pEdw== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=U27JiZkT; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id u3-20020a0ced23000000b0066fccf78119si4510619qvq.295.2023.11.05.10.02.21 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 05 Nov 2023 10:02:22 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=U27JiZkT; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CAF533858C54 for ; Sun, 5 Nov 2023 18:02:21 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-yb1-xb29.google.com (mail-yb1-xb29.google.com [IPv6:2607:f8b0:4864:20::b29]) by sourceware.org (Postfix) with ESMTPS id B3F4B3858D3C; Sun, 5 Nov 2023 18:01:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B3F4B3858D3C 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 B3F4B3858D3C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::b29 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699207317; cv=none; b=sXMqGygChwoqyVLFTvZ61ko1Y48QPe+Fp8Wf3iYg68lW+3Vsem/X0zCAVc0tZmjNby6O1a/g06PGhyE7kSRMvw5n5mGmsQUlqoIr7lk4nudQYR+KY2pqdAvSx1dFzI0MpnSTbt0sWx3J2eETXIV6pbqGQZuo7KyevF3miTzKX/I= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1699207317; c=relaxed/simple; bh=u7Y8h0FOgaFj6ThkSuFPc16HQid2Wx1O/HzFYT5M/fc=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=umqMn26gwRaWcg3hSAk9LIaM4INDDuWuQ7eHxOAL5M7okiFdSAtbRyNqmZR4tJXI6/xCR2UW9dTUd1hJDkCX03tM0KC5V4+WDC92ANbWPQBhAGyD8DtT5sFvKG/W7y/0MAKnLG9qCY1ttjIAdhkQNRv0/cZZzA6EHbcFSAxhwh0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-yb1-xb29.google.com with SMTP id 3f1490d57ef6-da3b4b7c6bdso3737841276.2; Sun, 05 Nov 2023 10:01:55 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1699207315; x=1699812115; 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=Bwnc0uQjAra3ahjrVh5uUVOwQDLGLy33IFPCGYUE0ew=; b=U27JiZkT0GqTEWULzrJcUHM7AJPyJ548r1+Dlg/qdnMGihg0hTPx62+nqNikcEB/a/ +fx4zALsWTeotq/Jp9rNRSzDuvRQ8T6gNaaaz4nem5VHHuISMlc19mTaaNmhD6m7gTfM Oqr66nkY2Uf8FFturN/A+cNQkL2p55BA+1VugoKmzHEl6MFu6ljnRqCSOK0NKsE2CDSA dqQR733GwFamvJbxIbQf16lWfmBFtsbss3rdTadv1sLLyY9lsY33fPa6Y2LsI8xu2yMW lwSHzBcMhCCGBSI/Na7l0OqCkZmQXJnanBDiDVzzRi7as1KqcnnxXBRQbLoDSAxE6y0y R2QA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1699207315; x=1699812115; 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=Bwnc0uQjAra3ahjrVh5uUVOwQDLGLy33IFPCGYUE0ew=; b=g4R/K3li7HPlAFSHFujBsOYHH5/F7bzSvgS0/m0A4w04jSQOOnuBx8UXRoPPNYTzay EOtfOPyicB2TDWuR+76TrdvfZF9dH5wXrw/z57KBCZn5cYbaLz0cjepHvJUUd3uVVdKU S072lgi/LXtds13AIHZozi/LVhXuUGt5qlbzX/n2qZHH7TPzg78YhaAaQZF1JhyI0fMj aUMBgmHsTxmgvscO2i0F/tVBBdv8oyvJwwNjzBoUEjJSTa2eGWpeZm+rrcMRlBn2KEJm sjzRzxuFkEh5+foBgn/mgMxlAGCFTn8sRIxqTiepPNHLDOf8ADQxcCF+IS+KKdNVLhl/ KoxQ== X-Gm-Message-State: AOJu0Ywa6hw7qs0J7TFKzfx1QEHSOlWjYvM2C5NMBznX4SKaucazISg+ BF8IiPPVvIu33l02iVtv5J3QQuThIDhAWc8+1mkJMMNS4sE= X-Received: by 2002:a25:ae04:0:b0:d9b:353b:9e24 with SMTP id a4-20020a25ae04000000b00d9b353b9e24mr26550517ybj.11.1699207314676; Sun, 05 Nov 2023 10:01:54 -0800 (PST) MIME-Version: 1.0 From: Cassio Neri Date: Sun, 5 Nov 2023 18:01:43 +0000 Message-ID: Subject: [PATCH] Simplify year::is_leap(). To: "libstdc++" , Gcc-patches X-Spam-Status: No, score=-8.2 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+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1781748037561605520 X-GMAIL-MSGID: 1781748037561605520 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