This patch updates algorithms in <numeric> to use std::move based on p0616r0. Moving values instead of copying them creates huge speed improvements (see the paper for details).
Details
Details
- Reviewers
mclow.lists EricWF ldionne - Group Reviewers
Restricted Project - Commits
- rGb2943765e72e: [libc++] Use std::move in numeric algorithms (P0616R0).
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
| include/numeric | ||
|---|---|---|
| 277 ↗ | (On Diff #196789) | Using std::move in places like this, while not specified in the standard (or paper), also improves performance a lot (about 7x in my tests). I think it would be good to try to find other places in numeric/algorithms where values could be moved instead of copied (because there is no downside and a lot of performance gains). |
| include/numeric | ||
|---|---|---|
| 277 ↗ | (On Diff #196789) | I don't think this is correct. |
| 295 ↗ | (On Diff #196789) | Same comment as above. You're relying on the value of a moved-from object. |
| 425 ↗ | (On Diff #196789) | And here. |
| 445 ↗ | (On Diff #196789) | And here. |
| test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp | ||
| 40 ↗ | (On Diff #196789) | I don't see what this code is testing. You set no values in the array; nor do you test the results. |
Comment Actions
Consider the following code:
std::vector<std::string> v = { "abc", "def", "ghi", "jkl", "mno" };
std::vector<std::string> r = { "xxx", "xxx", "xxx", "xxx", "xxx" };
std::partial_sum(v.begin(), v.end(), r.begin());
for (const auto &s: r) std::cout << s << "|";
std::cout << std::endl;With the current implementation of partial_sum, this prints: abc|abcdef|abcdefghi|abcdefghijkl|abcdefghijklmno|
With your changes, it prints: abc|def|ghi|jkl|mno|
| include/numeric | ||
|---|---|---|
| 425 ↗ | (On Diff #196789) |
Maybe I am misunderstanding what the paper is saying. While the above call to std::move is not specified in the paper, I think the one on line 425 is. |
| test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp | ||
| 40 ↗ | (On Diff #196789) | This ensures that the left-hand side of the addition operator is an rvalue. |
Comment Actions
Thanks for the help and example @mclow.lists. That cleared it up a lot, hope this update fixes the issues and provides a test for the example you gave.
| include/numeric | ||
|---|---|---|
| 416 ↗ | (On Diff #196985) | While updating this function, I changed the variable names so it could more easily be read. If you want, I am happy to change them back. |
| 425 ↗ | (On Diff #196985) | I can't find a good way to test that __acc is not read after being moved but before being re-assigned. If you have any ideas, let me know. Otherwise, I think it will be okay as-is. |
Comment Actions
I don't understand P0616 at all.
It's expecting users to provide operator+(T&&, T const&) and operator-(T const&, T&&) that move from the first and second arguments respectively.
Who writes that kind of thing?
But that ship appears to have sailed.
I don't see anything majorly wrong with this (except the paper itself). But I'll leave it up to Marshall to finish this review.
| test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp | ||
|---|---|---|
| 73 ↗ | (On Diff #196985) | The new test requires C++11 but this test file runs in C++03. So you need to wrap the new test in #ifdef TEST_STD_VER >= 11 blocks. |
| 40 ↗ | (On Diff #196789) | A better name would be ensure_move, or rvalue_addable. Also, why is the rvalue const? |
| test/std/numerics/numeric.ops/inner.product/inner_product_comp.pass.cpp | ||
| 35 ↗ | (On Diff #196985) | Again, none of the && parameters should be const. |
Comment Actions
It's expecting users to provide operator+(T&&, T const&) and operator-(T const&, T&&) that move from the first and second arguments respectively.
It's not expecting users to do this, its allowing them to. Rvalue references can turn into lvalue references implicitly but not the other way around. My tests error when an lvalue is passed to an operator expecting an rvalue, but if you tried to use the same method to tests the opposite thing it would not work. In other words, if I used this in my tests, the program would still "work":
force_move operator+(force_move const&, force_move const&)
This paper allows users to have huge speed improvements while not breaking code for most people.
| test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp | ||
|---|---|---|
| 40 ↗ | (On Diff #196789) | I talked with @mclow.lists about this a bit; I am going to re-work these tests to use TrackedValue (or something similar) and add some tests for std::string (because that was one of the paper's main focuses).
Because it's never modified. It would normally be useless because it cannot be moved from, but here it's purpose is only in the argument type, so I think it's okay to copy it. I can change it if you want. |
| include/numeric | ||
|---|---|---|
| 425 ↗ | (On Diff #196985) | You probably don't need a test for that exact bit of behavior. |
| test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp | ||
| 40 ↗ | (On Diff #196789) | If the purpose is the argument type, we want the parameter to match it. Imagine if we wrote a bug where we passed int&& as const int&&. These tests wouldn't catch it. |
| include/numeric | ||
|---|---|---|
| 425 ↗ | (On Diff #196985) | That's what I was thinking, glad you agree. |
| test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp | ||
| 40 ↗ | (On Diff #196789) | So I should make two overloads? I am not really understanding what you are asking. A non-const argument can be passed as a const argument if it is not modified (which it isn't), so I don't think a bug would be created here because of the const-ness. Take this for example: struct pred
{
// operator which takes const parameters
bool operator()(bool const& a, bool const& b) { return a == b; }
};
int main()
{
auto p = pred { };
const bool t = true; // const parameter
bool f = false; // non-const parameter
assert(p(true, true));
assert(p(t, t));
assert(p(f, f)); // both are fine because `f` is implicitly converted to a const type
} |
Comment Actions
- Update tests to make them more readable and visually correct.
- Add tests for` std::string` (a thing the paper focuses on).
I originally wanted to use TrackedValue or another pre-built struct instead of rvalue_addable, but they all required so much modification / overriding that it seemed easier to just create a new one.
| test/std/numerics/numeric.ops/accumulate/accumulate_op.pass.cpp | ||
|---|---|---|
| 52 ↗ | (On Diff #197631) | Let's not require C99 VLAs to run our tests. |
| 60 ↗ | (On Diff #197631) | You can do this test at C++03. |
| test/std/numerics/numeric.ops/adjacent.difference/adjacent_difference_op.pass.cpp | ||
| 75 ↗ | (On Diff #197631) | nit: line break. |
| include/numeric | ||
|---|---|---|
| 166 ↗ | (On Diff #197631) | This move stuff should be enabled for C++20 and later, not for older standards. This is a new feature (a paper), not a bug fix (an issue). So you need to do this: #if _LIBCPP_STD_VER > 17
__init = _VSTD::move(__init) + *__first;
#else
__init = __init + *__first;
#endifand the move-enabled tests should be post-C++17. Note that we never test for an unreleased standard version. We only say "greater than 17", not "20" - because something might happen, and there might not be a C++20. It might slip to 2021, say. |
Comment Actions
- wrap all changes to <numeric> in if after 17
- move string tests outside of version check
Comment Actions
- update the expected error from calling std::abs on unsigned char and short (does anyone know why those types got a specialization here?).
Comment Actions
Can you update the paper status in www/?
LGTM after CI passes and updating the paper status. Also consider the comment about comments on short #endifs, but it's non-blocking.
| include/numeric | ||
|---|---|---|
| 453 ↗ | (On Diff #214706) | These comments on the #endif don't add a lot of value since there's only one line in between. I think it would un-clutter the code a bit to remove them. |