Use trivial relocation operations in std::vector, by porting D67524 and part of D61761 to work on top of the changes in D114732.

[devin.jeanpierre]

Summary

This change is based on work from @Quuxplusone in D67524 and D61761. All credit to them, all blame to me for any errors or problems, as I may have accidentally made it worse. :)

Previous change: D114732

---

The benefit here is that it can make trivially relocatable types -- by which, for now, we mean "types which are trivial for calls" -- easy to optimize. I have measured performance improvements of up to 0.25% on some large server macrobenchmarks.

For microbenchmarks, with my copy of clang, this change makes std::vector<std::unique_ptr<T>>::push_back ~38% faster when trivial_abi is enabled on unique_ptr.

This also also to unlocks further optimizations: it is, after this change, even more profitable to convert an existing type to trivial_abi, e.g. to enable it on even more types in the standard library than just the smart pointers. For example: it could become more worthwhile, after this change, to try to mark std::string as [[trivial_abi]].

---

Changes from D61761 and D67524:

1. This change does not include support for std::swap (*relatively* low value, and very difficult to do correctly), just vector operations. It also does not include the relocate_at family of functions.
2. (minor) Use __is_default_allocator instead of a new __is_exactly_std_allocator. At least to my eye, these seemed identical.
3. bugfix to erase: it would memove N *bytes*, instead of N *items*.
4. The tests now use std::conditional to enable trivial relocatability, as [[clang::trivial_abi]] doesn't take a bool parameter.
5. Due to a (new?) warning that breaks the test, I had to add a layer of indirection to the countdown in insert_exception_safety_pass.
6. in is_trivially_relocatable.pass.cpp:
   • I renamed the classes to suit my personal taste (e.g. NonEmpty->Polymorphic, as it's a nonempty polymorphic class).
     • I moved the static_asserts directly into main, so that I could see which one failed. This drops the test that is_trivially_relocatable and is_trivially_relocatable_v are identical, but this can be verified by inspection.
     • The test asserted that const MoveOnly2 was trivially relocatable, even though it was not trivially move-constructible due to the const. I reversed the test, but I'm not 100% sure whether that was the right fix.
7. Finally, of course, some things in the source tree have changed, and I had to figure out where to put things. Not sure if I did it right!

The most important bit I want feedback on: are there any changes to the compiler needed to actually make it defined behavior to memcpy a trivially-relocatable type? I believe the answer is no, but want to double check. I chatted a bit with @rsmith, and the takeaway that I got was that Clang defines the behavior (or at least, doesn't exploit undefined behavior) for all non-polymorphic types. Since trivially relocatable types cannot be polymorphic, this should be a documentation-only change: we explicitly extend implicit-lifetime types to also include trivially-relocatable types (which are, at least for now, all trivial-abi types.)

It is possibly worthwhile to note that vector *already*, before this change, used memcpyor memmove on types which have nontrivial destructors, and are therefore not implicit-lifetime. So it already had in mind some extension to implicit-lifetime types, though not one which it describes explicitly. This change further extends it to also include all __is_trivially_relocatable types.

[devin.jeanpierre]

In D119385#3392540, @ldionne wrote:

@devin.jeanpierre Would you be willing to get on a call with me to go over your patch? I think it would make it easier to make progress -- you have significantly more context than me around it, so it'd be helpful for me.

Almost missed this request -- absolutely, I'd be happy to. I don't know the procedure around this stuff though.

Edit: sent wrong draft. Meant to add: I'm free during the day pacific time, you can schedule something with me out of band via email/chat to jeanpierreda [at] google [dot] com.

libcxx/include/memory

862

So it definitely does change semantics: if you call __construct_backward_with_exception_guarantees with true_type, but the object is not trivially-movable, then you are promising that 1) it is trivially relocatable (via [[clang::trivial_abi]], today), and 2) you will be releasing the underlying storage of the "moved"-from objects without invoking the destructor.

