From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id D04D93871F9F; Wed, 14 Dec 2022 16:58:58 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org D04D93871F9F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1671037138; bh=+KcDSGFiKl8LvzQ83stkSulESbJqnT7PYn49QzAIXrE=; h=From:To:Subject:Date:From; b=OF959XlKPV9UpCE9BlcJkrbrWqhuR/SR/mj1j0LTZo7PHb7Qx6etayBz7ubc6NWlt zMo1UzVkw+d7ZESezr5VObdinXjhzSxNVe5JLDeYAECFHZkAR9YSmxNAKG/3oN5uTk JoYLyKdHPbbQuG4V3mM4axy899jwLgiWsmdxmw2s= From: "thomas.jollans at dentsplysirona dot com" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/108105] New: std::is_sorted(std::execution::par, ...) giving incorrect result Date: Wed, 14 Dec 2022 16:58:58 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Version: 12.2.0 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: thomas.jollans at dentsplysirona dot com X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter target_milestone Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 List-Id: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D108105 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 wh= en 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 #include #include int constexpr REPEAT =3D 100000; int main() { std::vector nums =3D { 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 =3D 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 << " tim= es \"sorted\" out of " << REPEAT << '\n'; int sorted_par_count =3D 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 =3D=3D 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-d= ev Output of gcc -v: root@02a06f558cd5:~# g++ -v -save-temps -std=3Dc++20 -ois_sorted_test is_sorted_test.cpp -ltbb Using built-in specs. COLLECT_GCC=3Dg++ COLLECT_LTO_WRAPPER=3D/usr/lib/gcc/x86_64-linux-gnu/12/lto-wrapper OFFLOAD_TARGET_NAMES=3Dnvptx-none:amdgcn-amdhsa OFFLOAD_TARGET_DEFAULT=3D1 Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion=3D'Ubuntu 12.2.0-3ub= untu1' --with-bugurl=3Dfile:///usr/share/doc/gcc-12/README.Bugs --enable-languages=3Dc,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=3D/usr --with-gcc-major-version-only --program-suffix=3D-12 --program-prefix=3Dx86_64-linux-gnu- --enable-shared --enable-linker-build-= id --libexecdir=3D/usr/lib --without-included-gettext --enable-threads=3Dposix --libdir=3D/usr/lib --enable-nls --enable-clocale=3Dgnu --enable-libstdcxx-= debug --enable-libstdcxx-time=3Dyes --with-default-libstdcxx-abi=3Dnew --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=3Drelea= se --with-target-system-zlib=3Dauto --enable-objc-gc=3Dauto --enable-multiarch --disable-werror --enable-cet --with-arch-32=3Di686 --with-abi=3Dm64 --with-multilib-list=3Dm32,m64,mx32 --enable-multilib --with-tune=3Dgeneric --enable-offload-targets=3Dnvptx-none=3D/build/gcc-12-U8K4Qv/gcc-12-12.2.0/= debian/tmp-nvptx/usr,amdgcn-amdhsa=3D/build/gcc-12-U8K4Qv/gcc-12-12.2.0/deb= ian/tmp-gcn/usr --enable-offload-defaulted --without-cuda-driver --enable-checking=3Drelease --build=3Dx86_64-linux-gnu --host=3Dx86_64-linux-gnu --target=3Dx86_64-linu= x-gnu Thread model: posix Supported LTO compression algorithms: zlib zstd gcc version 12.2.0 (Ubuntu 12.2.0-3ubuntu1) COLLECT_GCC_OPTIONS=3D'-v' '-save-temps' '-std=3Dc++20' '-o' 'is_sorted_tes= t' '-shared-libgcc' '-mtune=3Dgeneric' '-march=3Dx86-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=3Dgeneric -march= =3Dx86-64 -std=3Dc++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-fi= xed" 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=3D'-v' '-save-temps' '-std=3Dc++20' '-o' 'is_sorted_tes= t' '-shared-libgcc' '-mtune=3Dgeneric' '-march=3Dx86-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=3Dgeneric -march=3Dx86-64 -std=3Dc++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=3D100 --param ggc-min-heapsize=3D131= 072 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=3D100 --param ggc-min-heapsize=3D131= 072 Compiler executable checksum: 0d4a81275e4da7c024affb8f28a87ddd COLLECT_GCC_OPTIONS=3D'-v' '-save-temps' '-std=3Dc++20' '-o' 'is_sorted_tes= t' '-shared-libgcc' '-mtune=3Dgeneric' '-march=3Dx86-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 Binuti= ls for Ubuntu) 2.39 COMPILER_PATH=3D/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=3D/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/:/us= r/lib/../lib/:/usr/lib/gcc/x86_64-linux-gnu/12/../../../:/lib/:/usr/lib/ COLLECT_GCC_OPTIONS=3D'-v' '-save-temps' '-std=3Dc++20' '-o' 'is_sorted_tes= t' '-shared-libgcc' '-mtune=3Dgeneric' '-march=3Dx86-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=3D/usr/lib/gcc/x86_64-linux-gnu/12/lto-wrapper -plugin-opt=3D-fresolution=3Dis_sorted_test.res -plugin-opt=3D-pass-through= =3D-lgcc_s -plugin-opt=3D-pass-through=3D-lgcc -plugin-opt=3D-pass-through=3D-lc -plugin-opt=3D-pass-through=3D-lgcc_s -plugin-opt=3D-pass-through=3D-lgcc -= -build-id --eh-frame-hdr -m elf_x86_64 --hash-style=3Dgnu --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-gn= u/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=3D'-v' '-save-temps' '-std=3Dc++20' '-o' 'is_sorted_tes= t' '-shared-libgcc' '-mtune=3Dgeneric' '-march=3Dx86-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=