Page MenuHomePhabricator

[libc++] Implement ranges::move{, _backward}
ClosedPublic

Authored by philnik on May 29 2022, 9:28 AM.

Details

Summary

This patch also adds a new optimization to std::move. It unwraps three reverse_iterators if the wrapped iterator is a contiguous_iterator and the iterated type is trivially_movable. This allows us to simplify ranges::move_backward to a forward to std::move without any pessimization.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
var-const requested changes to this revision.Jun 3 2022, 9:15 PM
var-const added inline comments.
libcxx/include/__algorithm/move.h
37

Nit: you can use std::make_pair.

40–55

Nit: I think we usually don't add T to template type names.

49

Can you provide a bit more context about this workaround?

54

Is this check necessary? Does __builtin_memmove require the argument not to be zero?

73

Question: if _InIter and _OutIter have the same underlying value type, wouldn't __is_trivially_move_assignable_unwrapped always return the same result for both of them?

76

Question: this is a new optimization that isn't directly related to implementing ranges::move, right?

84

Very optional: you can use make_reverse_iterator.

90

Is this used? (same for this function's implementation below)

107–108

Nit: this should be _InIter for consistency (I'd personally prefer _InputIter, but feel free to ignore).

libcxx/include/__algorithm/move_backward.h
28 ↗(On Diff #432792)

I'd rather keep the previous approach -- it's more verbose, but also straightforward, symmetrical with move.h, and avoiding the extra overhead from using reverse iterators (which includes the additional mental burden when reading the code and more complicated types when debugging).

libcxx/include/__algorithm/ranges_move.h
21

Nit: seems unused (in the other ranges header as well).

41

Question: can you provide more context on this constraint?

56

Nit: move the iterators?

libcxx/include/__algorithm/ranges_move_backward.h
46

Why does this function forward to __move with reverse iterators rather than __move_backward? (I understand that __move_backward would have to be added) While this would be more boilerplate, I think it would be simpler, more consistent, and avoid the extra overhead from using reverse iterators (and probably the need to treat them specially in __move).

73

Nit: move result.

libcxx/include/algorithm
362

Please double-check the synopsis, there are a few mentions of copy that should be move (e.g., s/copy_backward_result/move_backward_result/).

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp
16

Same as synopsis, there are a few mentions of copy (in the other test file as well).

39

Question: are these types for checking the weakly_incrementable constraint? Just clarifying because the names seem unrelated.

53

Please also check the weakly_incrementable constraint.

95

How about a name like IteratorWithIterMove to make it a little easier to parse?

102

Nit: s/derefernced/dereferenced/.

112

Can you add a test case that deals with a move-only type?

122

Nit: decltype(auto).

139

Nit: s/copied/moved/.

169

Nit: s/canCopy/canMove/.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move_backward.pass.cpp
4

Comments from the other test file apply here as well.

14

Ultranit: there's an extra blank line.

140

Nit: s/copied/moved/.

141

Nit: s/CopyOnce/MoveOnce/.

This revision now requires changes to proceed.Jun 3 2022, 9:15 PM

Please update the ranges status page.

philnik updated this revision to Diff 435382.Wed, Jun 8, 4:17 PM
philnik marked 25 inline comments as done.
  • Rebased
  • Address comments
libcxx/include/__algorithm/move.h
49

What are you asking about exactly? Why I have to check for is_trivially_copyable? That's because __builtin_memmove requires the type to be trivially_copable. Or do you mean something else?

54

AFAIK __builtin_memmove doesn't require the argument to be non-zero. The compiler doesn't eliminate the check either so I'm not sure if it should stay or not. This means potentially less function call, but also a branch more. I don't think it makes a large difference either way, so I'll remove it.

73

__is_trivially_move_assignable_unwrapped also checks that we get a raw pointer. But that's not relevant, since I'm updating the check to be equivalent to the check in copy.

76

It's a new optimization for std::move, but I'm removing a specialization from std::move_backward that would have done the same thing. Without this 'new' optimization I would pessimize std::move_backward and ranges::move_backward. I also think it's a good idea to implement more algorithms in terms of other algorithms to get more optimizations and get the optimizations into a single place instead of duplicating them all over the place. To achieve that I'm using reverse_iterator in quite a few places, so it's getting a lot more likely to have weird things like reverse_iterator<reverse_iterator<T>> or even more wrapped around.

84

make_reverse_iterator requires C++14 and I don't think it's worth to add a new __make_reverse_iterator for relatively little extra convenience.

90

This has been superseded by D127049. Removing it.

107–108

Nope. This is one of the classic STL algorithms where we use _InputIterator and friends. This is specifically to make them easily distinguishable.

libcxx/include/__algorithm/move_backward.h
28 ↗(On Diff #432792)

I strongly disagree. It's currently a lot of code duplication without any obvious benefit IMO. I don't see how any symmetry is good here. We already have a better implementation of the algorithm, so why not use it? I also don't understand what mental burden you mean. I think it's a lot easier to reason about a forward going algorithm. If that works, a reverse_iterator call to that also works. With a reverse_iterator the types are technically more complicated, but how often do you step into move_backward? Almost never I would think. Forwarding to std::move also allows code sharing if you have std::move(reverse_iterator<T>) and std::move_backward(T) and similar combinations.

libcxx/include/__algorithm/ranges_move.h
41

As you can see below, ranges::move is required to use ranges::iter_move. The overload with __move_deref<_Iter> is the one that uses std::move(*__iter) (effectively). I think this can also be enabled in the __just_deref case, but I'm not sure and I wanted to play it safe for now.

libcxx/include/__algorithm/ranges_move_backward.h
46

See my comment in move_backward.h.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp
39

Nope, that's for checking the requires clause. I just forgot to rename it to NotIndirectlyMovable though. weakly_incrementable is checked by WeaklyIncrementableNotMovable.

var-const requested changes to this revision.Thu, Jun 9, 7:43 PM

Please update the ranges status page.

libcxx/include/__algorithm/move.h
49

I'm asking about the preprocessor guard, why the check is only done if the compiler is not GCC.

54

I'd expect 0 to be a very rare case, so I wouldn't add branching to the common case for the sake of it. Moreover, the 0 case will be pretty efficient even without omitting the function call.

76

I think this is useful context, consider adding a condensed version of it to the patch description.

84

Makes sense, thanks for explaining.

107–108

Ah, I must have missed that part of the discussion, thanks for explaining.

libcxx/include/__algorithm/move_backward.h
28 ↗(On Diff #432792)

Let's say I'm writing a custom iterator and get a crash somewhere further down the stack from move_backward. The mental burden is having to deal with the additional layer of indirection from reverse_iterator. It might be a rare use case, but I don't think we can afford to ignore rare use cases given the size of our user base. Debugging experience is a common complaint about C++.

That said, I understand better why you prefer this approach after seeing the reverse_copy implementation which is quite elegant. Since this is a decision that can affect the implementation of quite a few algorithms, I'd ask @ldionne for guidance and defer to his opinion.

libcxx/include/__algorithm/ranges_move.h
41

Thanks. Can you add a comment like "Checks that std::move(*__iter) is well-formed"? I didn't find it entirely obvious from the name, and the implementation checks for a few different things.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp
114

Can you please add a brief comment explaining why cpp17_input_iterator doesn't work?

This revision now requires changes to proceed.Thu, Jun 9, 7:43 PM
ldionne added inline comments.Fri, Jun 10, 8:58 AM
libcxx/include/__algorithm/move_backward.h
28 ↗(On Diff #432792)

I understand Costa's point about debugging and I agree with it to some extent. However, concretely, I don't think users would be stepping through our whole std::move_backward implementation anyways, and if so, they are probably placing breakpoints in strategic places in their code to avoid stepping through our implementation details. Hence, I think there are other ways to mitigate the downsides of this implementation, and I think the optimization in std::move and the removal of duplication in std::move_backward are worth it. Just my .02, but I would err towards the currently-proposed approach. If we gain more experience with this sort of technique (which BTW is akin to expression templates in a really basic way), and if we realize that it has negative effects for our users, we can and should revisit this stance.

philnik edited the summary of this revision. (Show Details)Sat, Jun 11, 1:18 PM
philnik updated this revision to Diff 436166.Sat, Jun 11, 1:28 PM
philnik marked 9 inline comments as done.
  • Address comments
libcxx/include/__algorithm/move.h
49

GCC currently doesn't support __builtin_memmove during constant evaluation, so we have to fall back to the naive implementation.

libcxx/test/std/algorithms/alg.modifying.operations/alg.move/ranges.move.pass.cpp
114

Because I forgot to add it :P

var-const accepted this revision.Mon, Jun 13, 2:47 PM

LGTM (didn't review the reverse_iterator changes that come from a different patch).

This revision is now accepted and ready to land.Mon, Jun 13, 2:47 PM
philnik updated this revision to Diff 439294.Thu, Jun 23, 2:46 AM
  • Undo the changes to move_backward for now
philnik updated this revision to Diff 439304.Thu, Jun 23, 3:02 AM
  • Try to fix CI
philnik updated this revision to Diff 439311.Thu, Jun 23, 3:24 AM
  • Fix modulemap
philnik edited the summary of this revision. (Show Details)Thu, Jun 23, 3:24 AM
This revision was automatically updated to reflect the committed changes.
huixie90 added inline comments.
libcxx/include/__algorithm/ranges_move.h
38–44

Why do we need this overload? shouldn't ranges::move always call ranges::iter_move?

philnik added inline comments.Fri, Jun 24, 10:27 AM
libcxx/include/__algorithm/ranges_move.h
38–44

This isn't needed, but this allows us to unwrap the iterator and call memmove on trivially_copyable types.

huixie90 added inline comments.Fri, Jun 24, 10:59 AM
libcxx/include/__algorithm/ranges_move.h
38–44

But this overload has the wrong behaviour for proxy iterators. For example zip_view

see this example: https://godbolt.org/z/fWG6Te69T

if you call ranges::move on two zip_views, because zip_view's reference type is tuple<X&>, std::move(tuple<X&>) gives you tuple<X&>&&>, which will still trigger copy assignment of X. but zip_view customises its iter_move to return tuple<X&&> so if you use iter_move(it), it would trigger the move assignment of X.

I think correctness takes precedence of performance.

philnik added inline comments.Fri, Jun 24, 11:06 AM
libcxx/include/__algorithm/ranges_move.h
38–44

That's why it's guarded with requires __iter_move::__move_deref<_InIter> to ensure that ranges::iter_move would just call std::move. Or am I missing something? Your example also looks correct to me: https://godbolt.org/z/vjchvc11z.

huixie90 added inline comments.Fri, Jun 24, 11:14 AM
libcxx/include/__algorithm/ranges_move.h
38–44

I see. I read the comments "// check that we are allowed to std::move() the value" and thought it meant that " std::move(x) is a valid expression". I think what it actually means is "there is no iter_move customisations."

My example is just showing that when there is an iter_move customisation, calling std::move(it, it, o) is the wrong behaviour.

I think your optimisation is ok but the comment can be made more clearer.

BTW, I think you could also turn on this optimisation for both move_deref and just_deref

philnik marked 3 inline comments as done.Fri, Jun 24, 11:31 AM
philnik added inline comments.
libcxx/include/__algorithm/ranges_move.h
38–44

Ah OK. I can see that the comment could be interpreted the wrong way. If you're writing a comment yourself it often feels a lot more obvious than it actually is.
I too think that I could also enable it for __just_deref, but I wasn't 100% sure if I'm correct on that, so I wanted to postpone this optimziation to a follow-up PR. Calling std::move either way is a lot easier to ensure than checking all the implications of casting a type to an rvalue.
Anyways, I'm planning to look into that optimization and I'll update the comment.