This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Forward more often to memmove in copy
ClosedPublic

Authored by philnik on Apr 23 2022, 8:10 AM.

Details

Summary

In D122982 I accidentally disabled the memmove optimization. This re-enables it and adds more cases where copy forwards to memmove.
Fixes https://github.com/llvm/llvm-project/issues/33687

Diff Detail

Event Timeline

philnik created this revision.Apr 23 2022, 8:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 23 2022, 8:10 AM
philnik requested review of this revision.Apr 23 2022, 8:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 23 2022, 8:10 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

Fixes https://github.com/llvm/llvm-project/issues/33687

What exactly? For the testcases, I see two memmoves with libc++:

https://gcc.godbolt.org/z/GeWf6b179

Fixes https://github.com/llvm/llvm-project/issues/33687

What exactly? For the testcases, I see two memmoves with libc++:

https://gcc.godbolt.org/z/GeWf6b179

This now unwraps even weird stuff like reverse_iterator<reverse_iterator<int*>>. It also unwraps reverse_iterator<std::vector<int>::iterator> properly (and combinations). In D122982 I disabled the std::vector<int>::iterator unwrapping accidentally.

var-const requested changes to this revision.Apr 27 2022, 7:54 PM

Is it possible to add some tests for this? For checking the optimization, perhaps use structs containing pointers to dynamically-allocated memory that have deep-copying constructors, then check that only the pointers themselves were copied?

libcxx/include/__algorithm/copy.h
74

Nit: I think checking _InIter should happen before _OutIter for consistency with the argument order.

105

Question: why wouldn't the other reverse_iter overload that calls __unwrap_iter handle the case?

This revision now requires changes to proceed.Apr 27 2022, 7:54 PM
philnik updated this revision to Diff 425777.Apr 28 2022, 7:39 AM
philnik marked 2 inline comments as done.
  • address comments

Is it possible to add some tests for this? For checking the optimization, perhaps use structs containing pointers to dynamically-allocated memory that have deep-copying constructors, then check that only the pointers themselves were copied?

I don't think there is a way to check other than grepping for memmove in the binary. IIUC you suggestion would be to add non-trivial assignment operators, but that would disable the optimization. The optimization should only apply if it's invisible to the user.

libcxx/include/__algorithm/copy.h
105

With a reverse_iterator<reverse_iterator<int*>> the other overload would have _InIter = reverse_iterator<int*>. This is only a random access iterator and not a contiguous iterator, so it wouldn't get unwrapped.

var-const accepted this revision as: var-const.Apr 28 2022, 2:13 PM

IIUC you suggestion would be to add non-trivial assignment operators, but that would disable the optimization. The optimization should only apply if it's invisible to the user.

Ah, I think you're right.

libcxx/include/__algorithm/copy.h
105

Can you please add a comment to that effect in this function? The fact that __unwrap_iter only deals with contiguous iterators is really not obvious without looking at its implementation.

philnik updated this revision to Diff 426392.May 2 2022, 6:10 AM
philnik marked an inline comment as done.
  • Try to fix C++03
dcheng added a subscriber: dcheng.May 13 2022, 3:02 PM

Not sure if this helps, but Chrome noticed this breakage during an attempt to roll libc++: https://crbug.com/1322961

The "test" that we have for this is quite horrible and I'm not sure that we'd want to adopt it here, but just for the sake of completeness: https://source.chromium.org/chromium/chromium/src/+/main:base/containers/checked_iterators_unittest.cc;l=101;drc=633d2d745d1fd09256ab846e7f923fbc5c084770

philnik updated this revision to Diff 429381.May 13 2022, 4:10 PM
  • Add test
philnik updated this revision to Diff 429430.May 14 2022, 3:31 AM
  • Try to fix CI
ayzhao added a subscriber: ayzhao.May 17 2022, 9:39 AM
ldionne requested changes to this revision.May 17 2022, 11:39 AM
ldionne added inline comments.
libcxx/include/__algorithm/copy.h
51

This is one of the reasons why I like sharing implementations between ranges versions of algorithms and non-ranges versions. Even a simple algorithm like std::copy can become not-so-simple due to subtle reasons, and we'd risk not fixing/improving one of the two algorithms if we had two copies. Nothing to do about this comment, just a rationale for why I can appear annoying with my requests to share ranges and non-ranges code.

59–75

Is it possible that what you're looking for here is instead is_contiguous_iterator<_Iter> && is_trivially_copy_assignable<value_type<_Iter>>? I don't think we have a trait for is_contiguous_iterator that works with older standards and understands __wrap_iter properly, but we probably should if that's indeed what you mean.

99–101

Can you negate the condition used below instead? It makes it easier to understand what's going on:

__enable_if_t<!(is_copy_constructible<_InIter>::value
                && is_copy_constructible<_Sent>::value
                && is_copy_constructible<_OutIter>::value)>
116–119

Can you use class = __enable_if_t<...> instead to allow placing the return type in the usual place? Note that if you run into duplicate declaration issues, you can use non-type template parameters instead:

template <class _InIter, class _Sent, class _OutIter, __enable_if_t<CONDITION>* = nullptr>
...
libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp
12 ↗(On Diff #429430)

This needs a comment explaining what the test does (it tests that we optimize copy operations into memmoves IIUC).

This revision now requires changes to proceed.May 17 2022, 11:39 AM
philnik updated this revision to Diff 431002.May 20 2022, 9:53 AM
philnik marked 4 inline comments as done.
  • Address comments
philnik updated this revision to Diff 431178.May 21 2022, 2:41 PM
  • Try to fix CI

@philnik It looks like you're working on this in your spare time. Do you know when you'll be able to get back to it? Chromium downstream is waiting on this to land before updating to the latest libc++ sources, to avoid regressing perf.

@philnik It looks like you're working on this in your spare time. Do you know when you'll be able to get back to it? Chromium downstream is waiting on this to land before updating to the latest libc++ sources, to avoid regressing perf.

The patch works. Right now I'm just waiting for @ldionne to review it. It should be done by Friday.

ldionne accepted this revision.Jun 2 2022, 8:25 AM

LGTM, but let's fix the failing CI tests. Thanks!

libcxx/include/__algorithm/copy.h
127

I would like to investigate (in a different patch if the experiment turns out positive) the possibility of overloading __unwrap_iter (and __rewrap_iter) for reverse_iterator<reverse_iterator<It>> more generally. If that works out, we would get some added benefits in other algorithms as well for free, and this overload could go away entirely.

libcxx/test/libcxx/algorithms/alg.modifying.operations/copy.pass.cpp
14 ↗(On Diff #431178)
This revision is now accepted and ready to land.Jun 2 2022, 8:25 AM
philnik updated this revision to Diff 433993.Jun 3 2022, 3:50 AM
philnik marked an inline comment as done.
  • Fix tests and address comments
libcxx/include/__algorithm/copy.h
127

Added a TODO

This revision was automatically updated to reflect the committed changes.