[Bug libstdc++/108105] New: std::is_sorted(std::execution::par, ...) giving incorrect result

["thomas.jollans at dentsplysirona dot com" <gcc-bugzilla@gcc.gnu.org>]

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

            Bug ID: 108105
           Summary: std::is_sorted(std::execution::par, ...) giving
                    incorrect result
           Product: gcc
           Version: 12.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: thomas.jollans at dentsplysirona dot com
  Target Milestone: ---

For the sequence
    {
        1, 23, 33, 48, 49, 65, 89, 0, 1, 2, 10, 11, 12, 12, 13, 14, 22, 23, 24,
        32, 33, 34, 22, 23, 24, 32, 33, 34, 42, 43, 44, 37, 38, 39, 47, 48, 49,
        57, 58, 59, 38, 39, 40, 48, 49, 50, 58, 59, 60, 54, 55, 56, 64, 65, 66,
        74, 75, 76, 78, 79, 80, 88, 89
    }

(which, as you can see, is not sorted), is_sorted sometimes reports true when
called with the parallel execution policy. Without an execution policy,
is_sorted works as expected, and returns false.

(The sequence was not created to have any special properties, but comes a
real-world case)

Minimal test case:

// BEGIN TEST CODE

#include <algorithm>
#include <execution>
#include <iostream>

int constexpr REPEAT = 100000;

int main()
{
    std::vector nums = {
        1, 23, 33, 48, 49, 65, 89, 0, 1, 2, 10, 11, 12, 12, 13, 14, 22, 23, 24,
        32, 33, 34, 22, 23, 24, 32, 33, 34, 42, 43, 44, 37, 38, 39, 47, 48, 49,
        57, 58, 59, 38, 39, 40, 48, 49, 50, 58, 59, 60, 54, 55, 56, 64, 65, 66,
        74, 75, 76, 78, 79, 80, 88, 89
    };

    int sorted_seq_count = 0;
    for (int i{}; i < REPEAT; ++i) {
        if (std::is_sorted(begin(nums), end(nums))) ++sorted_seq_count;
    }
    std::cout << "Sequential std::is_sorted: " << sorted_seq_count << " times
\"sorted\" out of " << REPEAT << '\n';

    int sorted_par_count = 0;
    for (int i{}; i < REPEAT; ++i) {
        if (std::is_sorted(std::execution::par, begin(nums), end(nums)))
++sorted_par_count;
    }
    std::cout << "Parallel std::is_sorted: " << sorted_par_count << " times
\"sorted\" out of " << REPEAT << '\n';

    return sorted_par_count == sorted_seq_count ? 0 : 1;
}

// END TEST CODE

This produces output similar to the following on x86_64 Linux (via
WSL2/Windows):

Sequential std::is_sorted: 0 times "sorted" out of 100000
Parallel std::is_sorted: 71233 times "sorted" out of 100000

I've observed this problem both
 * on GCC 11.3.0 running on (and provided by) Ubuntu 22.04 LTS
 * on GCC 12.2.0 running on (and provided by) Ubuntu 22.10 running in Docker
for reproducibility

   docker run --rm -i --tty ubuntu:22.10
   ( in container ) # apt update && apt upgrade && apt install g++ libtbb-dev

Output of gcc -v:

root@02a06f558cd5:~# g++ -v -save-temps -std=c++20 -ois_sorted_test
is_sorted_test.cpp -ltbb
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/12/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 12.2.0-3ubuntu1'
--with-bugurl=file:///usr/share/doc/gcc-12/README.Bugs
--enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr
--with-gcc-major-version-only --program-suffix=-12
--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 --enable-cet --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-12-U8K4Qv/gcc-12-12.2.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-12-U8K4Qv/gcc-12-12.2.0/debian/tmp-gcn/usr
--enable-offload-defaulted --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 12.2.0 (Ubuntu 12.2.0-3ubuntu1)
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-std=c++20' '-o' 'is_sorted_test'
'-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/12/cc1plus -E -quiet -v -imultiarch
x86_64-linux-gnu -D_GNU_SOURCE is_sorted_test.cpp -mtune=generic -march=x86-64
-std=c++20 -fpch-preprocess -fasynchronous-unwind-tables
-fstack-protector-strong -Wformat -Wformat-security -fstack-clash-protection
-fcf-protection -o is_sorted_test.ii
ignoring duplicate directory "/usr/include/x86_64-linux-gnu/c++/12"
ignoring nonexistent directory "/usr/local/include/x86_64-linux-gnu"
ignoring nonexistent directory "/usr/lib/gcc/x86_64-linux-gnu/12/include-fixed"
ignoring nonexistent directory
"/usr/lib/gcc/x86_64-linux-gnu/12/../../../../x86_64-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
 /usr/include/c++/12
 /usr/include/x86_64-linux-gnu/c++/12
 /usr/include/c++/12/backward
 /usr/lib/gcc/x86_64-linux-gnu/12/include
 /usr/local/include
 /usr/include/x86_64-linux-gnu
 /usr/include
