How to implement a vtable for our custom type erasure type

We will see how to improve our erasure type and, more specifically, how to implement a vtable.

Here is the current list of our articles on this subject:

1. Macro-based type erasure
2. Macroless type erasure
3. this one: custom vtable for type erasure

Introduction

The problem with our current implementation is that each instance of our erased type embeds a list of function pointers. It means that if you have 1 behavior (e.g., draw), you will have one function pointer by instance; if you have 2 behaviors (e.g., open and close), you will have two function pointers. This means the more you add behaviors, the more memory your instance will take. How can we optimize it? Firstly, we need to observe something. If we have two instances containing the same type (e.g., a Circle), we observe that both instances have the same list of function pointers. It means that we can gather this list into another type.

How to implement a vtable

Basically, a vtable is a structure containing dynamic information about one given type. For example, it contains the name type, hierarchical information, and a pointer to the function for the given interface.

struct vtable_drawable {
    std::string name;
    HierarchicalInformation information;
    pointer_to_draw_function function_draw;
};

struct vtable_openable {
    std::string name;
    HierarchicalInformation information;
    pointer_to_open_function function_open;
    pointer_to_close_function function_close;
};

The interface type owns a pointer to the vtable, and the concrete type sets this pointer.

struct DrawableInterface {
    const vtable_drawable *vtable = nullptr;
};

struct Circle {
    DrawableInterface::vtable = vtable_drawable::construct_for<Circle>();
};

struct Rectangle {
    DrawableInterface::vtable = vtable_drawable::construct_for<Rectangle>();
};

In this article, we will focus mainly on the pointer to functions. We will not manage hierarchical information or type naming. Here are the basics of our custom vtable for the erased type.

template <typename... Methods> class vtable {
    std::tuple<MethodPtr<Methods>...> m_pointers;
};

The first idea is straightforward: our vtable object contains a list of pointers of functions retrieved through MethodPtr meta function seen in the prior article.

Now, we must see how to construct such vtable.

public:
template <typename T> static const vtable *construct_for() {
    static vtable vtable{MethodTrait<Methods>::template createInvoker<T>()...};
    return &vtable;
}

private:
  vtable(MethodPtr<Methods>... ptrs) : m_pointers{ptrs...} {}

We have the static template function construct_for. This function creates a static vtable and returns it by pointer. The construction is straightforward. We reuse the MethodTrait meta function to create the invokers.

Now, we need to be able to retrieve the function pointer from a given Method:

public:
template <typename Method> auto get_function_for() const noexcept {
    return std::get<index_in_list<Method, Methods...>()>(m_pointers);
}

We can then use it inside the erased type like this

template <typename... Methods> class erased : public Methods... {
private:
  std::any m_value;
  const vtable<Methods...> *m_vtable;

public:
  template <typename T>
  erased(T x) noexcept
      : m_value(std::move(x)),
        m_vtable{vtable<Methods...>::template construct_for<T>()} {}

  template <typename Method, typename... Args>
  decltype(auto) invoke(Method, Args &&...args) const {
    return m_vtable->template get_function_for<Method>()(
        m_value, std::forward<Args>(args)...);
  }

  template <typename Method, typename... Args>
  decltype(auto) invoke(Method, Args &&...args) {
    return m_vtable->template get_function_for<Method>()(
        m_value, std::forward<Args>(args)...);
  }
};

We need to call construct_for in the constructor and get_function_for inside the invoke functions. Et voilà!

Conclusion

To conclude, we saw how to improve the memory footprint of our erased type by implementing a little custom vtable. For those who want to follow the project, here is the erased repo using vtable.

In the future, maybe we can compare vtables based on function pointers or natural vtables generated from our compiler from the performance side!

Stay tuned!