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.
Details
Details
- Reviewers
var-const Mordante ldionne - Group Reviewers
Restricted Project - Commits
- rG2c3bbac0c715: [libc++] Implement ranges::move{, _backward}
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
| 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/. | |
Comment Actions
- 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. | |
Comment Actions
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? | |
| 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. |
| libcxx/include/__algorithm/ranges_move.h | ||
|---|---|---|
| 38–44 | Why do we need this overload? shouldn't ranges::move always call ranges::iter_move? | |
| 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. | |
| 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. | |
| 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. | |
| 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 | |
| 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. | |
Nit: you can use std::make_pair.