Re: [PATCH] libstdc++: Optimize std::has_single_bit

[Patrick Palka <ppalka@redhat.com>]

On Thu, Apr 14, 2022 at 2:59 PM Jonathan Wakely <jwakely@redhat.com> wrote:
>
> On Thu, 14 Apr 2022 at 19:17, Patrick Palka via Libstdc++
> <libstdc++@gcc.gnu.org> 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.

Whoops, I completely forgot that we had a PR about this!  Makes sense
to fix this on the compiler side instead.

>
> 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.

Understood, thanks!

>
> > 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<typename _Tp>
> >      constexpr bool
> >      __has_single_bit(_Tp __x) noexcept
> > -    { return std::__popcount(__x) == 1; }
> > +    { return __x != 0 && (__x & (__x - 1)) == 0; }
> >
> >    template<typename _Tp>
> >      constexpr _Tp
> > --
> > 2.36.0.rc2.10.g1ac7422e39
> >
>