End of search list.
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-std=c++20' '-o' 'is_sorted_test'
'-shared-libgcc' '-mtune=generic' '-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/12/cc1plus -fpreprocessed is_sorted_test.ii
-quiet -dumpbase is_sorted_test.cpp -dumpbase-ext .cpp -mtune=generic
-march=x86-64 -std=c++20 -version -fasynchronous-unwind-tables
-fstack-protector-strong -Wformat -Wformat-security -fstack-clash-protection
-fcf-protection -o is_sorted_test.s
GNU C++20 (Ubuntu 12.2.0-3ubuntu1) version 12.2.0 (x86_64-linux-gnu)
        compiled by GNU C version 12.2.0, GMP version 6.2.1, MPFR version
4.1.0, MPC version 1.2.1, isl version isl-0.25-GMP

GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
GNU C++20 (Ubuntu 12.2.0-3ubuntu1) version 12.2.0 (x86_64-linux-gnu)
        compiled by GNU C version 12.2.0, GMP version 6.2.1, MPFR version
4.1.0, MPC version 1.2.1, isl version isl-0.25-GMP

GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: 0d4a81275e4da7c024affb8f28a87ddd
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-std=c++20' '-o' 'is_sorted_test'
'-shared-libgcc' '-mtune=generic' '-march=x86-64'
 as -v --64 -o is_sorted_test.o is_sorted_test.s
GNU assembler version 2.39 (x86_64-linux-gnu) using BFD version (GNU Binutils
for Ubuntu) 2.39
COMPILER_PATH=/usr/lib/gcc/x86_64-linux-gnu/12/:/usr/lib/gcc/x86_64-linux-gnu/12/:/usr/lib/gcc/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/12/:/usr/lib/gcc/x86_64-linux-gnu/
LIBRARY_PATH=/usr/lib/gcc/x86_64-linux-gnu/12/:/usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/12/../../../../lib/:/lib/x86_64-linux-gnu/:/lib/../lib/:/usr/lib/x86_64-linux-gnu/:/usr/lib/../lib/:/usr/lib/gcc/x86_64-linux-gnu/12/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-std=c++20' '-o' 'is_sorted_test'
'-shared-libgcc' '-mtune=generic' '-march=x86-64' '-dumpdir' 'is_sorted_test.'
 /usr/lib/gcc/x86_64-linux-gnu/12/collect2 -plugin
/usr/lib/gcc/x86_64-linux-gnu/12/liblto_plugin.so
-plugin-opt=/usr/lib/gcc/x86_64-linux-gnu/12/lto-wrapper
-plugin-opt=-fresolution=is_sorted_test.res -plugin-opt=-pass-through=-lgcc_s
-plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lc
-plugin-opt=-pass-through=-lgcc_s -plugin-opt=-pass-through=-lgcc --build-id
--eh-frame-hdr -m elf_x86_64 --hash-style=gnu --as-needed -dynamic-linker
/lib64/ld-linux-x86-64.so.2 -pie -z now -z relro -o is_sorted_test
/usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu/Scrt1.o
/usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu/crti.o
/usr/lib/gcc/x86_64-linux-gnu/12/crtbeginS.o -L/usr/lib/gcc/x86_64-linux-gnu/12
-L/usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu
-L/usr/lib/gcc/x86_64-linux-gnu/12/../../../../lib -L/lib/x86_64-linux-gnu
-L/lib/../lib -L/usr/lib/x86_64-linux-gnu -L/usr/lib/../lib
-L/usr/lib/gcc/x86_64-linux-gnu/12/../../.. is_sorted_test.o -ltbb -lstdc++ -lm
-lgcc_s -lgcc -lc -lgcc_s -lgcc /usr/lib/gcc/x86_64-linux-gnu/12/crtendS.o
/usr/lib/gcc/x86_64-linux-gnu/12/../../../x86_64-linux-gnu/crtn.o
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-std=c++20' '-o' 'is_sorted_test'
'-shared-libgcc' '-mtune=generic' '-march=x86-64' '-dumpdir' 'is_sorted_test.'

Output of the program:

root@02a06f558cd5:~# ./is_sorted_test
Sequential std::is_sorted: 0 times "sorted" out of 100000
Parallel std::is_sorted: 71233 times "sorted" out of 100000

This is all running on a 12-core Intel(R) Xeon(R) W-2133 CPU @ 3.60GHz