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.133.124]) by sourceware.org (Postfix) with ESMTPS id C7F3F3858C2C for ; Thu, 14 Apr 2022 18:59:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C7F3F3858C2C Received: from mail-yw1-f199.google.com (mail-yw1-f199.google.com [209.85.128.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-336-mZ8JePoGN7-d9M-agfTW1Q-1; Thu, 14 Apr 2022 14:59:55 -0400 X-MC-Unique: mZ8JePoGN7-d9M-agfTW1Q-1 Received: by mail-yw1-f199.google.com with SMTP id 00721157ae682-2eb2bc9018aso49650757b3.18 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=7fvAYk+q6SfBSt8iIwTAPknlQqQRh5PjygtyvSPhU1VPpcAaj/M2ZFFH3UJfabiub6 uKWLim4EgUP9BUbqpmfoBLpQttS/59qpever0xIFWEVjZrtJtjnGL8vg+bckcUCPGSVQ sZvcYaeAG0KPtLe29UPtYMdgTs3Qdb9JaQ8bF+3eq3HVmf/+0QLJf0xUSvAfc1ykZY2I 3fm+HFBz3HhuxKn8BoBIuKzWEgQ2X+40KpAn1n6D2BNg1jR6ys2iILlHdD3MTQsVFnmf /B3WHr3TEBrUVNrguSNjqvReLU/iZRsGcdP7n5UreBIlQZKZmf50cs9aDB0VlfoPQucm EDGg== X-Gm-Message-State: AOAM531V3WjtRYmVF4ok+yycmmzjUS0xsP3+vtfRZiGVOh43Lf+u1Vn1 5tO0qkxZ2mTwnQEmuNVExNBkl9dAykpODh+NzgForsClTsNOPlUxsQdR/lbBukdyL2VYPvSgCPx 3vqWYlUmaF1+pFKXVZqJAyEvp6/iZw1NPwA== X-Received: by 2002:a05:6902:509:b0:641:3b3c:9ca0 with SMTP id x9-20020a056902050900b006413b3c9ca0mr2714270ybs.415.1649962794954; Thu, 14 Apr 2022 11:59:54 -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=-13.3 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_H5, 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: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches 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 >