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 B72373858C54 for ; Thu, 14 Apr 2022 18:59:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B72373858C54 Received: from mail-yw1-f198.google.com (mail-yw1-f198.google.com [209.85.128.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-623-iogjPDtlOmWbDcBnpwAMJA-1; Thu, 14 Apr 2022 14:59:55 -0400 X-MC-Unique: iogjPDtlOmWbDcBnpwAMJA-1 Received: by mail-yw1-f198.google.com with SMTP id 00721157ae682-2ebfdbe01f6so49335057b3.10 for ; Thu, 14 Apr 2022 11:59:55 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=lBoe2NvTPk+a9psEnpWCjVoVMbSPB5o03aOIxfA/4Zo=; b=8Dxyx62lDsIQjz78zZhBqRXumrMWaX91Q9B2/SGMUYm/PGQRqrCjvtbuWNbhC10pX3 0MLPaHHRWlhYyHIY2mkikr/5b/BnxGnoySVveC3+z9SIorspbS5886Qdfaypt3n8C0WC cbfRbs55ta99Tgemb2hrnIAwgQa2fjymgfVLs/04RO07ykUUEPQTxOYa28/RtFYXhtsN gligINMUPTj+E2BMEuUva9LJRtvC5g9g0xB2bWEH4Ar6hgCkfIXrNlbSElV0R35LZ+bB gmj8EA8+rRnXTqIRqn0d8AMD5s7kOs/u4dHy/uwhGyMJDqM4UVZVmNoGju53Nk3LCszG G+TA== X-Gm-Message-State: AOAM530ttxxrIz/RdeWDJsstEggIQB0EBg8H90jD4trMFibzZdKeKp85 FY4Vj/aZVJBXfJgUmRQDYE5YOMoXSYud9TuCvxEXqCOEybEHB3dy3INeF/iggo98bGdK/BlOESC ub1ygBkPqQB/439840m3JhmPYeZEprPc= X-Received: by 2002:a05:6902:509:b0:641:3b3c:9ca0 with SMTP id x9-20020a056902050900b006413b3c9ca0mr2714279ybs.415.1649962795025; Thu, 14 Apr 2022 11:59:55 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwPJxMYhTI0jFQE1LeVsq5XHCHv/nWCdYQvU6CJ0ZUs3glr4GIppvY6P3CZwNnzBAlkXsvuq64MSY6I3PSsik8= X-Received: by 2002:a05:6902:509:b0:641:3b3c:9ca0 with SMTP id x9-20020a056902050900b006413b3c9ca0mr2714255ybs.415.1649962794749; Thu, 14 Apr 2022 11:59:54 -0700 (PDT) MIME-Version: 1.0 References: <20220414181546.306201-1-ppalka@redhat.com> In-Reply-To: <20220414181546.306201-1-ppalka@redhat.com> From: Jonathan Wakely Date: Thu, 14 Apr 2022 19:59:43 +0100 Message-ID: Subject: Re: [PATCH] libstdc++: Optimize std::has_single_bit To: Patrick Palka Cc: gcc Patches , "libstdc++" X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE, URI_DOTEDU 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:59:59 -0000 On Thu, 14 Apr 2022 at 19:17, Patrick Palka via Libstdc++ wrote: > > This reimplements std::has_single_bit using the well-known bit-twiddilng > trick[1], which is much faster than popcount on x86_64. Is that always true for all microarchitectures? We have https://gcc.gnu.org/PR97759 on this topic, and I think we agreed that the compiler should match the popcount pattern and Do The Right Thing for the target and current -march. If we're confident it's always better, that PR number should go in the changelog. > 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? No. The extensions have the same preconditions as the corresponding standard functions, we just don't check them. The code using them is internal to the library and should only use unsigned types. Users relying on the extensions need to meet those preconditions too. > 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 >