The compiler can infer (1): it could just check for trivially relocatability. That's what the callers do! But it cannot check for (2), the caller has to be careful here. So I do think it should probably be explicit.

If I were to do it myself, I'd probably pass in reinterpret_cast<const char*>(my_pointer), rather than defining a separate function. The benefit of having it be a true_type/false_type argument is, I suppose, that it's easy to call: it's just a parameter as to whether to use trivial relocation, and the caller can do neat so that they have just one call site with a varying parameter. I can see the merit to it. For example, one caller looks like so:

__construct_forward_with_exception_guarantees(this->__alloc(), __p, this->__end_, __v.__end_, __move_via_memcpy());

If we were to make it different functions, or require a reinterpret_cast in the caller, it would become:

if (__move_via_memcpy::value) {
  __trivial_construct_forward_with_exception_guarantees(this->__alloc(), __p, this->__end_, __v.__end__;
  // or: __construct_forward_with_exception_guarantees(this->__alloc(), reinterpret_cast<const char*(...),  reinterpret_cast<const char*(...), reinterpret_cast<const char*(...);
} else {
  __construct_forward_with_exception_guarantees(this->__alloc(), __p, this->__end_, __v.__end__;
}

So I can see the merit to it.

Of course, the magic boolean parameter seemed weird to me too. It was impressed on me when I asked a coworker that it is not so strange, and indeed cases already exist of it in llvm: for example, __move_assign in vector, __process in memory, etc.

So what I want to know is -- is this really that weird, and existing code is "legacy" code we should try not to emulate? Or is this relatively normal? I will do whatever the "normal" thing is. :P

Leaving your comment unresolved. :)

877

(I confess I'm not sure why this had to be changed. I can only assume because now it's selected in branches that, yes, use __wrap_iter, but it's very indirect.)

FWIW _Ptr was already in use in the other overload, so I would prefer to leave it unchanged for now. LMK if I should change both, or if it's acceptable/preferable to change just this one, and I'll do so.

885

The const_cast is to support vector<const T>, see e.g. libcxx/test/libcxx/containers/sequences/vector/const_value_type.pass.cpp.

I thought libc++ no longer supported const-qualified value types, but it seems that test is still there, and the change deleting it was rolled back. So until libc++ properly removes this, I need to retain the const_casting after all. Oops!

Note that this isn't "new" -- e.g. line 902 of the LHS revision at time of writing also does a const_cast for the same reason. However, I added a comment anyway, to avoid confusion.

Did my best to replace _VSTD with std.

libcxx/include/type_traits

3130–3134

That makes sense to me. In point of fact, I was thinking the same thing!

libcxx/include/vector

329

Deleted, and with joy in my heart.

Unfortunately I then proactively did the same for const, because I thought that change had gone in -- but the change deleting const-qualification support in libc++ was rolled back.

713–714

Unfortunately I'm not sure what this is asking, and probably don't have the background to give an informed answer. Anyone else want to step in here?

919–922

Yeah, I agree. WDYT about how I've done it now? Three categories:

• trivial_relocate: relocation operations can be trivial (both move+destroy), because the type is trivially relocatable
• relocate_trivial_move: relocation operations use memcpy -- maybe because it's trivially relocatable, maybe because it's trivially movable
• relocate_trivial_destroy: relocation operations drop underlying storage without invoking the destructor -- maybe because it's trivially relocatable, maybe because (in a future change) it's trivially destructible?

I've made the corresponding changes to the source so you can see how it plays out.

1651–1663

Ah, sorry, I was just doing whatever the code already did. Looks like it was unnecessary.

1656

(Please forgive me if I'm misunderstanding something here.)

Not without casting to e.g. std::byte pointers first -- that would invoke move constructors, where here we should be copying raw bytes.

The difference in behavior comes up if you have a nontrivial but clang::trivial_abi type, such as:

struct [[clang::trivial_abi]] MyClass  {
  MyClass(const MyClass&) { ... }
  MyClass(MyClass&&) { ... }
  ~MyClass() {}
};

The intention of this change is to use memmove for this type, and not invoke move constructors etc.. So we skip across std::move and instead use memmove.

We also cannot move this optimization to std::move, because in general, std::move should still be calling move constructors: it is only in the specific case that the moved-from location is destroyed immediately afterwards that we can safely use memcpy/memmove: we can replace a move+destroy pair with a relocate + release-underlying-storage pair.

(That's not quite what's happening with erase, but we could imagine it was: erase is, I believe, allowed to work as if it moved everything after the erased point to a temporary buffer, destroyed the original objects, and then moved them back, destroying the temporary buffer.)

Hoping that addresses your comment!

1693

This is in the #else block, so that's fine, right? (Should only fire for C++11 and up, since e.g. 98 isn't supported.)

1698

Could you rename this to something like __is_nothrow_constructible_alloc? __is_nothrow_constructible_a sounds a lot like you needed another name and you just slapped _a at the end.

Agreed, and done!

Do you only have this to allow better optimizations in C++03? If that is the case I'd say just remove it. If you care about performace you should switch to C++11 or newer. We currently don't even enable the move overloads in C++03 in most (all?) classes.

Hmmm, correct me if I'm wrong, but I think it's the #else block that doesn't do anything. These two lines are basically equivalent:

struct __is_nothrow_constructible_a : integral_constant<bool, false> {};
struct __is_nothrow_constructible_a : integral_constant<bool, noexcept(allocator_traits<_Allocator>::construct(declval<_Allocator&>(), (_Tp*)nullptr, declval<_Up>()))> {};

... because allocator_traits<T>::construct is never noexcept unless you specialize it, which libc++ does not permit.

The intent of the check is clearly that the ::construct call will not throw, which we can determine, instead, by if the allocator defines construct at all. (Since we don't support overloading the trait).

Something like: is_nothrow_constructible<_Tp, _Up>::value && (__is_default_allocator<_Allocator>::value || !__has_construct<_Allocator, _Tp*, _Tp>::value

Does that look good?

libcxx/test/libcxx/containers/sequences/vector/insert_trivially_relocatable.pass.cpp

14

Apologies, I think earlier reviewers made the same comment and I accidentally failed to address it. My bad.

20

Not super sure what is allowed in constant evaluation, but hoping this is what you meant. At the very least, I believe it's an improvement.

libcxx/test/libcxx/type_traits/is_trivially_relocatable.pass.cpp

1 ↗

(On Diff #409779)

Well, but we are adding __libcpp_is_trivially_relocatable. Perhaps this should go in a separate change, though, since morally speaking it's testing __is_trivially_relocatable? WDYT?

1–8 ↗

(On Diff #409779)

Apologies, I didn't even think to check for that! Done -- looks like it was just the two tests.

56–72 ↗

(On Diff #409779)

Agreed, and done. :)

Actually, I hadn't looked closely at this test. I think it can be simplified a bit too -- for example, rather than having a separate nontrivial key type, I just added operator== etc. to the nontrivial type. (Could do the same for the mutex type, but wasn't sure if that'd be even more confusing.)

78–83 ↗

(On Diff #409779)

Ooh, indeed.

85–86 ↗

(On Diff #409779)

You are 100% right, done.

libcxx/test/libcxx/utilities/meta/meta.unary.prop/is_trivially_relocatable.pass.cpp

16 ↗

(On Diff #409779)

Apologies, and thanks for the correction!

94 ↗

(On Diff #409779)

Good call, thank you!

[devin.jeanpierre]

libcxx/test/libcxx/type_traits/is_trivially_relocatable.pass.cpp

243 ↗

(On Diff #416606)

This should also be a .compile.pass.cpp. Just making the comment now before anyone else does -- I have to step away from my computer for a bit, but will get back to it.

[philnik]

This looks good so far. I think with Louis' and my comments addressed this should be good to go, but I want to do another thorough review with the comments addressed before approving this.

libcxx/include/vector

713–714

I think that's a question @ldionne has to answer. My question is essentially if we want to have this as part of the ABI or if it should be marked _LIBCPP_HIDE_FROM_ABI.

919–922

Yes, looks much better!

1656

Right, I missed that it's implicitly casting to void* in the call to std::memmove. Using std::move would look something like

std::move(reinterpret_cast<byte*>(__rawp + 1), reinterpret_cast<byte*>(__rawp + (__end_ - __p) * sizeof(_Tp)), __rawp);

. That's obviously not an improvement. Currently I also don't have any good idea to make it more readable.

1693

I think you misunderstood me a bit. We don't support C++98, but we do support C++03. I know there isn't a huge difference, but it's significant enough in a standard library implementation to point out. Although the C++03 support is very weird, but that's another story.

1698

It definitely makes sense to me. Maybe you could check if the allocator::construct member function is noexcept. That would include more allocators. Something like !__has_construct<_Allocator, _Tp*, _Tp>::value || __nothrow_invocable<_Allocator::construct, _Tp*, _Tp>::value should work. (I haven't tested it.)

1703

Is this a forward? If yes, please spell it as one.

libcxx/test/libcxx/containers/sequences/vector/insert_trivially_relocatable.pass.cpp

20

Yes, that's exactly what I had in mind.

libcxx/test/libcxx/type_traits/is_trivially_relocatable.pass.cpp

94–96 ↗

(On Diff #416606)

Why aren't these trivially relocatable? These should be in the unstable ABI because they are marked [[clang::trivial_abi]], or am I not understanding something?

116–131 ↗

(On Diff #416606)

Do you have any interest in making a follow-up PR for these? It should be possible to make these all trivially_relocatable, right?

[devin.jeanpierre]

Deleted libcxx/test/libcxx/type_traits/is_trivially_relocatable.pass.cpp, changed static_cast to std::forward

[devin.jeanpierre]

Really sorry about the delay on this one, I stepped away to work on a build breakage for the predecessor PR, and then never came back to this. (And then I felt bad about never coming back to this, and... well, maybe you know how it is, "ugh field" etc.) I'll try to stay more on top of this, since I definitely want it to go in! I'm really excited about this change. :)

Let me know how to proceed. And, obviously, feel free to take your time, I don't have the right at this point to request speedy review.

libcxx/include/vector

1693

I'm still not following. My understanding had been that this should be fine, because noexcept is only used if _LIBCPP_CXX03_LANG is not defined, meaning that we only use noexcept on C++11 and above.

I think this is no longer relevant though, since that code snippet is deleted.

1698

It's more complicated than that, because the allocator is allowed not to define construct -- so we need to do the dance that __has_construct does to ensure that this fails gracefully (SFINAE) when it doesn't exist.

Can we defer this / not implement it now? I played around with this a bit, but as it turns out I'm really not very familiar with template metaprogramming in C++. If this is a strongly desired feature, I can write a followup as my very next change, but otherwise I'd actually prefer not to write it at all until a concrete use presents itself. :)

(I think such concrete uses may not exist at all, or be very rare -- it'd be a construct function that is defined only for types with noexcept constructors, which is I think impossible to guarantee in C++ (you can't enumerate all the constructors). So the only allocators that would satisfy this are those that are special-cased to known types to be noexcept, or which are noexcept even though the underlying constructors might throw.)

1703

Ah, yes, it is, since _Up is a template parameter. Fixed.

libcxx/test/libcxx/type_traits/is_trivially_relocatable.pass.cpp

94–96 ↗

(On Diff #416606)

Great catch.

Um, actually, on reflection, this whole file is a nightmare of test failures depending on build mode. My experience with the predecessor PR D114732 is that this will be very hard to get right -- we will need ifdefs for win64 and for PS3, at the least -- not to mention, as you've noticed, checking for the unstable ABI.

Moreover, I think it doesn't really belong in this change. So at least for now, I'm reverting it entirely. If this change should go in, I think a separate PR would be best. (It's basically testing D114732, and possibly not this change.)

116–131 ↗

(On Diff #416606)

Yes, I think we should put work into making many common datatypes [[clang::trivial_abi]], in the same way as already done for unique_ptr, and I want to do this for at least a couple common/easy ones (hoping std::vector, std::string qualify).

Others might require more substantial design work to make this happen (e.g. the map types), and it might be that yet others fundamentally can't (e.g. std::list -- something in there is going to be inherently non-trivially-relocatable, since it's self-referential by design).

[philnik]

libcxx/include/vector

713–714

We are in vector so this won't be exported in our dylib. I think this should be marked _LIBCPP_HIDE_FROM_ABI.

1698

You could have something like void construct(Args&&... args) noexcept(noexcept(T(args...))). I don't think that's too rare, but we can do that later if you want. If you don't feel comfortable writing that fun stuff I can try as well.

libcxx/test/libcxx/type_traits/is_trivially_relocatable.pass.cpp

116–131 ↗

(On Diff #416606)

Great! I think starting with string would be good. That's like the most commonly used type in the library and there won't be that many more changes in the near future AFAIK.

libcxx/test/libcxx/utilities/meta/meta.unary.prop/is_trivially_relocatable.compile.pass.cpp

13

This shouldn't be here.

libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_exception_safety.pass.cpp

65

What does that do? If it's just a cast to bool could you maybe just make if a functional cast? That's a lot less surprising.

[devin.jeanpierre]

Act on review comments. TY for the speedy review!

[devin.jeanpierre]

Manually reflow comment. (I had hoped that clang-format would do it for me, oops.)

[devin.jeanpierre]

Actually reflow comment. (SSH session had disconnected, saves were going to /dev/null. ... this actually is super discouraging behavior in vscode, I'm scared now.)

[devin.jeanpierre]

libcxx/include/vector

713–714

Sounds good to me, and thanks for following up here. Done.

1698

Ah, that goes to show my unfamiliarity with exceptions/noexcept. That's a compelling example, and I agree we should support it.

I think this would make a very decent standalone PR after the fact -- I don't think we need to do it in this PR. I will, uh, iron out the implementation with some coworkers who know the idioms here, and send a followup PR. So I'm marking as resolved for now. Should I add some form of TODO comment to mark this as a potential improvement, or no?

libcxx/test/libcxx/utilities/meta/meta.unary.prop/is_trivially_relocatable.compile.pass.cpp

13

Definitely __libcpp_is_trivially_relocatable_v should be deleted, but I think __libcpp_is_trivially_relocatable does belong here -- it emulates the style of the other files. (Except it should start with // <type_traits>, not // type_traits).

For example, variant_size.pass.cpp opens with:

// <variant>

// template <class ...Types> class variant;

or, tuple_array_template_depth.pass.cpp opens with:

// <tuple>

// template <class... Types> class tuple;

// template <class Tuple, __tuple_assignable<Tuple, tuple> >
//   tuple & operator=(Tuple &&);

// This test checks that we do not evaluate __make_tuple_types
// on the array when it doesn't match the size of the tuple.

I see a similar pattern in every test file I open here: they (usually) list the header they're testing, and (always) list the specific function or type being tested.

(They do it below the UNSUPPORTED line though, so moved that.)

84

I have a feeling that this test is going to have failures on a few platforms (e.g. PS4, Win64), now that I've had experience with the predecessor change and its rollbacks. I'm asking in discord for how to run the tests locally, without doing a slow upload / look at build results loop. (I haven't even looked at the failures for this right here, actually.)

https://discord.com/channels/636084430946959380/642374147640524831/971015700665761833

Just leaving this (unresolved) comment to mark that additional work is needed here.

libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_exception_safety.pass.cpp

65

Not sure what you mean by functional cast, but maybe it'd be clearer as a ;;?

I also added a comment to document the test itself and its behavior.

[philnik]

From me it's just nits at this point, so LGTM. Please wait for @ldionne to approve.

libcxx/include/memory

856–857

Why does this comment exist?

880

using is supported as an extension in C++03. You don't have to use using, but I think it's a lot nicer to read.

881

Could you reformulate this to make it a TODO?

libcxx/include/type_traits

3119–3128

I think this should be equivalent.

libcxx/include/vector

325–330

337–342

713–715

1698

I think adding a TODO would be good, since we know it can be improved relatively easily.

libcxx/test/libcxx/containers/sequences/vector/insert_trivially_relocatable.pass.cpp

14

Why exactly is it not supported in C++03?

libcxx/test/libcxx/utilities/meta/meta.unary.prop/is_trivially_relocatable.compile.pass.cpp

13

I only meant the __libcpp_is_trivially_relocatable_v :)

15

Missed one.

libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_exception_safety.pass.cpp

65

I mean that you could use bool(Mask & 1), .... I think it's actually called function-style cast, not functional cast.

[devin.jeanpierre]

This comment was removed by devin.jeanpierre.

[devin.jeanpierre]

A couple notes:

• I was really struggling to run tests locally and only uploaded this to run the tests. Unfortunately, that also did things like mark comments as resolved, oops. Tomorrow I might try again to get local tests working, as I expect many rounds of test fixing, and CI is taking longer than expected.
• I struggled a bit with git and lost some work. Did a couple passes over everything to make sure I actually addressed everything I hit done on (and didn't e.g. fix it before accidentally losing work), but I'm very sorry if I missed something!

Aside from comments, also tried to fix test failures (e.g. fixed my local copy of clang-format so that it runs -- my copy of Debian doesn't have the python binary that git clang-format expects, just python2 and python3; and disabled execution of the exception test on tests that disable exceptions)

libcxx/include/memory

856–857

Without reading the implementation, one doesn't know the difference between __construct_forward_with_exception_guarantees(a, x, y, z, true_type) and __construct_forward_with_exception_guarantees(a, x, y, z, false_type), so I figured documentation was appropriate to clarify. (Well, not that this function is incredibly well-documented right now.)

I can delete it if it's actually obvious and these overloads mean the same thing everywhere.

880

Ah, sorry. I should've gone through the whole PR and fixed these the first time around. Done.

The other instance I replaced was in __construct_backward_with_exception_guarantees.

881

Done!

libcxx/include/type_traits

3119–3128

Also gets rid of the memey #if inside of the integral_constant type.

libcxx/include/vector

325–330

This looks prettier than it has any right to. :) Done, and thank you!

713–715

Apologies, I had hoped arc diff would autoformat this correctly.

libcxx/test/libcxx/containers/sequences/vector/insert_trivially_relocatable.pass.cpp

14

Ah. I had copied this from the change I'm forward porting, but I believe it is trivial to support C++03 in this test, so I've done so and removed the comment.

libcxx/test/libcxx/utilities/meta/meta.unary.prop/is_trivially_relocatable.compile.pass.cpp

15

Sorry, I don't know what happened there.

libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_exception_safety.pass.cpp

65

Sorry, I think phabricator was attributing your comment to the wrong line (I saw it on the for statement before. At the moment, it's now centered on a comment line.). Replaced with casts.

[devin.jeanpierre]

Oops, forgot C++03 doesn't do Template<Template2<T>>.

[devin.jeanpierre]

1. actually make C++03 compatible: use __attribute__((trivial_abi)), a custom struct instead of std::conditional
2. Add the static asserts for trivial relocatability to both tests that define a conditionally-trivially-relocatable type.

[devin.jeanpierre]

... sigh, apparently I made the static_assert change at the last minute and forgot to run check-cxx. Fixed.