Safe 'type erasure' without runtime memory allocation

[phdsch...@outlook.com]

Hi,

Many times we create a variable from a specific instantiation of a class template, but then need to assign a value from a different instantiation. This is the classic case of mixing custom allocators for standard containers with the default allocator. C++17 solves this through polymorphic memory resources. But it would be nice to have an easy solution available for programmers. Generally, the 'type erasure' pattern involves the use of:

1. boost/std any - which is inefficient because of the need to query the object or it forces use of the visitor pattern which scatters the logic all over the place.

2. A custom abstract interface - which leads to runtime memory allocation.

It would be nice if there was a mechanism by which the compiler could defer the determination of size till link time, and then choose a size that fits the largest size needed. In effect, it allows the programmer to control the tradeoff between higher static memory usage vs performance cost of memory allocation. Here, I would like to explore such an option, using type erasure of lambdas as a specific example.

template <typename …>
erasure function;


template <typename R, typename ...Args>
erasure function<R(Args…)>
{
    using _Me = function<R(Args…)>;


    // erasure implies these are pure virtual


    R operator()(Args…);


    template <typename Callable>
    _Me& operator=(Callable&&);    
};


template <typename Callable, typename R, typename ...Args>
class callable_container : public function<R(Args…)>
{
    // The implementation of erased templates is hidden from users. Users can only see the public erasure interface.


    R operator()(Args… args) override { /* Implement */ }

    // The set of concrete types that are passed to operator= anywhere in the program,
    // which are determined through template argument deduction,
    // determines the amount of memory to be allocated for _c.
    _Me& operator=(Callable&& c) override { /* Implement */ }


    Callable _c;
};

---------------------------------

In module A:

class A
{
public:


    template <typename Handler>
    void SetHandler(Handler&& h) { mHandler = std::forward<Handler>(h); }


    void Op()
    {
        // Do work
        auto ret = mHandler(1, 2);
    }


private:
Callable<int(int, int)> mHandler;
};


// As a first iteration, objects containing erased types can only be constructed in global scope.


A globalA;

---------------------------------

In module B:

class B
{
public:

    void f()
    {
        globalA.SetHandler([&i, f = f, &d](auto&&…) {});
        globalA.Op();
    }


private:


    float f;
    int i;
    double d;
};

---------------------------------

In module C:

class C
{
public:

    void f()
    {
        globalA.SetHandler([this](auto&&…) {});
        globalA.Op();
    }


private:


    float f;
    int i;
    double d;
};

The compiler defers the size determination of A to link time when all the information is available.

I would like the experts' opinion on this. Is this something that could be possible?

[Barry Revzin]

On Sunday, January 13, 2019 at 2:36:52 AM UTC-6, phdsch...@outlook.com wrote:

Hi,

Many times we create a variable from a specific instantiation of a class template, but then need to assign a value from a different instantiation. This is the classic case of mixing custom allocators for standard containers with the default allocator. C++17 solves this through polymorphic memory resources. But it would be nice to have an easy solution available for programmers. Generally, the 'type erasure' pattern involves the use of:

1. boost/std any - which is inefficient because of the need to query the object or it forces use of the visitor pattern which scatters the logic all over the place.

2. A custom abstract interface - which leads to runtime memory allocation.

It would be nice if there was a mechanism by which the compiler could defer the determination of size till link time, and then choose a size that fits the largest size needed. In effect, it allows the programmer to control the tradeoff between higher static memory usage vs performance cost of memory allocation. Here, I would like to explore such an option, using type erasure of lambdas as a specific example.

It's not clear to me what exactly you're looking for.  I didn't understand your example.

