From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 67E003858C54 for ; Thu, 14 Apr 2022 18:15:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 67E003858C54 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-659-36Rr2T6YNMqe600Q7zNB1w-1; Thu, 14 Apr 2022 14:15:54 -0400 X-MC-Unique: 36Rr2T6YNMqe600Q7zNB1w-1 Received: by mail-qv1-f72.google.com with SMTP id e10-20020a0562140d8a00b00443c3595342so5024185qve.8 for ; Thu, 14 Apr 2022 11:15:54 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=fLzOC09ANZk4o3p9N1JtSreVcgHnJ6byP+9SnMud3S0=; b=xLgupoqXWUOfFPHhkDwnZBH3mTqgjT0Sawp6ijZxyQZAMpGe/cYwOEYY51gpbO9GI3 16bMIzj8yhYBdoCKZIniByyrKjbDY428fcnHMmBIcut1Gkvou7PBp57WHR7fbmjnfYvE /JnDGkq6RVqn0sE7nIrFbXSMc1G9ldKPcWNz3Iq2xdxRFaUPASUYNQrlz/He90agPjSe d0V5zZGned27RKg8pHcebQxc2v90mOv7ODz9vwpVZugBNSQcTnC42fwP8JRRvbuPPJdz hQ0mZ9eJCYO5e8fhJ+Lg/VNdnsFMV3FO47/9/apFMWi9SyIFVisTIk6VVXpJA5jC0HpH W4bA== X-Gm-Message-State: AOAM530yjOfopT7DAO/8QT+tCTTjW+hTBFDIpiRwpcYrdFBWSxOfpNaS x1UD4neAE7HYpgQ/Rb0u2+wT1LYMgpBj6n/JYAmoQPLO1L/ZNCoP8hUrduXg5+NixL7cAZMt+s8 YW5N+ssnVot+z+tE= X-Received: by 2002:ac8:5e13:0:b0:2e1:cd7e:a29e with SMTP id h19-20020ac85e13000000b002e1cd7ea29emr2705855qtx.31.1649960154050; Thu, 14 Apr 2022 11:15:54 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyO3viQI6Gg/UB2a1RrNuabrjvJZy2btNpOvEReDS8jY0RXKHNn3RVvtZt558FzTJnM7Xwt2A== X-Received: by 2002:ac8:5e13:0:b0:2e1:cd7e:a29e with SMTP id h19-20020ac85e13000000b002e1cd7ea29emr2705839qtx.31.1649960153793; Thu, 14 Apr 2022 11:15:53 -0700 (PDT) Received: from localhost.localdomain (ool-18e40894.dyn.optonline.net. [24.228.8.148]) by smtp.gmail.com with ESMTPSA id i2-20020a05620a248200b00680f3c2f888sm1393165qkn.126.2022.04.14.11.15.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 14 Apr 2022 11:15:53 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH] libstdc++: Optimize std::has_single_bit Date: Thu, 14 Apr 2022 14:15:46 -0400 Message-Id: <20220414181546.306201-1-ppalka@redhat.com> X-Mailer: git-send-email 2.36.0.rc2.10.g1ac7422e39 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-14.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 14 Apr 2022 18:15:57 -0000 This reimplements std::has_single_bit using the well-known bit-twiddilng trick[1], which is much faster than popcount on x86_64. Note that when __x is signed and maximally negative then this implementation invokes UB due to signed overflow, whereas the previous implementation would return true. This isn't a problem for has_single_bit because it accepts only unsigned types, but it is a potential problem for the unconstrained __has_single_bit. Should __has_single_bit continue to handle this non-standard case correctly for sake of backwards compatibility? Tested on x86_64-pc-linux-gnu. [1]: http://www.graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 libstdc++-v3/ChangeLog: * include/std/bit (__has_single_bit): Define in terms of bitwise-and, not popcount. --- libstdc++-v3/include/std/bit | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libstdc++-v3/include/std/bit b/libstdc++-v3/include/std/bit index ef19d649e32..621ee4a9b95 100644 --- a/libstdc++-v3/include/std/bit +++ b/libstdc++-v3/include/std/bit @@ -316,7 +316,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template constexpr bool __has_single_bit(_Tp __x) noexcept - { return std::__popcount(__x) == 1; } + { return __x != 0 && (__x & (__x - 1)) == 0; } template constexpr _Tp -- 2.36.0.rc2.10.g1ac7422e39