Re: [PATCH] libstdc++: Optimize std::has_single_bit
On Thu, Apr 14, 2022 at 2:59 PM Jonathan Wakely wrote: > > 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. 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 > > 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 > > >
Re: [PATCH] libstdc++: Optimize std::has_single_bit
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 >
[PATCH] libstdc++: Optimize std::has_single_bit
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 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