Is there a way to return an abstraction from a function without using new (for performance reasons)

Question

For example I have some function pet_maker() that creates and returns a Cat or a Dog as a base Pet. I want to call this function many many times, and do something with the Pet returned.

Traditionally I would new the Cat or Dog in pet_maker() and return a pointer to it, however the new call is much slower than doing everything on the stack.

Is there a neat way anyone can think of to return as an abstraction without having to do the new every time the function is called, or is there some other way that I can quickly create and return abstractions?

Answer 1

Using new is pretty much inevitable if you want polymorphism. But the reason new works slowly is because it looks for free memory every time. What you could do is write your own operator new, which could, in theory, for example use pre-allocated memory chunks and be very fast.

This article covers many aspects of what you might need.

Answer 2

Each allocation is an overhead so you may get benefits by allocating whole arrays of objects rather than one object at a time.

You could use std::deque to achieve this:

class Pet { public: virtual ~Pet() {} virtual std::string talk() const = 0; };
class Cat: public Pet { std::string talk() const override { return "meow"; }};
class Dog: public Pet { std::string talk() const override { return "woof"; }};
class Pig: public Pet { std::string talk() const override { return "oink"; }};

class PetMaker
{
    // std::deque never re-allocates when adding
    // elements which is important when distributing
    // pointers to the elements
    std::deque<Cat> cats;
    std::deque<Dog> dogs;
    std::deque<Pig> pigs;

public:

    Pet* make()
    {
        switch(std::rand() % 3)
        {
            case 0:
                cats.emplace_back();
                return &cats.back();
            case 1:
                dogs.emplace_back();
                return &dogs.back();
        }
        pigs.emplace_back();
        return &pigs.back();
    }
};

int main()
{
    std::srand(std::time(0));

    PetMaker maker;

    std::vector<Pet*> pets;

    for(auto i = 0; i < 100; ++i)
        pets.push_back(maker.make());

    for(auto pet: pets)
        std::cout << pet->talk() << '\n';
}

The reason to use a std::deque is that it never reallocates its elements when you add new ones so the pointers that you distribute always remain valid until the PetMaker itself is deleted.

An added benefit to this over allocating objects individually is that they don't need to be deleted or placed in a smart pointer, the std::deque manages their lifetime.

Answer 3

Is there a neat way anyone can think of to return as an abstraction without having to do the new every time the function is called, or is there some other way that I can quickly create and return abstractions?

TL;DR: The function need not allocate if there is already sufficient memory to work with.

A simple way would be to create a smart pointer that is slightly different from its siblings: it would contain a buffer in which it would store the object. We can even make it non-nullable!

---

Long version:

I'll present the rough draft in reverse order, from the motivation to the tricky details:

class Pet {
public:
    virtual ~Pet() {}

    virtual void say() = 0;
};

class Cat: public Pet {
public:
    virtual void say() override { std::cout << "Miaou\n"; }
};

class Dog: public Pet {
public:
    virtual void say() override { std::cout << "Woof\n"; }
};

template <>
struct polymorphic_value_memory<Pet> {
    static size_t const capacity = sizeof(Dog);
    static size_t const alignment = alignof(Dog);
};

typedef polymorphic_value<Pet> any_pet;

any_pet pet_factory(std::string const& name) {
    if (name == "Cat") { return any_pet::build<Cat>(); }
    if (name == "Dog") { return any_pet::build<Dog>(); }

    throw std::runtime_error("Unknown pet name");
}

int main() {
    any_pet pet = pet_factory("Cat");
    pet->say();
    pet = pet_factory("Dog");
    pet->say();
    pet = pet_factory("Cat");
    pet->say();
}

The expected output:

Miaou
Woof
Miaou

which you can find here.

Note that it is required to specify the maximum size and alignment of the derived values that can be supported. No way around that.

Of course, we statically check whether the caller would attempt to build a value with an inappropriate type to avoid any unpleasantness.

The main disadvantage, of course, is that it must be at least as big (and aligned) as its largest variant, and all this must be predicted ahead of time. This is thus not a silver bullet, but performance-wise the absence of memory-allocation can rock.

---

How does it work? Using this high-level class (and the helper):

//  To be specialized for each base class:
//  - provide capacity member (size_t)
//  - provide alignment member (size_t)
template <typename> struct polymorphic_value_memory;

