std::move in std::accumulate and other algorithmsSection: 26.10 [numeric.ops] Status: Resolved Submitter: Chris Jefferson Opened: 2011-01-01 Last modified: 2020-09-06
Priority: 3
View all other issues in [numeric.ops].
View all issues with Resolved status.
Discussion:
The C++0x draft says std::accumulate uses: acc = binary_op(acc, *i).
acc = binary_op(std::move(acc), *i) can lead to massive improvements (particularly,
it means accumulating strings is linear rather than quadratic).
Consider the simple case, accumulating a bunch of strings of length 1 (the same argument holds for other length buffers).
For strings s and t, s+t takes time length(s)+length(t), as you have to copy
both s and t into a new buffer.
So in accumulating n strings, step i adds a string of length i-1 to a string of length
1, so takes time i.
Therefore the total time taken is: 1+2+3+...+n = O(n2)
std::move(s)+t, for a "good" implementation, is amortized time length(t), like vector,
just copy t onto the end of the buffer. So the total time taken is:
1+1+1+...+1 (n times) = O(n). This is the same as push_back on a vector.
I'm trying to decide if this implementation might already be allowed. I suspect it might not
be (although I can't imagine any sensible code it would break). There are other algorithms
which could benefit similarly (inner_product, partial_sum and
adjacent_difference are the most obvious).
Is there any general wording for "you can use rvalues of temporaries"?
The reflector discussion starting with message c++std-lib-29763 came to the conclusion
that above example is not covered by the "as-if" rules and that enabling this behaviour
would seem quite useful.
[ 2011 Bloomington ]
Moved to NAD Future. This would be a larger change than we would consider for a simple TC.
[2017-02 in Kona, LEWG responds]
Like the goal.
What is broken by adding std::move() on the non-binary-op version?
A different overload might be selected, and that would be a breakage. Is it breakage that we should care about?
We need to encourage value semantics.
Need a paper. What guidance do we give?
Use std::reduce() (uses generalized sum) instead of accumulate which doesn’t suffer it.
Inner_product and adjacent_difference also. adjacent_difference solves it half-way for “val” object, but misses the opportunity for passing acc as std::move(acc).
[2017-06-02 Issues Telecon]
Ville to encourage Eelis to write a paper on the algorithms in <numeric>, not just for accumulate.
Howard pointed out that this has already been done for the algorithms in <algorithm>
Status to Open; Priority 3
[2017-11-11, Albuquerque]
This was resolved by the adoption of P0616r0.
Proposed resolution: