How can I design storage that conforms to the standard's implementation of std::any?

Question

The standard working draft (n4582, 20.6.3, p.552) states the following suggestion for implementations of std::any:

Implementations should avoid the use of dynamically allocated memory for a small contained object. [ Example: where the object constructed is holding only an int. —end example ] Such small-object optimization shall only be applied to types T for which is_nothrow_move_constructible_v is true.

As far as I know, std::any can be easily implemented through type erasure/virtual functions and dynamically allocated memory.

How can std::any avoid dynamic allocation and still destroy such values if no compile time information is known at the time of destruction; how would a solution that follows the standard's suggestion be designed?

---

If anyone wants to see a possible implementation of the non-dynamic part, I've posted one on Code Review: https://codereview.stackexchange.com/questions/128011/an-implementation-of-a-static-any-type

It's a little too long for an answer here. It's based on the suggestions of Kerrek SB on the comments below.

Answer 1

Typically, any takes anything and dynamically allocates a new object from it:

struct any {
    placeholder* place;

    template <class T>
    any(T const& value) {
        place = new holder<T>(value);
    }

    ~any() {
        delete place;
    }
};

We use the fact that placeholder is polymorphic to handle all of our operations - destruction, cast, etc. But now we want to avoid allocation, which means we avoid all the nice things that polymorphism gives us - and need to reimplement them. To start with, we'll have some union:

union Storage {
    placeholder* ptr;
    std::aligned_storage_t<sizeof(ptr), sizeof(ptr)> buffer;
};

where we have some template <class T> is_small_object { ... } to decide whether or not we're doing ptr = new holder<T>(value) or new (&buffer) T(value). But construction isn't the only thing we have to do - we also have to do destruction and type info retrieval, which look different depending on which case we're in. Either we're doing delete ptr or we're doing static_cast<T*>(&buffer)->~T();, the latter of which depends on keeping track of T!

So we introduce our own vtable-like thing. Our any will then hold onto:

enum Op { OP_DESTROY, OP_TYPE_INFO };
void (*vtable)(Op, Storage&, const std::type_info* );
Storage storage;

You could instead create a new function pointer for each op, but there are probably several other ops that I'm missing here (e.g. OP_CLONE, which might call for changing the passed-in argument to be a union...) and you don't want to just bloat your any size with a bunch of function pointers. This way we lose a tiny bit of performance in exchange for a big difference in size.

On construction, we then populate both the storage and the vtable:

template <class T,
          class dT = std::decay_t<T>,
          class V = VTable<dT>,
          class = std::enable_if_t<!std::is_same<dT, any>::value>>
any(T&& value)
: vtable(V::vtable)
, storage(V::create(std::forward<T>(value))
{ }

where our VTable types are something like:

template <class T>
struct PolymorphicVTable {
    template <class U>
    static Storage create(U&& value) {
        Storage s;
        s.ptr = new holder<T>(std::forward<U>(value));
        return s;
    }

    static void vtable(Op op, Storage& storage, const std::type_info* ti) {
        placeholder* p = storage.ptr;

        switch (op) {
        case OP_TYPE_INFO:
            ti = &typeid(T);
            break;
        case OP_DESTROY:
            delete p;
            break;
        }
    }
};

template <class T>
struct InternalVTable {
    template <class U>
    static Storage create(U&& value) {
        Storage s;
        new (&s.buffer) T(std::forward<U>(value));
        return s;
    }

    static void vtable(Op op, Storage& storage, const std::type_info* ti) {
        auto p = static_cast<T*>(&storage.buffer);

        switch (op) {
        case OP_TYPE_INFO:
            ti = &typeid(T);
            break;
        case OP_DESTROY:
            p->~T();
            break;
        }
    }
};

template <class T>
using VTable = std::conditional_t<sizeof(T) <= 8 && std::is_nothrow_move_constructible<T>::value,
                   InternalVTable<T>,
                   PolymorphicVTable<T>>;

and then we just use that vtable to implement our various operations. Like:

~any() {
    vtable(OP_DESTROY, storage, nullptr);
}