[libc++] Implement P0288R9 (move_only_function)

[ldionne]

libcxx/include/__functional/move_only_function_impl.h

6

General comment 2:

Fundamentally, we need to decide whether we're going to implement the function call dispatching using a classic vtable, or generate a "vtable" ourselves (either inlined in the object like you do right now, or not). This has to be thought through, but my initial preference would be to go for a manual vtable with one layer of indirection, since IIRC that's what I had the best results with when I investigated this with Dyno. IIRC, the observation was that you don't really pay for the additional level of indirection if you're calling the function over and over again, since it's hot in the cache anyway. Instead, you're better to just reduce the size of the object. This is a really tough call to make though, because we're operating with a lot of assumptions and we have to make this work well for all possible workloads, which is simply impossible.

Probably relevant things to look at (sorry for the plug): https://github.com/ldionne/dyno and http://ldionne.com/cppnow-2018-runtime-polymorphism. It's been a while but I had done a survey of various techniques in that area and I think the conclusions might still be relevant, even if that's a little bit dated.

65

General comment: Please make sure you have _LIBCPP_ASSERTs in place for UB in this class, and tests that these assertions work as intended.

244

IMO this is too large. I believe that types with sizeof(T) == 32 AND that are trivially move constructible/destructible AND that we want to type erase are going to be quite rare. I think that most types will be either smaller, or will be non-trivial. Shooting from the hip, I would use something like 2*sizeof(void*) at most, but we definitely need to look at what other implementations are doing, and also what other common utilities like this do (let's do a quick survey in open source libraries, e.g. have Folly or Abseil already shipped something like this, and if so, is there something we can learn from their experience?).

252

I think we should make it possible to store non-trivially-fooable types in the small buffer. IIUC you only need that constraint in order to implement swap, but you should be able to handle that by adding yet another function to the vtable. This would create a size issue right now, but wouldn't be a concern anymore if we move to a remote vtable.

[jwakely]

In D130631#3824399, @ldionne wrote:

2. Survey other implementations and also other open source projects to see what approach they've taken.

GCC's implementation (which could change before we declare C++23 support non-experimental) has a SBO buffer that is big enough to store a pointer to member function and an object pointer, i.e. a simple delegate.

Please do file a GCC request for trivial_abi, I don't think that's on anybody's radar yet.

[lichray]

libcxx/include/__functional/move_only_function.h

27

No macro and maintainable. Here is an example: https://github.com/zhihaoy/nontype_functional/blob/main/include/std23/move_only_function.h
With C++ explicit object member function, you can also turn the six operator() into one.

libcxx/include/__functional/move_only_function_impl.h

71

According to STL the person, it is reasonable to "store a std::string locally." To libc++, that's 24 bytes; 32 bytes for the whole mv-func object with a vptr.

[philnik]

• Address some of the comments

libcxx/include/__config

141–142

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=107187

libcxx/include/__functional/move_only_function.h

27

I don't think that implementation is conforming. The standard explicitly states that there have to be partial specializations for each combination of cv, ref and noex (http://eel.is/c++draft/func.wrap.move#general-1). I didn't ask before, but how exactly does it affect users whether the implementation is macro-free or not?

libcxx/include/__functional/move_only_function_impl.h

244

library	name	size	buffer size
Abseil	absl::any_invocable	32	16
libstdc++	std::move_only_function	40	24
folly	folly::Function	64	48
LLVM	llvm::unique_function	32	24
HPX	hpx::move_only_function	40	24
MSVC STL	std::move_only_function	64	56

libcxx/test/std/utilities/function.objects/func.wrap/func.wrap.move/call/normal_const.pass.cpp

84

What are you talking about?

[ldionne]

libcxx/include/__functional/move_only_function.h

27

I agree with @philnik that this isn't conforming, although I think it's only pedantically non-conforming. In practice, I would expect that it works for most users.

Most importantly, it seems to me like the spec is too narrow here. What the standard *really* wants to say is that move_only_function can handle any combination of cv noexcept ref, but I don't think it was ever an explicit goal to say that it would be achieved via specialization specifically.

@jwakely @lichray Do you agree this is overspecified? If so, I could write a NB comment about it and we could relax the specification. Otherwise, I would argue that the current approach taken by @philnik is probably the right one, even though I agree it's kind of lame to be required by the Standard to use the X macro idiom.

libcxx/include/__functional/move_only_function_common.h

32

Let's call this in a way that it's move_only_function specific. Maybe _MoveOnlyFunctionVtable or whatever. Just std::_VTable is taking a pretty general name and assigning it specific meaning, which is weird.

libcxx/include/__functional/move_only_function_impl.h

100

If we do like llvm::unique_function (and I think we should), then we would have two sorts of vtables (pseudocode obviously):

struct _TrivialMoveOnlyFunctionVTable {
  auto __call_;
};

struct _NonTrivialMoveOnlyFunctionVTable : _TrivialMoveOnlyFunctionVTable {
  auto __destroy_;
  auto __move_;
};

We could use the pointer union trick to store whether the vtable is for a trivial type or not, which would replace your check for __destroy_ == nullptr in __reset(). IMO that would be slightly better.

We should implement a pointer union like type in libc++, that's something we should have had for a while. Give me a few days to get to it, and if I don't manage to I'll let you know and you can treat yourself.

159

How do you know that __func.__vtable_ is compatible with this function's vtable? And by that I mean precisely: how do you know that this function's vtable.__call_ (and __destroy_ and __move_) have exactly the same signature as __func.__vtable_'s? If they are not exactly the same, it's going to be UB to call them through pointers to different types.

From live review: you say this is definitely UB. First, please ensure to call out things like that explicitly. Second, I don't think we should perform this optimization unless we have some sort of blessing from the compiler (through a builtin or something like that).

244

Shooting from the hip, I would go for an implementation like llvm::unique_function, with 32 total size and 24 SBO. But it would be great to have more data about how these types are used. Unfortunately that's pretty difficult to get.

@EricWF Do you have any way to gather some data on your code base that would help us pick something here?

libcxx/include/__utility/small_buffer.h

38 ↗

(On Diff #467116)

I think we should allow storing non-trivially movable types in the SBO. This would require another "virtual" function to perform the move, but I think that's worth the trouble. Concretely, the size of the vtable isn't a huge issue.

46 ↗

(On Diff #467116)

IMO it would be nice if __small_buffer had a constructor that took an object. It would then encapsulate way more logic. That does mean that __small_buffer would have to know how to allocate and deallocate, but that can be done via template parameters. I think that would simplify the implementation of move_only_function quite a bit.

It would also make sense (?) if __small_buffer could be swapped, IMO. That also requires additional knowledge that should be parameterizable.

56 ↗

(On Diff #467116)

Do we need launder?

68 ↗

(On Diff #467116)

You'll need to guard this for exceptions once you store non-trivial types in the buffer.

81 ↗

(On Diff #467116)

This allows dropping the dependency on std::array, which doesn't add much. The _BufferSize is always > 0.

libcxx/test/libcxx/utilities/function.objects/func.wrap/func.wrap.move/call_disengaged.pass.cpp

1 ↗

(On Diff #467116)

Can you call this assert.<whatever> for consistency?

libcxx/test/std/utilities/function.objects/func.wrap/func.wrap.move/common.h

16–17

Please keep this in each file, even if that means duplicating it. Seeing a variable named called in the tests coming from seamingly nowhere is really weird IMO. And the duplication isn't much.

83

This is weird too - this has a different behavior depending on whether the function returns void or not. I understand you were maybe trying to reduce code duplication, but this is kind of spaghetti in return, IMO. Instead, consider always setting a bool to express that the function was called. The only difference will then become whether you're taking an argument or not and what you're returning, which seems better:

struct NonTrivial {
  NonTrivial() = default;
  NonTrivial(MoveCounter, bool* set_on_call) {}
  NonTrivial(std::initializer_list<int>&, MoveCounter, bool* set_on_call) {}
  NonTrivial(NonTrivial&&) noexcept(false) {} // todo
  ~NonTrivial() {}

  void operator()() const noexcept { *called_ = true; }
  int operator()(int i) const noexcept { *called_ = true; return i; }
};

Also, I would suggest not using a global here. It's not constexpr friendly and it's also not the best style, even though I understand it results in more "compact" code.

[ldionne]

libcxx/include/__functional/move_only_function_impl.h

62

https://wg21.link/p2548 copyable_function is making progress through the committee. We should discuss how these two types are going to interoperate and whether that should inform the representation we choose for move_only_function. In particular, it would be a nice QOI property to have move_only_function(copyable_function&&) just steal the guts of the copyable_function and make no allocation.

[philnik]

Address some more comments

libcxx/include/__functional/move_only_function_impl.h

71

We've got multiple threads discussing the this, so I'm closing some.

252

The question of using the SBO for non-trivially relocatable types is spanning multiple threads, so I'm closing this one.

libcxx/include/__utility/small_buffer.h

38 ↗

(On Diff #467116)

This would also make move_only_function not trivially relocatable anymore.

56 ↗

(On Diff #467116)

I think the answer is yes, because we might never have destroyed a trivial object that was in __buffer_ before, but I'm not familiar enough with the technicalities of object lifetime to be confident in answering the question.

[philnik]

Generate files

[philnik]

Try to fix CI

[philnik]

Next try

[ldionne]

libcxx/include/__functional/move_only_function_impl.h

40–55

Is there a reason why you allow these macros to *not* be defined? I would simply document the macros that this file needs in a comment and also have a #ifndef #error #endif for each of them.

62

I think the question here is basically whether we will want to have non-trivially-movable types in the SBO of copyable_function. If we do, then we won't be able to steal the guts, otherwise we will (assuming we use a SBO size that is no larger than that of move-only-function).

68

Please add documentation explaining the design choices we made and why. Basically a summary of this review. You'll thank yourself in a few months/years -- it's much much easier to do it right now while it's fresh.

77

This doesn't look super useful anymore.

102

104

I would call those __trivial_vtable and __nontrivial_vtable instead, since they are vtables and not vpointers.

105–108

111

_LIBCPP_HIDE_FROM_ABI here and wherever else you need it -- please make a pass.

131

You could use an immediately-invoked lambda here to avoid defining a separate function, since it's used exactly once.

libcxx/include/__utility/pointer_int_pair.h

1 ↗

(On Diff #479860)

This one in a separate patch too, please!

28–30 ↗

(On Diff #479860)

36 ↗

(On Diff #479860)

We should implement _PointerLikeTraits for __pointer_int_pair so that we can chain __pointer_int_pairs.

47 ↗

(On Diff #479860)

Let's require std::is_signed_v unless you want to have some fun making sure it works with signed types.

49 ↗

(On Diff #479860)

Can you please make sure that you have tests with a fancy pointer class?

58 ↗

(On Diff #479860)

Lets explicitly do __pointer_int_pair(__pointer_int_pair const&) = default, and so on for the move constructor and the assignment operators. It's nice documentation to state that it's trivially whatever-able just like one would expect.

59 ↗

(On Diff #479860)

constexpr? That will make it constinit-able.

62 ↗

(On Diff #479860)

I think this assertion is incorrect. Let's say you have something like this:

// int value: 15 aka 1111 binary
// number of bits free in the pointer: 4
// number of bits in use: 2
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 0000 // before you store anything into the pointer
xxxxxxxxxxxxxxxxxxxxxxxxxxxx11 1100 // after you store 15 into the pointer (it overflowed)
xxxxxxxxxxxxxxxxxxxxxxxxxxxx11 1111 // assuming you were using the 2 lower bits of the pointer to store something like int-value=3

Your assertion will pass but you still overflowed.

67 ↗

(On Diff #479860)

constexpr

72 ↗

(On Diff #479860)

This could be constexpr?

76–78 ↗

(On Diff #479860)

Looking at this, I am wondering whether we actually want to give it a pointer-like interface at all. This is a pair, not a pointer. Maybe we just want __first() and __second()? That would simplify the API.

And we should also make it work with structured bindings by making it a tuple-like class.

libcxx/include/__utility/small_buffer.h

1 ↗

(On Diff #479860)

Can you split this class off into its own patch?

32–33 ↗

(On Diff #479860)

That way we can decide from move_only_function the additional criteria for storing the type in the SBO.

Nevermind, this adds too much complexity in the move constructor for little benefit since the only user (for now) would have it be trivially relocatable anyways.

33 ↗

(On Diff #479860)

Please document the design of the class, in particular the fact that it only ever stores trivially movable objects in the buffer, which allows it to be trivially relocatable. Also mention that the users of the class are expected to manage the lifetime of the object inside the buffer.

38 ↗

(On Diff #467116)

So the tradeoff here is that either we accept non-trivially movable types in the SBO, or we only accept trivially movable types and then we can guarantee that the SBO is trivially relocatable.

I think this decision boils down to what's the most important use case for move_only_function. In live review, I said I thought it would be used mostly as a function parameter, however you rightly point out that we'll have function_ref for that. So for times where we don't want to actually store the move_only_function, we can just use function_ref and there's never an allocation.

So I think it would make sense to keep it trivially relocatable, as in the current patch.

56 ↗

(On Diff #467116)

I think we need to launder for this case:

struct Foo { };
struct Bar { };

buf.construct<Foo>(Foo{});
Foo* foo = buf.__get<Foo>();

use(buf);
Bar* bar = buf.__get<Bar>();


// somewhere else
void use(__small_buffer& buf) {
  buf.construct<Bar>(Bar{});
}

libcxx/test/libcxx/utilities/pointer_int_pair.pass.cpp

10

Maybe there should be more tests? This is a pretty fundamental utility.

Also please test chaining, etc.

libcxx/test/std/utilities/function.objects/func.wrap/func.wrap.move/assignment/nullptr.pass.cpp

71

return 0 everywhere please!

libcxx/test/support/type_algorithms.h

121

Maybe this should take an enum that you can bit-or to say which combinations you want?

[philnik]

Address some more comments

libcxx/include/__functional/move_only_function_impl.h

40–55

There are a two reasons:

1. It's a lot harder to define _LIBCPP_MOVE_ONLY_FUNCTION_INVOKE_QUALS
2. Having defaults for them allows editors to parse the file properly, instead of generating errors all over the place.

libcxx/include/__utility/pointer_int_pair.h

59 ↗

(On Diff #479860)

Doesn't apply anymore.

72 ↗

(On Diff #479860)

I guess so, but I don't think it makes a lot of sense to mark constexpr since nothing else is constexpr, or is there some benefit?

[ldionne]

libcxx/include/__functional/move_only_function_impl.h

74

I would add

// This is also a nice place to document how we're storing the vtable, i.e. explain that we're either pointing to a TrivialVTable or a non-trivial one based on the bool.
using _VTableStorage = __pointer_int_pair<const _TrivialVTable*, bool, bitfield_width(1)>;

104

Can you use a more descriptive name here?