Use of std::move in std::accumulate

Question

In my Fedora 34 environment (g++), std::accumulate is defined as:

template<typename ITER, typename T>
constexpr inline T accumulate(ITER first, ITER last, T init)
{
  for (; first != last; ++first)
      init = std::move(init) + *first; // why move ?

  return init;
}

If the expression init + *first is already an rvalue, what is the purpose of std::move ?

Fouquet

Answer 1

std::move(init) + *first can sometimes generate more efficient code than init + *first, because it allows init to be overwritten. However, since (as you observed) the result of the + will generally be an rvalue, there is no need to wrap the entire expression in a second std::move.

For example, if you are accumulating std::strings, then std::move(init) + *first might be able to append *first into reserved-but-not-yet-used space in init's buffer instead of having to allocate a new buffer whose length is the sum of the lengths of init and *first.

Orchitis

Interesting though that it's defined using +, instead init += *first;, shouldn't that yield similar performance to the version with move? Is there really a valid case to prefer + and move over += or is it just a design decision? – Eulogistic

@Eulogistic std::accumulate can't use +=, because it can't guarantee that a += b necessarily has the same semantics as a = a + b given that the user can overload these operators however they wish. If you want to write your own version with +=, that is a fine choice but you need to document it. If you're writing a non-generic version that just works with std::string, then you probably won't use + or += at all since there are more efficient approaches to concatenation. – Orchitis

@BrianBi That's a "Doctor, it hurts if I do this" problem. If a user defines operator += to have different semantics from a=a+b they get what they deserve. – Skyler

@Skyler pretend that there's one overload and BinaryOperation is defaulted to std::plus if there were std::plus_assign we might have a different std::accumulate – Compunction

@Compunction That's a much better argument. Perhaps even an answer. – Skyler

It's really the same argument. STL algorithms (and their descendants in the C++ std::lib) are specified in terms of the minimal operations they require, and for this algo the required operations are only + and assignment. Requiring += would be a different set of requirements, so a different algorithm that would not be usable with types that only provide + and not +=. tl;dr the algorithm as specified for decades doesn't even assume that a += b exists for the type. Changing it to use += instead would be a breaking change. – Cormick

Answer 2

The value category of init + *first doesn't matter.

init in init + *first is a lvalue.

So if init + *first calls an operator+ overload taking the parameter by-value, it will cause a copy construction of that parameter

But the value of init is not required anymore after init + *first, so it makes sense to move it into the parameter instead.

Similarly a operator+ overload taking its first argument by rvalue-reference might be used to allow modification of the argument by the operation.

This is what std::move achieves here.

The standard specifies this behavior since C++20.

Coupler

But the operator + undoes any of this effect. It's going to return a pure rvalue which will be copied. – Skyler

@Skyler If operator+ returns by-value, then std::move(init) + *first is a prvalue expression (independently of the std::move) and = will therefore use move assignment if available for the type. In the end, only moves are required, no copies. – Coupler

Answer 3

It's nothing to do with the return value of operator +, but with the arguments to it.

As far as I can tell, a valid implementation of std::accumulate could be

template<typename ITER, typename T, typename OP = plus>
constexpr inline T accumulate(ITER first, ITER last, T init, OP op = {})
{
  for (; first != last; ++first)
      init = op(std::move(init), *first); // move the argument that is being overwritten

  return init;
}

It would be a larger breaking change to specify accumulate in terms of operator +=. For symmetry you'd want to change the BinaryOperation overloads, and that would break all the existing uses, as would any type that defined + but not += .

Compunction

Answer 4

I was just reminded, when I wrote out an example of bignum addition yesterday as a lesson, why this is more efficient.

The binary + operator creates and returns a temporary object. With operands that fit into a machine register, this can be zero-cost (at most spilling what was in the destination register before onto the stack), but sometimes, a large data structure will need to be created. And this seems to be template code that might have to implement that use case.

If the left operand can be clobbered, though, + can be implemented as +=, overwriting the operand and optimizing away the creation of a new copy.

This coding style strikes me as a bit odd—as I mentioned, += has exactly the semantics the programmer seems to want here, so I’m not sure why they don’t use that instead.

Redfin

@YSC I’ve removed the misleading sentence. – Redfin

Since the comments have been cleaned up, the reason for the downvotes is that I originally referred to an expandable template argument as a “macro.” In C++, that term normally only is used for preprocessor macros – Redfin

You're assuming the type even has +=, which is an assumption that this algorithm doesn't make. One of Stepanov's goals for the STL was to define things in terms of the minimal set of operations required. Even if += exists, assuming that a += b has the same semantics as a = a + b would be another additional requirement that the algo would need to document. – Cormick

@JonathanWakely The implementation might check for += with a requires clause or a concept. You’re correct that it might break on a type that overloads operator+= with different semantics. Although I could also think of types for which this version would break, such as a type that can be updated but not assigned to. – Redfin

@JonathanWakely However, you have a good point that the Standard Library defines how this function works, and making assumptions about += (if present) would complicate that in an undesirable way. A modern implementation should really take an arbitrary reduction function, defaulting to std::plus<T>, though. In practice, any well-behaved type will implement operator+(T&&, const T&) to have the same behavior as operator+= if it matters, and then check for self-assignment. Using += would, therefore optimize out the tuntime self-assignment test. – Redfin