[Bug libstdc++/98226] New: Slow std::countr_one

[Bug libstdc++/98226] New: Slow std::countr_one

[zaikin.icc at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

            Bug ID: 98226
           Summary: Slow std::countr_one
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zaikin.icc at gmail dot com
  Target Milestone: ---

The function std::countr_one() from C++20 is slow. For a given x (say, unsigned
int) it in fact  calls std::countr_zero(~x) which in turn calls
__builtin_ctz(~x). Calling __builtin_ctz(~x) directly from std::countr_one()
would increase the performance. The test case contains three sources, each of
which finally does the same but with different performance.

Test case:
---
test1.cpp:
#include <bit>

int main()
{
  unsigned j;
  for (unsigned i=0; i<(1 << 30); i++) {
    j = std::countr_one(i);
  }
}
---
g++ -std=c++20 ./test1.cpp -o test1


test2.cpp:
#include <bit>

int main()
{
  unsigned j;
  for (unsigned i=0; i<(1 << 30); i++) {
    j = std::countr_zero(~i);
  }
}
---
g++ -std=c++20 ./test2.cpp -o test2


test3.cpp:
#include <bit>

int main()
{
  unsigned j;
  for (unsigned i=0; i<(1 << 30); i++) {
    j = __builtin_ctz(~i);
  }
}
---
g++ -std=c++20 ./test3.cpp -o test3

The user time is reported below:
time ./test1
5.266s
time ./test2
3.028s
time ./test3
0.741s

$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/10/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa:hsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu
10.2.0-5ubuntu1~20.04' --with-bugurl=file:///usr/share/doc/gcc-10/README.Bugs
--enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 --prefix=/usr
--with-gcc-major-version-only --program-suffix=-10
--program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id
--libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
--libdir=/usr/lib --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug
--enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new
--enable-gnu-unique-object --disable-vtable-verify --enable-plugin
--enable-default-pie --with-system-zlib --enable-libphobos-checking=release
--with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch
--disable-werror --with-arch-32=i686 --with-abi=m64
--with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic
--enable-offload-targets=nvptx-none=/build/gcc-10-WJNXnb/gcc-10-10.2.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-10-WJNXnb/gcc-10-10.2.0/debian/tmp-gcn/usr,hsa
--without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 10.2.0 (Ubuntu 10.2.0-5ubuntu1~20.04)

[Bug libstdc++/98226] Slow std::countr_one

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This seems like an optimizer bug. There is no way I'm going to repeat the
entire body of countr_zero in countr_one.

[Bug libstdc++/98226] Slow std::countr_one

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oh, but you didn't enable any optimization at all, so who cares about the
performance?

[Bug libstdc++/98226] Slow std::countr_one

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #2)
> Oh, but you didn't enable any optimization at all, so who cares about the
> performance?

I was thinking the same.

[Bug libstdc++/98226] Slow std::countr_one

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #4 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:2ea62857a3fbdf091ba38cbb62e98dc76b198e2e

commit r11-5922-g2ea62857a3fbdf091ba38cbb62e98dc76b198e2e
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Dec 10 21:57:42 2020 +0000

    libstdc++: Remove redundant branches in countl_one and countr_one [PR
98226]

    There's no need to explicitly check for the maximum value, because the
    function we call handles it correctly anyway.

    libstdc++-v3/ChangeLog:

            PR libstdc++/98226
            * include/std/bit (__countl_one, __countr_one): Remove redundant
            branches.

[Bug libstdc++/98226] Slow std::countr_one

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I've removed some redundant code from them, but not changed the indirection
that this PR complains about. I don't plan to change that.

[Bug libstdc++/98226] Slow std::countr_one

[zaikin.icc at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #6 from Oleg Zaikin <zaikin.icc at gmail dot com> ---
(In reply to Jonathan Wakely from comment #2)
> Oh, but you didn't enable any optimization at all, so who cares about the
> performance?

Let me give the whole picture. The issue is very close to that from
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97759 where a C-style
implementation was replaced by C++20 std::has_single_bit. We have a complex
project that of course is compiled with all proper optimization flags. There we
have a function firstzero(unsigned x) that returns 2^i, with i the position of
the first 0 of x, and 0 iff there is no 0. Its implementation is:
  unsigned firstzero(const unsigned x) noexcept {
#if __cplusplus > 201703L
    return x == unsigned(-1) ? 0 : unsigned(1) << std::countr_one(x);
#else
    const unsigned y = x+1; return (y ^ x) & y;
#endif
  }
When we switched from C++17-based g++ to C++20-based g++, the performance of
the whole program decreased by about 7 %. It turned out that the main reason is
the firstzero function.

[Bug libstdc++/98226] Slow std::countr_one

[zaikin.icc at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #7 from Oleg Zaikin <zaikin.icc at gmail dot com> ---
(In reply to Jonathan Wakely from comment #5)
> I've removed some redundant code from them, but not changed the indirection
> that this PR complains about. I don't plan to change that.

Thank you! I've got your point regarding the indirection.

[Bug libstdc++/98226] Slow std::countr_one

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Oleg Zaikin from comment #6)
> When we switched from C++17-based g++ to C++20-based g++, the performance of
> the whole program decreased by about 7 %. It turned out that the main reason
> is the firstzero function.

But if I create a microbenchmark for this function and replace countr_one(x) by
__builtin_ctz(~x) I don't see any improvement. The problem is not that
countr_one(x) calls countr_zero(~x). The problem is that the two versions of
firstzero are completely different.

If the (y ^ x) & y version is more efficient, just use that.

In other words, this is not a problem with countr_one, it's that you chose to
use countr_one here.

For example, using google benchmark:

#include <benchmark/benchmark.h>
#include <bit>
#include <vector>
#include <iostream>
#include <stdlib.h>

unsigned total = 0;

unsigned firstzero(const unsigned x) noexcept {
  const unsigned y = x+1;
  return (y ^ x) & y;
}

unsigned firstzero_cxx20(const unsigned x) noexcept {
  return x == unsigned(-1) ? 0 : unsigned(1) << std::countr_one(x);
}

unsigned firstzero_ctz(const unsigned x) noexcept {
  return x == unsigned(-1) ? 0 : unsigned(1) << __builtin_ctz(~x);
}

static void BM_orig(benchmark::State& state) {
  srand(0);
  std::vector<unsigned> v(1000000);
  for (auto& u : v)
    u = rand();
  for (auto _ : state)
  {
    total = 0;
    for (auto& u : v)
      total += firstzero(u);
  }
}

static void BM_cxx20(benchmark::State& state) {
  unsigned total;
  srand(0);
  std::vector<unsigned> v(1000000);
  for (auto& u : v)
    u = rand();
  for (auto _ : state)
  {
    total = 0;
    for (auto& u : v)
      total += firstzero_cxx20(u);
  }
  if (total != ::total) // check for correct result
    throw 1;
}

static void BM_ctz(benchmark::State& state) {
  unsigned total;
  srand(0);
  std::vector<unsigned> v(1000000);
  for (auto& u : v)
    u = rand();
  for (auto _ : state)
  {
    total = 0;
    for (auto& u : v)
      total += firstzero_ctz(u);
  }
  if (total != ::total) // check for correct result
    throw 1;
}


BENCHMARK(BM_orig);
BENCHMARK(BM_cxx20);
BENCHMARK(BM_ctz);
BENCHMARK_MAIN();


With GCC 10 I get:

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
BM_orig        179283 ns       178739 ns         4388
BM_cxx20       888982 ns       886885 ns          770
BM_ctz         883696 ns       881765 ns          783

I think you've just chosen a bad algorithm.

However, I do see a regression using GCC 11:

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
BM_orig        174122 ns       172492 ns         4466
BM_cxx20      1104081 ns      1097202 ns          608
BM_ctz        1119849 ns      1112550 ns          634

That needs to be investigated, but it's a problem with the compiler. It has
nothing to do with countr_one being implemented using countr_zero (as shown by
the same problem being present when calling __builtin_ctz directly).

[Bug libstdc++/98226] Slow std::countr_one

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The generated code hasn't changed between gcc-10 and gcc-11 though, so the
difference must be in the code used to run the benchmarks, not the code under
test.
See https://godbolt.org/z/bWeMen

[Bug libstdc++/98226] Slow std::countr_one

[amonakov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

Alexander Monakov <amonakov at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amonakov at gcc dot gnu.org

--- Comment #10 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
(In reply to Oleg Zaikin from comment #6)
> There
> we have a function firstzero(unsigned x) that returns 2^i, with i the
> position of the first 0 of x, and 0 iff there is no 0. Its implementation is:
>   unsigned firstzero(const unsigned x) noexcept {
> #if __cplusplus > 201703L
>     return x == unsigned(-1) ? 0 : unsigned(1) << std::countr_one(x);
> #else
>     const unsigned y = x+1; return (y ^ x) & y;
> #endif
>   }

But why you are trying to use a more complex branchy expression in C++17 mode
when you already have a more efficient expression as a "fallback"?

Note that a cheaper way is available:

    return (x+1) & ~x;

(though gcc can optimize '(y ^ x) & y' you have to the same machine code)

[Bug libstdc++/98226] Slow std::countr_one

[zaikin.icc at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #11 from Oleg Zaikin <zaikin.icc at gmail dot com> ---
(In reply to Jonathan Wakely from comment #8)
> That needs to be investigated, but it's a problem with the compiler. It has
> nothing to do with countr_one being implemented using countr_zero (as shown
> by the same problem being present when calling __builtin_ctz directly).

Thank you for the detailed clarification!

[Bug libstdc++/98226] Slow std::countr_one

[zaikin.icc at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #12 from Oleg Zaikin <zaikin.icc at gmail dot com> ---
(In reply to Alexander Monakov from comment #10)
> But why you are trying to use a more complex branchy expression in C++17
> mode when you already have a more efficient expression as a "fallback"?
> 
> Note that a cheaper way is available:
> 
>     return (x+1) & ~x;
> 
> (though gcc can optimize '(y ^ x) & y' you have to the same machine code)

Thank you! We will try it.

[Bug libstdc++/98226] Slow std::countr_one

[zaikin.icc at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

Oleg Zaikin <zaikin.icc at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #13 from Oleg Zaikin <zaikin.icc at gmail dot com> ---
countr_one() should be used where it suits better.

[Bug libstdc++/98226] Slow std::countr_one

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98226

--- Comment #14 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-10 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:d7216ea6c0cd6c4fef06e9501bd630c3161b14fd

commit r10-9576-gd7216ea6c0cd6c4fef06e9501bd630c3161b14fd
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Dec 10 21:57:42 2020 +0000

    libstdc++: Remove redundant branches in countl_one and countr_one [PR
98226]

    There's no need to explicitly check for the maximum value, because the
    function we call handles it correctly anyway.

    libstdc++-v3/ChangeLog:

            PR libstdc++/98226
            * include/std/bit (__countl_one, __countr_one): Remove redundant
            branches.

    (cherry picked from commit 2ea62857a3fbdf091ba38cbb62e98dc76b198e2e)