P0288R9 `move_only_function`

[StephanTLavavej]

P0288R9 move_only_function

Feature-test macro:
__cpp_lib_move_only_function

[AlexGuteniev]

I think while it could be possible to tune the existing function to handle move-only implementation, it is better to have a new better implementation. Better means it should at least address #969, also I have some additional thoughts on a better function.

[AlexGuteniev]

EDIT: Never mind, can be implemented as usual template under as-if rule. function is also defined in terms of specialization in standard

---

Unlike good old function<T>, which is ideed templated by T, the move_only_function<T> is actually the following:

template <class... S>
class move_only_function; // not defined

template <class R, class... ArgTypes>
class move_only_function<R(ArgTypes...) cv ref noexcept(noex)> {
...
}

where cv ref noexcept(noex) is every sensible combination of qualifiers.
They make twelve possibilities:

(1.1) — cv is either const or empty.
(1.2) — ref is either &, &&, or empty.
(1.3) — noex is either true or false.

This leads to excess copypasta. Sure something can be moved out to a private base class, but even in this case using declarations alone will make move_only_function specialization have quite large definition.

How should this be handled? See these options:

1. Preprocessor only
2. Preprocessor + multi-included "template" header
3. A script that generates the content
4. Manual copypasting

[AlexGuteniev]

Here is a POC of an implementation with fake vTable.
For each target type in creates unique instance of constexpr structure that consists of function pointers.
Advantages of this approach are:

• Ease of implementation of optimization similar to <functional>: std::function: avoid one indirection for SFO #969
• Avoiding RTTI overhead (may be significant, as there are a lot of callable types)
• Avoiding checks for bad_function_call, instead making it a special vTable pointer value
  • Check for null can be performed by comparing vTable pointer against special vTable pointer value
  • Alternatively bool _IsEmpty; may be embedded into vTable
• Avoiding some code bloat. without relying on linker, by the compiler (again, may be significant)
  • Moving large function shares implementation between types
  • Moving small function could share implementation: when use of memcpy is possible, it can be templated by size
  • Destroying could share implementation for trivially destructible types
  • Functions that becomes non-template this way (like _Function_move_large) may go to sources (import library)

Such implementation may be a good idea for vNext std::function. For now I'm proposing to do this for move_only_function.

POC of an implementation

#include <cstdlib>
#include <cstdio>
#include <cstddef>
#include <stdexcept>
#include <type_traits>

template<typename R, typename ...Args>
struct _Move_only_function_impl {
    using _Invoke_t = R(*)(uintptr_t* self, Args...);
    using _Move_t = void(*)(uintptr_t* self, uintptr_t* src);
    using _Destroy_t = void(*)(uintptr_t* self);

    _Invoke_t _Invoke;
    _Move_t _Move;
    _Destroy_t _Destroy;
};

template<typename R, typename ...Args>
R _Function_throw_bad_call(uintptr_t* self, Args...) {
    throw std::runtime_error("bad function call");
}

inline void _Function_Noop_move(uintptr_t*, uintptr_t*) noexcept {}
inline void _Function_Noop_destroy(uintptr_t*) noexcept {}

template<typename R, typename ...Args>
constexpr _Move_only_function_impl<R, Args...> _Null_function = {
    _Function_throw_bad_call<R, Args...>,
    _Function_Noop_move,
    _Function_Noop_destroy,
};

template<typename F, typename R, typename ...Args>
R _Function_invoke_small(uintptr_t* self, Args... args) {
    return reinterpret_cast<F&>(*self)(std::forward<Args>(args)...);
}

template<typename F, typename R, typename ...Args>
R _Function_invoke_large(uintptr_t* self, Args... args) {
    return (*reinterpret_cast<F*>(*self))(std::forward<Args>(args)...);
}

template<typename F>
void _Function_move_small(uintptr_t* self, uintptr_t* src) {
    new (reinterpret_cast<void*>(self)) F(std::move(*reinterpret_cast<F*>(src)));
    reinterpret_cast<F&>(*src).~F();
}

inline void _Function_move_large(uintptr_t* self, uintptr_t* src) {
    *self = *src;
}

template<typename F>
void _Function_destroy_small(uintptr_t* self) {
    reinterpret_cast<F&>(*self).~F();
}

template<typename F>
void _Function_destroy_large(uintptr_t* self) {
    delete reinterpret_cast<F*>(*self);
}


template<class R, class... Args>
class move_only_function {
public:
    using result_type = R;

    move_only_function() noexcept : _Impl(&_Null_function<R, Args...>) {}
    move_only_function(nullptr_t) noexcept : _Impl(&_Null_function<R, Args...>) {}

    move_only_function(move_only_function&& _Other) : _Impl(_Other._Impl) {
        _Impl->_Move(_Data, _Other._Data);
        _Other._Impl = &_Null_function<R, Args...>;
    }
    
    template<class F> 
    move_only_function(F&& f) : _Impl(_Create_impl_ptr<F, R, Args...>()) {
        if constexpr (_Large_function_engaged<F>()) {
            reinterpret_cast<void*&>(_Data[0]) = new F(std::move(f));
        }
        else {
            new (reinterpret_cast<void*>(_Data)) F(std::move(f));
        }
    }

    ~move_only_function() {
        _Impl->_Destroy(_Data);
    }

    R operator()(Args... args) {
        return _Impl->_Invoke(_Data, std::forward<Args>(args)...);
    }

private:
    using _Impl_t = _Move_only_function_impl<R, Args...>;