template <typename T,
          typename CA = CopyAssignableTag,
          typename CC = CopyConstructibleTag,
          typename MA = MoveAssignableTag,
          typename MC = MoveConstructibleTag>
class polymorphic_value {
    static size_t const capacity = polymorphic_value_memory<T>::capacity;
    static size_t const alignment = polymorphic_value_memory<T>::alignment;

    static bool const move_constructible = std::is_same<MC, MoveConstructibleTag>::value;
    static bool const move_assignable = std::is_same<MA, MoveAssignableTag>::value;
    static bool const copy_constructible = std::is_same<CC, CopyConstructibleTag>::value;
    static bool const copy_assignable = std::is_same<CA, CopyAssignableTag>::value;

    typedef typename std::aligned_storage<capacity, alignment>::type storage_type;

public:
    template <typename U, typename... Args>
    static polymorphic_value build(Args&&... args) {
        static_assert(
            sizeof(U) <= capacity,
            "Cannot host such a large type."
        );

        static_assert(
            alignof(U) <= alignment,
            "Cannot host such a largely aligned type."
        );

        polymorphic_value result{NoneTag{}};
        result.m_vtable = &build_vtable<T, U, MC, CC, MA, CA>();
        new (result.get_ptr()) U(std::forward<Args>(args)...);
        return result;
    }

    polymorphic_value(polymorphic_value&& other): m_vtable(other.m_vtable), m_storage() {
        static_assert(
            move_constructible,
            "Cannot move construct this value."
        );

        (*m_vtable->move_construct)(&other.m_storage, &m_storage);

        m_vtable = other.m_vtable;
    }

    polymorphic_value& operator=(polymorphic_value&& other) {
        static_assert(
            move_assignable || move_constructible,
            "Cannot move assign this value."
        );

        if (move_assignable && m_vtable == other.m_vtable)
        {
            (*m_vtable->move_assign)(&other.m_storage, &m_storage);
        }
        else
        {
            (*m_vtable->destroy)(&m_storage);

            m_vtable = other.m_vtable;
            (*m_vtable->move_construct)(&other.m_storage, &m_storage);
        }

        return *this;
    }

    polymorphic_value(polymorphic_value const& other): m_vtable(other.m_vtable), m_storage() {
        static_assert(
            copy_constructible,
            "Cannot copy construct this value."
        );

        (*m_vtable->copy_construct)(&other.m_storage, &m_storage);
    }

    polymorphic_value& operator=(polymorphic_value const& other) {
        static_assert(
            copy_assignable || (copy_constructible && move_constructible),
            "Cannot copy assign this value."
        );

        if (copy_assignable && m_vtable == other.m_vtable)
        {
            (*m_vtable->copy_assign)(&other.m_storage, &m_storage);
            return *this;
        }

        //  Exception safety
        storage_type tmp;
        (*other.m_vtable->copy_construct)(&other.m_storage, &tmp);

        if (move_assignable && m_vtable == other.m_vtable)
        {
            (*m_vtable->move_assign)(&tmp, &m_storage);
        }
        else
        {
            (*m_vtable->destroy)(&m_storage);

            m_vtable = other.m_vtable;
            (*m_vtable->move_construct)(&tmp, &m_storage);
        }

        return *this;
    }

    ~polymorphic_value() { (*m_vtable->destroy)(&m_storage); }

    T& get() { return *this->get_ptr(); }
    T const& get() const { return *this->get_ptr(); }

    T* operator->() { return this->get_ptr(); }
    T const* operator->() const { return this->get_ptr(); }

    T& operator*() { return this->get(); }
    T const& operator*() const { return this->get(); }

private:
    polymorphic_value(NoneTag): m_vtable(0), m_storage() {}

    T* get_ptr() { return reinterpret_cast<T*>(&m_storage); }
    T const* get_ptr() const { return reinterpret_cast<T const*>(&m_storage); }

    polymorphic_value_vtable const* m_vtable;
    storage_type m_storage;
}; // class polymorphic_value

Essentially, this is just like any STL container. The bulk of the complexity is in redefining the construction, move, copy and destruction. It's otherwise quite simple.

There are two points of note:

1. I use a tag-based approach to handling capabilities:

   • for example, a copy constructor is only available if the CopyConstructibleTag is passed
   • if the CopyConstructibleTag is passed, all types passed to build must be copy constructible

