Why does std::reduce need commutativity?

Question

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

It says that the behavior of an operation is not defined if the operation is not commutative, but why? We just divide the array into blocks and then merge the result. Is it only necessary to have associativity?

Answer 1

std::reduce requires both associativity and commutativity. Associativity is clearly needed for a parallel algorithm, since you want to perform the calculation on separate chunks and then combine them.

As for commutativity: According to a reddit post by MSVC STL developer Billy O'Neal, this is required in order to allow vectorization to SIMD instructions:

Commutativity is also necessary to enable vectorization, since the code you want for reduce to come out as something like:

vecRegister = load_contiguous(first);
while (a vector register sized chunk is left) {
    first += packSize;
    vecRegister = add_packed(load_contiguous(first), vecRegister);
}
// combine vecRegister's packed components

etc., which given ints and SSE registers and a * b * c * d * e * f * g * h gives something like (a * e) * (b * f) * (c * g) * (d * h).

Most other languages aren't doing explicit things to make vectorizing their reduction possible. And nothing says we can't add a noncommutative_reduce or something like that in the future if someone comes up with a compelling use case.