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

[Jonathan Wakely <jwakely@redhat.com>]

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
>