2. Some operations are provided even if the objects do not have the capability, as long as some alternative way of providing them exist

Obviously, all methods preserve the invariant that the polymorphic_value is never empty.

There is also a tricky detail related to assignments: assignment is only well-defined if both objects are of the same dynamic type, which we check with the m_vtable == other.m_vtable checks.

---

For completeness, the missing pieces used to power up this class:

//
//  VTable, with nullable methods for run-time detection of capabilities
//
struct NoneTag {};
struct MoveConstructibleTag {};
struct CopyConstructibleTag {};
struct MoveAssignableTag {};
struct CopyAssignableTag {};

struct polymorphic_value_vtable {
    typedef void (*move_construct_type)(void* src, void* dst);
    typedef void (*copy_construct_type)(void const* src, void* dst);
    typedef void (*move_assign_type)(void* src, void* dst);
    typedef void (*copy_assign_type)(void const* src, void* dst);
    typedef void (*destroy_type)(void* dst);

    move_construct_type move_construct;
    copy_construct_type copy_construct;
    move_assign_type move_assign;
    copy_assign_type copy_assign;
    destroy_type destroy;
};


template <typename Base, typename Derived>
void core_move_construct_function(void* src, void* dst) {
    Derived* derived = reinterpret_cast<Derived*>(src);
    new (reinterpret_cast<Base*>(dst)) Derived(std::move(*derived));
} // core_move_construct_function

template <typename Base, typename Derived>
void core_copy_construct_function(void const* src, void* dst) {
    Derived const* derived = reinterpret_cast<Derived const*>(src);
    new (reinterpret_cast<Base*>(dst)) Derived(*derived);
} // core_copy_construct_function

template <typename Derived>
void core_move_assign_function(void* src, void* dst) {
    Derived* source = reinterpret_cast<Derived*>(src);
    Derived* destination = reinterpret_cast<Derived*>(dst);
    *destination = std::move(*source);
} // core_move_assign_function

template <typename Derived>
void core_copy_assign_function(void const* src, void* dst) {
    Derived const* source = reinterpret_cast<Derived const*>(src);
    Derived* destination = reinterpret_cast<Derived*>(dst);
    *destination = *source;
} // core_copy_assign_function

template <typename Derived>
void core_destroy_function(void* dst) {
    Derived* d = reinterpret_cast<Derived*>(dst);
    d->~Derived();
} // core_destroy_function


template <typename Tag, typename Base, typename Derived>
typename std::enable_if<
    std::is_same<Tag, MoveConstructibleTag>::value,
    polymorphic_value_vtable::move_construct_type
>::type 
build_move_construct_function()
{
    return &core_move_construct_function<Base, Derived>;
} // build_move_construct_function

template <typename Tag, typename Base, typename Derived>
typename std::enable_if<
    std::is_same<Tag, CopyConstructibleTag>::value,
    polymorphic_value_vtable::copy_construct_type
>::type 
build_copy_construct_function()
{
    return &core_copy_construct_function<Base, Derived>;
} // build_copy_construct_function

template <typename Tag, typename Derived>
typename std::enable_if<
    std::is_same<Tag, MoveAssignableTag>::value,
    polymorphic_value_vtable::move_assign_type
>::type 
build_move_assign_function()
{
    return &core_move_assign_function<Derived>;
} // build_move_assign_function

template <typename Tag, typename Derived>
typename std::enable_if<
    std::is_same<Tag, CopyAssignableTag>::value,
    polymorphic_value_vtable::copy_construct_type
>::type 
build_copy_assign_function()
{
    return &core_copy_assign_function<Derived>;
} // build_copy_assign_function


template <typename Base, typename Derived,
          typename MC, typename CC,
          typename MA, typename CA>
polymorphic_value_vtable const& build_vtable() {
    static polymorphic_value_vtable const V = {
        build_move_construct_function<MC, Base, Derived>(),
        build_copy_construct_function<CC, Base, Derived>(),
        build_move_assign_function<MA, Derived>(),
        build_copy_assign_function<CA, Derived>(),
        &core_destroy_function<Derived>
    };
    return V;
} // build_vtable

The one trick I use here is to let the user configure whether the types he will use in this container can be move constructed, move assigned, ... via capability tags. A number of operations are keyed on these tags and will either be disabled or less efficient if the requested capability