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

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

[Patrick Palka]

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

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

[Jonathan Wakely]

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.

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

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

[Patrick Palka]

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