Page MenuHomePhabricator

Use std::move in numeric algorithms
ClosedPublic

Authored by zoecarver on Apr 25 2019, 8:22 PM.

Details

Summary

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).

Diff Detail

Event Timeline

zoecarver created this revision.Apr 25 2019, 8:22 PM
zoecarver marked an inline comment as done.Apr 25 2019, 8:27 PM
zoecarver added inline comments.
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).

mclow.lists requested changes to this revision.Apr 26 2019, 5:44 AM
mclow.lists added inline comments.
include/numeric
277 ↗(On Diff #196789)

I don't think this is correct.
On line #273, you move from __t, but then on line #276, you use the value of __t.

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.

This revision now requires changes to proceed.Apr 26 2019, 5:44 AM

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|

zoecarver marked 2 inline comments as done.Apr 26 2019, 12:06 PM
zoecarver added inline comments.
include/numeric
425 ↗(On Diff #196789)

For every iterator i in [first + 1, last) in order, creates an object val whose type is InputIterator’s value type, initializes it with *i, computes val - std::move(acc) or binary_op(val, std::move(acc)), assigns the result to *(result + (i - first)), and move assigns from val to acc.

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.

zoecarver marked 3 inline comments as done.Apr 26 2019, 10:11 PM
zoecarver added inline comments.
include/numeric
277 ↗(On Diff #196789)

Yes, you're completely right. I will update this and the other instances of this issue below.

295 ↗(On Diff #196789)

On the other two lines (292 and 296) not 295, right?

425 ↗(On Diff #196789)

This function might need some re-working to adhere to the standard.

  • update based on reviews
  • expand tests
zoecarver marked 3 inline comments as done.Apr 27 2019, 12:55 PM

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.

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.

zoecarver marked an inline comment as done.EditedApr 28 2019, 9:14 AM

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).

Also, why is the rvalue const?

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.

EricWF added inline comments.Apr 28 2019, 11:10 AM
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.

zoecarver marked 2 inline comments as done.Apr 28 2019, 11:23 AM
zoecarver added inline comments.
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
}
zoecarver updated this revision to Diff 197631.May 1 2019, 1:56 PM
  • 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.

mclow.lists added inline comments.May 1 2019, 5:35 PM
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.
Also, this test doesn't require C++11

mclow.lists added inline comments.May 1 2019, 5:49 PM
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;
#endif

and 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.

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?

I refer you to http://eel.is/c++draft/string.op.plus

zoecarver updated this revision to Diff 197692.May 1 2019, 7:03 PM
  • wrap all changes to <numeric> in if after 17
  • move string tests outside of version check
zoecarver updated this revision to Diff 203471.Jun 6 2019, 6:09 PM
  • general fixes
  • update test versions
  • update c++03 issue
zoecarver updated this revision to Diff 214701.Aug 12 2019, 2:05 PM
  • update the expected error from calling std::abs on unsigned char and short (does anyone know why those types got a specialization here?).
zoecarver updated this revision to Diff 214706.Aug 12 2019, 2:25 PM

Revert the last diff. Wrong revision.

ldionne added a reviewer: Restricted Project.Nov 2 2020, 2:27 PM
ldionne accepted this revision.Nov 23 2020, 1:50 PM

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.

zoecarver updated this revision to Diff 307197.Nov 23 2020, 2:19 PM
  • Rebase off master
  • Remove comments at the end of "#endif"s
  • Update the www
Herald added a project: Restricted Project. · View Herald TranscriptNov 23 2020, 2:19 PM
  • Rebase to trigger CI
This revision was not accepted when it landed; it landed in state Needs Review.Nov 27 2020, 11:17 AM
This revision was automatically updated to reflect the committed changes.