[Bug c++/101274] New: std::execution::seq has incorrect behaviour under GCC 11.1.0

[Bug c++/101274] New: std::execution::seq has incorrect behaviour under GCC 11.1.0

[general at yhf8377 dot me]

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

            Bug ID: 101274
           Summary: std::execution::seq has incorrect behaviour under GCC
                    11.1.0
           Product: gcc
           Version: 11.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: general at yhf8377 dot me
  Target Milestone: ---

Created attachment 51091
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51091&action=edit
Minimal code to reproduce the error

We have a unit test that passes when compiled with GCC 10 but fails when
compiled with GCC 11. Further digging shows that calling `std::reduce()` with
execution policy `std::execution::seq` does not execute the provided function
object in sequential order.

Attached is the minimal test case that shows the different behaviour under GCC
10 and GCC 11.

Under GCC 10 (10.3.0) the output is:

plus_squared_ignore_nan: a = nan, b = 336.88
plus_squared_ignore_nan: a = 113488, b = nan
plus_squared_ignore_nan: a = 113488, b = 818.6
plus_squared_ignore_nan: a = 783594, b = nan
plus_squared_ignore_nan: a = 783594, b = 521.16
plus_squared_ignore_nan: a = 1.0552e+06, b = 451.78
plus_squared_ignore_nan: a = 1.25931e+06, b = 601.78
plus_squared_ignore_nan: a = 1.62145e+06, b = 709.2
plus_squared_ignore_nan: a = 2.12441e+06, b = 262.55
plus_squared_ignore_nan: a = 2.19334e+06, b = 659.67
plus_squared_ignore_nan: a = 2.62851e+06, b = 56.6
plus_squared_ignore_nan: a = 2.63171e+06, b = 780.31
plus_squared_ignore_nan: a = 3.2406e+06, b = 398.74

Correct! sum_squared == 3399588.6719

Under GCC 11 (11.1.0) the output is:

plus_squared_ignore_nan: a = 336.88, b = nan
plus_squared_ignore_nan: a = 818.6, b = nan
plus_squared_ignore_nan: a = 336.88, b = 818.6
plus_squared_ignore_nan: a = nan, b = 670443
plus_squared_ignore_nan: a = 521.16, b = 451.78
plus_squared_ignore_nan: a = 601.78, b = 709.2
plus_squared_ignore_nan: a = 204626, b = 503566
plus_squared_ignore_nan: a = 4.49494e+11, b = 2.53579e+11
plus_squared_ignore_nan: a = 262.55, b = 659.67
plus_squared_ignore_nan: a = 56.6, b = 780.31
plus_squared_ignore_nan: a = 435427, b = 608940
plus_squared_ignore_nan: a = 6.43025e+22, b = 3.70809e+11
plus_squared_ignore_nan: a = 2.01802e+23, b = 398.74
gcc_test: src/main.cpp:24: int main(int, char**): Assertion `sum_squared ==
3399588.6719' failed.
Aborted

[Bug c++/101274] std::execution::seq has incorrect behaviour under GCC 11.1.0

[general at yhf8377 dot me]

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

--- Comment #1 from yhf8377 <general at yhf8377 dot me> ---
Sorry, forgot to list the compiler options we used.

g++ -std=c++17 -g -m64 -O0 -Wall -fmessage-length=0 -pthread -o gcc_test
src/main.cpp

[Bug libstdc++/101274] [11/12 Regression] std::execution::seq has incorrect behaviour under GCC 11.1.0

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
            Summary|std::execution::seq has     |[11/12 Regression]
                   |incorrect behaviour under   |std::execution::seq has
                   |GCC 11.1.0                  |incorrect behaviour under
                   |                            |GCC 11.1.0
   Target Milestone|---                         |11.2

[Bug libstdc++/101274] [11/12 Regression] std::execution::seq has incorrect behaviour under GCC 11.1.0

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-07-01

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Confirmed.

[Bug libstdc++/101274] [11/12 Regression] std::execution::seq has incorrect behaviour under GCC 11.1.0

[rodgertq at gcc dot gnu.org]

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

Thomas Rodgers <rodgertq at gcc dot gnu.org> changed:

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

--- Comment #3 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
The standard only requires that the the parallel algorithm's execution, when
invoked with std::sequenced_policy, be invoked on the calling thread, and (as
with the other execution policies) allows for the invocations of element access
functions to be indeterminately sequenced on the execution agent.

This is also spelled at -

https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

"1) The execution policy type used as a unique type to disambiguate parallel
algorithm overloading and require that a parallel algorithm's execution may not
be parallelized. The invocations of element access functions in parallel
algorithms invoked with this policy (usually specified as std::execution::seq)
are indeterminately sequenced in the calling thread."

[Bug libstdc++/101274] [11/12 Regression] std::execution::seq has incorrect behaviour under GCC 11.1.0

[rodgertq at gcc dot gnu.org]

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

--- Comment #4 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
I did some more reading of
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4878.pdf and it would
seem that you are not even guaranteed a deterministic ordering of the
application of binary_op on the non-execution policy accepting overloads of
std::reduce().

See [reduce] the note at bullet 9 -

"[Note 1 : The difference between reduce and accumulate is that reduce applies
binary_op in an unspecified order, which yields a nondeterministic result for
non-associative or non-commutative binary_op such as floating-point addition. —
end note]"

[Bug libstdc++/101274] [11/12 Regression] std::execution::seq has incorrect behaviour under GCC 11.1.0

[general at yhf8377 dot me]

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

--- Comment #5 from yhf8377 <general at yhf8377 dot me> ---
Thank you Thomas for the detailed information and links to the references.

I guess I will need to move this bug report into our own bug tracker. :-) This
is indeed a bug in our code as we had incorrect assumptions on how
`std::reduce()` and `std::execution::seq` work.

Thanks again!

[Bug libstdc++/101274] [11/12 Regression] std::execution::seq has incorrect behaviour under GCC 11.1.0

[rodgertq at gcc dot gnu.org]

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

--- Comment #6 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
It does raise an issue which I'm going to follow up on separately on the SG1
(concurrency and parallelism study group) mailing list.

While it is indeed the case that standard says you can't count on deterministic
sequencing for std::reduce(), I can't find any wording that directly supports
the wording on cppreference.com std::execution::sequenced_policy, though that
wording is consistent with my recollection of SG1's discussions regarding
execution policies.

There is wording that says 'Unless otherwise specified, the semantics of
ExecutionPolicy algorithm overloads are identical to their overloads without."

The wording for std::for_each() for the non-execution policy overload the
standard says -

Effects: Applies f to the result of dereferencing every iterator in the range
[first, last), starting from first and proceeding to last - 1.

And for one that takes an execution policy -

Effects: Applies f to the result of dereferencing every iterator in the range
[first, last).

So it omits the ordering constraint, which makes sense, but I wonder if we
shouldn't be more explicit in the documentation of the policies themselves.