Have you seen, for instance, Dyno (https://github.com/ldionne/dyno/)? It allows you to provide a fixed, local storage that avoids allocation, or a custom-sized small buffer optimization. It's up to you to choose that storage though - to pick some fixed number, etc. Maybe that's good enough?

[Nicol Bolas]

As it currently stands, `sizeof` is a constant expression. And therefore, I ought to be able to instantiate a template with `sizeof(callable_container<Func>);`. What you want to do makes that impossible. So you now need a new category of types whose sizes are not constant expressions.

And such a property is viral. The size of `optional<callable_container<Func>>` is also not a constant expression. Nor is the size of anything that stores such a type. And so on.

Also, this poses a usability concern. What exactly happens if I instantiate `callable_container` with a gigantic type? That doesn't just affect the local instance of that object; it affects every instance everywhere. A seemingly localized change can have far-reaching impacts. And there's nothing I can actually do about it.

The nice thing about small storage optimization is that there is a strict upper-limit on how big it can get, thus ensuring that things can't get worse than a certain amount. What you're doing kind of breaks that, which can cause quite a lot of damage.

[Nicol Bolas]

Oh, and how exactly would this work across DLL/SO boundaries? Would `callable_container<Func>`, for the same `Func` type, have different sizes on different sides of the DLL/SO? After all, object sizes are static properties; they cannot change based on which libraries are loaded. So how does that work?

[Arthur O'Dwyer]

On Sunday, January 13, 2019 at 3:36:52 AM UTC-5, phdsch...@outlook.com wrote:

Hi,

Many times we create a variable from a specific instantiation of a class template, but then need to assign a value from a different instantiation. This is the classic case of mixing custom allocators for standard containers with the default allocator. C++17 solves this through polymorphic memory resources. But it would be nice to have an easy solution available for programmers. Generally, the 'type erasure' pattern involves the use of:

1. boost/std any - which is inefficient because of the need to query the object or it forces use of the visitor pattern which scatters the logic all over the place.

2. A custom abstract interface - which leads to runtime memory allocation.

It would be nice if there was a mechanism by which the compiler could [...]

I think your question/proposal is based on a misunderstanding.  Your "#1" and "#2" are actually the same thing, because boost::any and std::any (#1) are actually library types that work by using type erasure (#2).  And type erasure doesn't have to involve dynamic (heap) memory allocation. Heap allocation is needed only for two non-mutually-exclusive reasons which are really one reason:

- To indirectly store a wrapped object whose size is larger than the wrapper type's SBO capacity.

- To indirectly store a wrapped object which would otherwise violate some requirement of the wrapper, such as "trivially relocatable" or "nothrow move-constructible".

Furthermore, you make an analogy to std::pmr::polymorphic_allocator — a non-owning handle type. If you eliminate the requirement for ownership, then you eliminate the requirement to store a copy of the wrapped object, which usually eliminates both reasons above. So a non-owning type-erased wrapper generally doesn't allocate either.

For an example of a type-erasing, non-owning wrapper with no heap allocation, see std::function_ref<Sig>.

For an example of a type-erasing, owning wrapper with no heap allocation (but a maximum SBO capacity), see stdext::inplace_function<Sig, Cap, Align>.

----

As Nicol correctly states, you cannot have a type whose size is determined only at link-time.

However, for your use-case, all you have to do is pull the SBO size out into a compile-time macro:

    using HandlerType = stdext::inplace_function<int(int), HANDLER_SBO_SIZE>;

and then build your project with -DHANDLER_SBO_SIZE=16, -DHANDLER_SBO_SIZE=24, -DHANDLER_SBO_SIZE=32, -DHANDLER_SBO_SIZE=40,... until you find a value that lets the entire project compile cleanly. Then you can put that -D flag into your Makefile and you'll be good to go. (Until some maintainer adds an even larger lambda. Then you'll have to decide whether it's worth the performance penalty to increase HANDLER_SBO_SIZE, or whether you should just refactor the new lambda to be smaller.)

–Arthur

[phdsch...@outlook.com]

Hi Arthur,

Many thanks for your insightful reply. Having thought more about this, I really like the idea of a non-owning function wrapper. And I still insist on not having to perform the skulduggery of figuring out the right small buffer size. I want C++ code to be clean and expressive, reflecting the programmer's intent and automatically translating to efficient implementation. So, I would like to propose the following:

For class methods defined inside the class declaration, allow a way to declare method local variables as class member variables. Thus, they have storage within each object of the class, and can be safely passed as a type erased reference. The size of the class includes enough aligned space for storing these variables.

If you have the time, could you please take a look at this hypothetical code?

https://github.com/amir-ahmed-ansari/bits-n-pieces/blob/lambda-erasure/lambda-erasure.cpp

I know that the upcoming coroutines feature allows cleaner expression in this particular case, but this is only an example. There are many places where this could be useful. With libraries such as Boost.Hana and rxcpp, we are increasingly seeing instances were the actual type is not known in advance. All we have is the return value from a function call. Persisting such objects without the need for dynamic memory allocation should be possible.

Regards,

- Amir

[Arthur O'Dwyer]

On Tue, Jan 22, 2019 at 9:06 AM <phdsch...@outlook.com> wrote:

Hi Arthur,

Many thanks for your insightful reply. Having thought more about this, I really like the idea of a non-owning function wrapper. And I still insist on not having to perform the skulduggery of figuring out the right small buffer size. I want C++ code to be clean and expressive, reflecting the programmer's intent and automatically translating to efficient implementation. So, I would like to propose the following:

For class methods defined inside the class declaration, allow a way to declare method local variables as class member variables. Thus, they have storage within each object of the class, and can be safely passed as a type erased reference. The size of the class includes enough aligned space for storing these variables.

If you have the time, could you please take a look at this hypothetical code?

https://github.com/amir-ahmed-ansari/bits-n-pieces/blob/lambda-erasure/lambda-erasure.cpp

Okay, I've looked.

Have you looked at `function_ref`? It seems to be exactly what you're trying to do, but by looking at a real implementation you can find out how it's implemented.

 

I know that the upcoming coroutines feature allows cleaner expression in this particular case

No, it doesn't. Coroutines doesn't have anything to do with either type-erasure or vocabulary types for functions.

 

, but this is only an example. There are many places where this could be useful. With libraries such as Boost.Hana and rxcpp, we are increasingly seeing instances were the actual type is not known in advance. All we have is the return value from a function call. Persisting such objects without the need for dynamic memory allocation should be possible.

It is possible. Look at inplace_function or function_ref.

–Arthur