    alignas(max_align_t) uintptr_t _Data[4];
    const _Impl_t* _Impl;

    template<class F>
    static constexpr bool _Large_function_engaged() {
        return sizeof(F) > sizeof(_Data) ||
               !std::is_nothrow_move_constructible_v<F>;
    }

    template<class F, class R, class... Args>
    static constexpr _Impl_t _Create_impl() {
        _Impl_t _Impl{};
        if constexpr (_Large_function_engaged<F>()) {
            _Impl._Invoke  = _Function_invoke_large<F, R, Args...>;
            _Impl._Move    = _Function_move_large;
            _Impl._Destroy = _Function_destroy_large<F>;
        }
        else {
            _Impl._Invoke  = _Function_invoke_small<F, R, Args...>;
            _Impl._Move    = _Function_move_small<F>; // TODO: separate implementation for memcpy-movable
            _Impl._Destroy = _Function_destroy_small<F>; // TODO: separate implementation for trivially-destructible
        }
        return _Impl;
    }

    template<class F, class R, class... Args>
    static constexpr const _Impl_t* _Create_impl_ptr() {
        static constexpr _Impl_t _Impl = _Create_impl<F, R, Args...>();
        return &_Impl;
    }
};

struct small {
    char data;

    small(char v){
        data = v;
        printf("created %d\n", data);
    }

    small(small&& other) noexcept
    {
        data = other.data;
        printf("moved %d\n", data);
    }

    ~small()
    {
        printf("deleted %d\n", data);
    }

    int operator()(int a, int b) {
        printf("call %d: %d, %d\n", data, a, b);
        return a + b;
    }
};

struct large {
    char data;
    char more_data[100];

    large(char v) {
        data = v;
        printf("created %d\n", data);
    }

    large(large&& other) noexcept
    {
        data = other.data;
        printf("moved %d\n", data);
    }

    ~large()
    {
        printf("deleted %d\n", data);
    }

    int operator()(int a, int b) {
        printf("call %d: %d, %d\n", data, a, b);
        return a - b;
    }
};

int __cdecl main()
{
    {
        move_only_function<int, int, int> f1(small{ 11 });
        int i1 = f1(1, 2);
        move_only_function<int, int, int> f2(std::move(f1));
        int i2 = f2(3, 4);
    }

    {
        move_only_function<int, int, int> f3(large{ 22 });
        int i3 = f3(1, 2);
        move_only_function<int, int, int> f4(std::move(f3));
        int i4 = f4(3, 4);
    }

    move_only_function<int, int, int> f5;
    try
    {
        int i5 = f5(5, 6);
    }
    catch (std::exception&)
    {
    }
}

[MikeGitb]

Just wondering: Have you considered using the lower one or maybe two bits in the _Impl pointer (a.k.a the fake vTable pointer) to indicate if the current instance of a move_only_function is trivially moveable and/or trivially destructible and then switch on those bits inside the move constructor and destructor. That way, you wouldn't need to go through the function pointer for a lot of moves and destruction scenarious (large callable or small but trivially moveable/destructible callable like function pointers).

I've no data to indicate which one would perform better under which circumstances, so please just read this as a question out of curiosity, not a recommendation to do it.

[MikeGitb]

Same question about special casing a default constructed/moved from move_only_function (i.e. assigning nullptr to _Impl)

[AlexGuteniev]

Just wondering: Have you considered using the lower one or maybe two bits in the _Impl pointer (a.k.a the fake vTable pointer) to indicate if the current instance of a move_only_function is trivially moveable and/or trivially destructible and then switch on those bits inside the move constructor and destructor. That way, you wouldn't need to go through the function pointer for a lot of moves and destruction scenarious (large callable or small but trivially moveable/destructible callable like function pointers).

I was actually considering embedding those bools into the "fake vTable". This way don't need to restore pointer by mask. But I'll look into this too. Just will finish more obvious things first.

Sure bits would not only avoid the call itself, but also reaching "vTable"

Making extra check will cause having extra branch before the call. So larger code and more branches. But maybe this will be better. Very likely better with /guard:cf option.

[AlexGuteniev]

@MikeGitb, after giving this more thoughts, I think probably it could be a good option to use bits, as you suggested. Specifically:

• Bit for trivial destructor
• Bit for trivial move

With trivial move bit set, will memcpy exactly two pointers. This will cover:

• Large functions
• Small functions with size of a pointer or less (this includes plain pointers and trivial lambdas)
• Empty functions (will unnecessarily copy one pointer, but given alignas(8) and SSE2 as baseline, this will cause no performance difference whether copy one pointers or two)
  • Need to make sure for empty function second pointer is initialized to zero: to avoid reading initializing memory that may be flagged by address sanitizing tools, and to make store of empty function double-pointer store, and enable load-to-store forwarding
  • Alternatively, consider copying as two pointer assignment, not memcpy to prevent SSE2 copying

[AlexGuteniev]

@MikeGitb, I've experimented with optimizations:

1. always call by pointer
2. check pointer bits (before reaching fake vtable)
3. check vtable entries for null

2 and 3 are somewhat better than 1. Still there's not enough evidence to tell if 2 or 3 is better.

So I'll keep option 3 as it is simpler. You can try a PR after my PR is hopefully submitted if you think 2 is better, or can suggest other improvements (I think it is free to change, as no ABI stability is promised for C++23).