Chepurni Multimethods for Contemporary C++

Chepurni Multimethods for Contemporary C++

By Eugene Hutorny

Overload, 29(162):17-23, April 2021


Multimethods can be implemented in various ways. Eugene Hutorny showcases an approach using custom type identification and introspection.

Multiple dispatch, or multimethods, is a feature of some programming languages in which a function or method can be dynamically dispatched based on the run-time (dynamic) type or, in the more general case, some other attribute of more than one of its arguments [Wikipedia-1]. The need for such a feature appears, for instance, in software architectures where numerous classes of objects interact with each other in a way, specific for each pair. The C++ language did not directly provide such feature on the language level. It is possible to use std::visit in conjunction with std::variant to achieve multimethods (see [Filipek18], [Mertz18]). This article will consider an alternative approach, based on custom type identification and introspection facilities, letting us explore a variety of modern C++ techniques and providing flexibility

This study does not advocate a solution that would fit all use cases. Instead, it focuses on practical solutions for different use cases. The author encourages readers to experiment with the proposed solutions and tune or rework them for their particular needs.

Introduction

Existing solutions

Since a need for multiple dispatching is as old as the world of programming, quite a few solutions for C++ have been created (see [Bettini], [LeGoc14], [Loki], [Pirkelbauer07], [stfairy11], [Shopyrin06a], [Shopyrin06b], [Smith03a], [Smith03b]). However, none of them has a chepurni look (chepurni, Ukrainian чепурні – neat, clean, deft). Undoubtedly, chepurness is a subjective category. In the author’s opinion, a chepurni solution is simple to implement, easy to use, modern, non-intrusive and well structured. In other words, the complexity of a chepurni solution is related to the problem’s complexity, its use does not create extra dependencies, does not complicate the project maintenance, does not require changes to the existing designs, and every element of the solution addresses a single concern [Wikipedia-2] or bears a single responsibility [Wikipedia-3].

Problem overview

A dynamic, run-time dispatching requires knowledge about the class of the object. C++ facilitates Run-Time Type Information (RTTI), which is the number one choice for a project which already deploys it or is allowed to. However, the solution would not be chepurni if it did not offer an alternative for those projects where enabling RTTI would make them unviable.

Traditionally, multiple dispatching in C++ is implemented via a virtual method (the first dispatch) that performs next level dispatches with an if or switch statement, or with another virtual call to the other object. From the data modelling point of view, in many cases these methods do not look like natural parts of the classes implementing them, but rather as a workaround, caused by a missing language feature. They would look more organic if implemented as functions. However, in this study we will not impose a constraint to use only functions. Instead, we allow to use dispatchable methods along with functions.

Data models

In this study we will experiment with hierarchies of shapes and calculus expressions with simple inheritance (Listing 1).

namespace shapes {
  struct Shape {
    virtual ~Shape() {}
  };
  struct Rect : Shape {};
  struct Circle : Shape {};
  struct Square : Rect {};
}
namespace calculus {
  struct Expression {
    virtual ~Expression() {}
  };
  struct Constant : Expression {};
  struct Integer : Constant {};
  struct Float : Constant {};
}
			
Listing 1

Functions multidispatcher

Classes/templates, introduced in this section:

  • MULTIDISPATCHER

    The main template, implementing a dispatcher over a list of functions

  • ENTRY

    An auxiliary template for type identification and invocation

  • EXPECTED

    An auxiliary template for argument type matching

Let’s start with the calculus model and assume that it defines operations add, sub, implemented as template functions:

  template<class A, class B>
  Expression* add(const A&, const B&);
  template<class A, class B>
  Expression* sub(const A&, const B&);

This assumption greatly simplifies the start, and we will make it more complicated as we advance.

As it was mentioned earlier, our multimethod should discover actual argument types, select a proper function from the list of available according to the discovered types, and invoke the selected function. Here we stated three concerns. Let’s address them.

Function list

To define a list of function to dispatch we will use a variadic template with auto parameters, so it can be used as the following:

  multidispatcher<
    add<Integer, Integer>,
    add<Float, Integer>,
    add<Integer, Float>,
    add<Float, Float>>::dispatch(a,b);

For this kind of usage, the template may look like Listing 2.

template<auto Entry, auto ... Entries>
struct multidispatcher {
  template<class ... Arguments>
  static auto dispatch(Arguments& ... arguments) {
    if (entry<Entry>::matches(arguments...)) {
      return entry<Entry>::call(arguments...);
    }
    if constexpr (sizeof...(Entries)>0) {
      return multidispatcher<Entries...>
        ::dispatch(arguments...);
    }
  }
};
			
Listing 2

In the dispatch method we delegated type identification and invocation to another template entry, let’s write it as in Listing 3.

template<auto Method>
struct entry;
template<class Return, class ... Parameter,
    Return (*Function)(Parameter...)>
    struct entry<Function> {
  template<class ... Argument>
  static constexpr bool matches(const Argument& 
      ... argument) noexcept {
    return (expected<Parameter>::matches(argument)
       and ...);
  }
  template<class ... Argument>
  static Return call(Argument& ... argument)
      noexcept(noexcept(Function)) {
    return (*Function)((Parameter)(argument)...);
  }
};
			
Listing 3

Another template, expected, determines the actual argument’s type and whether it matches the expected type. With this design decision, the complete implementation is in Listing 4, which is available for experiments on this link: https://godbolt.org/z/oz585K

template<class Parameter>
struct expected {
  template<class Argument>
  static constexpr bool matches(const Argument&
      argument) noexcept {
    return typeid(Parameter) == typeid(argument);
  }
};
template<auto Method>
struct entry;
template<class Return, class ... Parameter, 
    Return (*Function)(Parameter...)>
    struct entry<Function> {
  template<class ... Argument>
  static constexpr bool matches(const Argument& ...
      argument) noexcept {
    return (expected<Parameter>::matches(argument)
      and ...);
  }
  template<class ... Argument>
  static Return call(Argument& ... argument)
      noexcept(noexcept(Function)) {
    return (*Function)((Parameter)(argument)...);
  }
};
template<auto Entry, auto ... Entries>
struct multidispatcher {
  template<class ... Arguments>
  static auto dispatch(Arguments& ... arguments) {
    if (entry<Entry>::matches(arguments...)) {
      return entry<Entry>::call(arguments...);
    }
    if constexpr (sizeof...(Entries)>0) {
      return multidispatcher<Entries...>
        ::dispatch(arguments...);
    }
  }
};
			
Listing 4

This implementation is very simple, although, comparing to the open methods, it has certain constraints:

  1. the length of the function list is limited by the compiler’s recursion depth
  2. the return type covariance is not supported
  3. the parameter covariance is not supported
  4. the first good candidate is selected instead of the best one
  5. virtual parameters not distinguished form regular, all treated as virtual

The second constraint restricts the users from using a function that returns a covariant result, for example one like this Float* sub(const Float&, const Float&). Also, this implementation does not do anything special about multiple inheritance. Such cases are handled the same way as simple inheritance – the first matching function is selected.

Third, fourth and fifth constraints limit the use cases. We will address them in the sections below. For now, we will focus on the first and second constraints.

Multimethods

Classes/templates/functions, introduced in this section

  • multimethod

    The main template, implementing a dispatcher over a list of functions or methods

  • resolve

    A helper function for resolving overloaded functions

  • class_hash()

    A function for generating unique class ID

  • is_virtual_parameter

    An auxiliary template for distinguishing between virtual and non-virtual parameters

Return type covariance

To support the return type covariance, we need to define the most generic return type for all used functions. To make it simple, we put this responsibility on the user and add this type as a parameter to our new template:

  template<typename ReturnType, auto ... Entries>
  struct multimethod;

As we are given the return type, we may use it for replacing the recursion with a folding expression (see Listing 5).

template<typename ReturnType, auto ... Entries>
struct multimethod {
  template<class ... Arguments>
  static auto dispatch(Arguments& ... arguments) {
    ReturnType value;
    if (((entry<Entries>::matches(arguments...)
        and ((value = entry<Entries>::
        call(arguments...)), true)) or ...))
      return value;
    else
      throw std::logic_error
        ("Missing dispatch entry");
  }
};
			
Listing 5

This modified example is available on this link: https://godbolt.org/z/rj5vvY

We have to admit that this approach requires the return type to be default constructible and to support move semantics. For our examples it makes no difference. For the other use cases, this may need taking into account.

A curious reader perhaps noticed that the last example on godbolt.org is not using overloaded functions for sub:

  Float* subf(const Float&, const Float&);
  Integer* subi(const Integer&, const Integer&);

This is a workaround for a C++ feature for the overloaded functions. To get an address of an overloaded function, one has to specify its full type: (Float* (*)(const Float&, const Float&))&sub. This inconvenient syntax could be a bit sugared with a template resolve:

  resolve<Float*, const Float&,
    const Float&>{}(&sub).

RTTI substitute

To work around the dependency on RTTI contributed with typeid, the model has to implement a custom type identification and introspection facilities (CTII). For instance, it could be a manually or automatically generated ID, assigned to every class. We may follow a simple autogenerating approach with a hash of __PRETTY_FUNCTION__:

  template<class Class>
  constexpr auto class_hash() noexcept {
    return
      hash(std::string_view(__PRETTY_FUNCTION__));
  }

Unfortunately, std::hash is not yet constexpr, thus we have to write out own hash function, (for example, one like given in [Hutorny]). Now we can easily assign unique IDs to our classes:

  static constexpr auto classid =
    class_hash<Rect>();

To access classid we define a template function classinfo:

  using class_info = size_t;
  template<class Class>
  class_info classinfo() noexcept {
    return Class::classid;
  }

For the dynamic type introspection, we define a virtual method (Listing 6).

//Shape
virtual bool instance_of
  (const class_info& expected) const noexcept {
  return classinfo<decltype(*this)>() ==
    expected;
}
//Rect, Circle
bool instance_of(const class_info& expected)
  const noexcept override {
  return classinfo<decltype(*this)>() == expected
    or Shape::instance_of(expected);
}
			
Listing 6

To avoid a dependency from the custom class class_info, we hide it behind a façade:

  //Shape
  template<class Expected>
  bool instanceof() const noexcept {
    return instance_of(classinfo<Expected>());
  }

Note, these methods are not overloaded. This will simplify our feature detecting template has_instanceof.

While we were using RTTI, we could ignore differences between virtual and regular parameters – typeid works for all types, and optimizer removes extraneous type checking for static types from the generated binary code. With CTII, however, we need to decide how to distinguish virtual parameters from non-virtual and how to compare the types for the latter. We may set the following rule: lvalue reference parameters to polymorphic types are virtual, the others are not:

  template<class Class>
  struct is_virtual_parameter {
    static constexpr bool value = 
      std::is_polymorphic_v<std::remove_reference_t
        <Class>> and
      std::is_reference_v<Class>;
  };

For the type check of not-virtual parameters we may use, for instance, is_same, or is_assignable. With this design of CTII, the adjusted template expected may look like Listing 7.

template<class Parameter>
struct expected {
  using parameter_type =
    std::remove_reference_t<std
    ::remove_cv_t<Parameter>>;
  template<class Argument>
  static constexpr bool matches(Argument&&
      argument) noexcept {
    if constexpr(has_instanceof<Argument>(0)) {
      return argument.template
        instanceof<parameter_type>();
    } else {
#if __cpp_rtti >= 199711
      return typeid(Parameter) == typeid(argument);
#else
      static_assert(
          not is_virtual_parameter_v<Parameter>,
          "No class info available");
      return is_assignable_parameter_v<Parameter,
          Argument>;
#endif
    }
  }
};
			
Listing 7

Supporting the methods

So far, our multimethod template only supports functions. Let’s extend it to accept methods as well. First what we need is to separate an object from the remaining arguments. We may, for example, define a new method in multimethod that accepts the objects as its first argument (Listing 8) and specialize template entry for methods (Listing 9).

// multimethod
template<class Target, class ... Arguments>
static auto call(Target& target,Arguments& ... arguments) {
  ReturnType value;
  if (((entry<Entries>::matches(target,
      arguments...)
    and ((value = entry<Entries>::call(target,
      arguments...)),true)) or ...))
    return value;
  else
    throw std::logic_error("Dispatcher failure");
}
			
Listing 8
template<class Target, class Return, 
    class ... Parameter, 
    Return (Target::*Method)(Parameter...)>
    struct entry<Method> {
  template<class Object, class ... Argument>
  static constexpr bool matches(Object& obj,
      Argument& ... argument) noexcept {
    return expected<Target>::matches(obj)
      and (expected<Parameter>::matches(argument)
        and ...);
  }
  template<class Object, class ... Argument>
  static Return call(Object& target, 
      Argument& ... argument) {
    return ((Target&)(target).*Method)
      ((Parameter&)(argument)...);
  }
};
			
Listing 9

Dealing with methods are somewhat more complicated than with functions – their signature may have specifier const. Thus, we will need two specializations of entry, and two methods call. With such implementation our multimethod accepts functions intermixed with methods. The sources for this design are available for experiments on this link: https://godbolt.org/z/ehEnnc

Parameter covariance

The CTII design with instance_of calling the base class also enabled parameter covariance. However, to get it working properly, the list should be ordered in a specific way: functions with more specific parameters should precede ones with more generic. It does not seem feasible to sort the list at compile time. Instead, one could add an order check which ensures that there are no functions below the current, accepting classes derived from the current ones. Computational complexity of such checking is estimated as O(kn²), where k is number of parameters, and n – number of functions in the list. It worth to note that this checking may significantly slowdown the compilation.

Multiple inheritance

Our CTII may also help with multiple inheritance – a class, inheriting multiple base classes should simply call instance_of of all its base classes. However, there might be cases, when the list ordering would not be sufficient for selecting the best match for certain combinations of parameter types.

Possible improvements

Maintaining a long list of functions may become too difficult for long function lists. To address this issue, one may group the list by the first parameter, like in the following example:

  groupdispatcher<
    group<Expression*,
      add<Integer, Float>,
      add<Integer, Integer>>,
    group<Expression*,
      add<Float, Integer>,
      add<Float, Float>>>::dispatch(a,b);

Each group then can be maintained in a separate header file. Also, one can use virtual methods for the first dispatch and multimethod – for the next dispatches.

Performance

This implementation of multimethod sequentially examines the functions till it finds a suitable one. Experiments shows 700 instructions in average for a list of 40 functions (please refer to perf.cpp on the github or to https://godbolt.org/z/1caGTs). With this implementation, a test run on x64 completes 10,000,000 dispatches in 6.4 sec. A table dispatching, expectingly, would show a better performance.

Table dispatching

Classes/templates/functions, introduced in this section

  • matrixdispatcher

    The main template, implementing a matrix dispatcher over a list of functions or methods

  • jumpvector

    An auxiliary template defining a row in the matrix

  • jumpmatrix

    An auxiliary template defining the dispatcher’s matrix

  • compute_score()

    A helper function, computing the score for a given pair of actual argument, formal parameter

  • make_score()

    A helper function, computing the score for a given function/method

  • find_best_match()

    A helper function, selecting the best scored function/method from the list

  • function_traits

    An auxiliary template, revealing characteristics of a function

  • func

    An internal template, generating wrapper functions

Assumptions

For a table dispatching, which is a matrix dispatch for two parameters, we need to fulfil some preconditions and solve some challenges:

  1. An effective table dispatching requires sequential class IDs, preferably with no gaps.
    • A manual ID assignment is error prone and, for some projects, may be too difficult in maintaining.
  2. A type-safe matrix may contain only functions of the same type, e.g. with identical signature.
    • A manual matrix filling is error prone, difficult even for small set of classes and practically impossible for large hierarchies.

For now, we just assume that sequential identification is made by the user, and address this concern in a chapter below. Also, as in previous designs, we assume that the functions are defined with the parameter types they actually operate on.

Matrix design

We have outlined the challenges, let’s find a design to solve them. As in earlier chapters, we start with a hierarchy of N classes that has K dispatchable functions defined on it. These functions we may list in our variadic template:

  matrixdispatcher<
    add<Integer, Integer>,
    add<Float, Integer>,
    add<Integer, Float>,
    add<Float, Float>>::dispatch(a,b);

As we assumed, class identification is made by the user:

  static constexpr auto classid = 1;
  virtual size_t classID() const 
  { return classid; }

If we require the same signature for all K functions, our template would not be able to distinguish them and pick the best one. Also, requiring the same signature we would transfer responsibility of down casting on the user. This seems to be too intrusive. So, we instead assume that the functions have different signatures with type of parameters they actually operate. To close the gap between different signatures on input and identical in the matrix we need some intermediate functions. With help of templates, we may delegate generating needed quantity of functions to the compiler and fill the matrix with pointers to them. They all should have the same signature, with the most common parameters of all dispatchable functions. Deriving such signature does not seem feasible, so we let the user to specify it as an input parameter FunctionType of our template. Also, we are not able to determine the actual number of classes, that we may get in our dispatch method. So, we will require this information to be a part of the input as well.

With this design, our matrix may look like in this example:

  FunctionType matrix[sizeA][sizeB]; 

However, filling this matrix in a constexpr manner is not handy, so we make it a bit more complex:

  std::array<std::array<FunctionType, sizeA>,
    sizeB> matrix;

Now, let’s find a way to fill it with function pointer. We need a constexpr filling to ensure that it will happen during compilation. C++ provides some means for filling constexpr arrays, in this design we use index_sequence. For instance, we may fill one row in our matrix with this line of code:

  std::array<FunctionType,N> { &Template<I> ... };

Where Template is a template function with class ID as a parameter, and I is an index sequence. Elaborating this design to some degree of completeness we get Listing 10.

template<template<size_t> class Template,
  size_t N>
class jumpvector : public 
  std::array<typename Template<0>::value_type,N>
{
public:
  using value_type =
    typename Template<0>::value_type;
  constexpr jumpvector() : jumpvector<Template,N>
    (std::make_index_sequence<N>()) {}
private:
  template<size_t ... I>
  constexpr jumpvector
    (std::index_sequence<I...>)
    : std::array<value_type,N> {
      &Template<I>::function ... } {}
};
			
Listing 10

Please note, in the code above we had to shift from a template function Template, to a template class Template with a static method function. This is because a template function would require signature, defined at this time. While with a static method we may defer the signature definition to a late stage.

Applying this design to all rows, we may fill the entire matrix (Listing 11).

template<template<size_t, size_t> class Template,
  size_t N, size_t M>
class jumpmatrix : public
  std::array<std::array<typename
  Template<0,0>::value_type, M>, N> {
public:
  using value_type = std::array
    <typename Template<0,0>::value_type, M>;
  constexpr jumpmatrix() : jumpmatrix<Template,
    N, M>(std::make_index_sequence<N>()) {}
private:
  template<size_t ... I>
  constexpr jumpmatrix(std::index_sequence<I...>)
    : std::array<value_type, N> { 
        jumpvector<reduce<Template,I>
          ::template type,M>{} ... } {}
};
			
Listing 11

This implementation sets up the requirements for the template class Template:

  template<size_t A, size_t B>
  struct func {
    static result_type function(parama_type& a,
      paramb_type& b);
  };

where result_type, parama_type, and paramb_type are parts, deduced from the FunctionType signature.

Scoring and selecting

For each specialization of our template func, we know exact class of each parameter – they are set by A and B. Thus, we can select the best candidate yet at compilation. To make this selection simple, we split it on two steps – scoring all functions with some criteria and selecting one with the highest score. The criteria should operate on actual and expected types. In C++17 we have standard templates is_same and is_base_of. For example, a class scoring template may be implemented as this:

  template<class Parameter, class Argument>
  constexpr ssize_t compute_score() noexcept {
    if( std::is_same_v< Argument, Parameter> ) 
      return 2;
    if( std::is_base_of_v<Parameter, Argument> )
      return 1;
    return 0;
  }

The function score then can be computed as a product of its parameter scores. This would work for simple hierarchies without multiple inheritance. More complex hierarchies may require a more advanced scoring design, based on a custom genesis inspection.

Now, we fill an array with the scores for every function from the list (Listing 12).

template<auto Entry>
static constexpr function_score make_score(size_t index) noexcept {
  using entry = function_traits<decltype(Entry)>;
  using paramA = typename entry::template nth_arg_type<0>;
  using paramB = typename entry::template nth_arg_type<1>;
  return function_score { 
    index, compute_score<paraьA,argA>() * compute_score<paramB,argB>() };
}
			
Listing 12

And select an element with the highest score:

  template<class ClassA, class ClassB,
    auto ... Entries>
  constexpr ssize_t find_best_match() noexcept {
    constexpr auto sc = function_scores<ClassA,
      ClassB, Entries...>{};
    return sc.highest();
  }

In a snippet of code above, function_traits is an auxiliary template for determining the function’s characteristics (see Listing 13).

template<typename Function>
struct function_traits;

template<class Return, class ... Parameter>
struct function_traits<Return (*)(Parameter...)> {
  using result_type = Return;
  static constexpr size_t parameter_count =
    sizeof...(Parameter);
  template<size_t N>
  using nth_arg_type = std::tuple_element_t<N,
    std::tuple<Parameter...>>;
};
			
Listing 13

Once we have a constexpr function index, we can get a function pointer from the list of input functions. To pass parameters to that function, we need a down cast, but since we already proved the proper relationship between the types, we may safely use static cast. Thereby, our function template becomes as in Listing 14.

template<size_t A, size_t B>
struct func {
  static result_type function(parama_type& a,
      paramb_type& b) {
    constexpr auto best = find_best_match<type<A>,
      type<B>, Entries...>();
    if constexpr(best >= 0) {
      constexpr auto f = get_entry<best,
        Entries...>();
      return (*f)( static_cast<type<A>>(a),
        static_cast<type<B>>(b));
    } else {
        LOGIC_ERROR("Dispatcher failure");
      }
    }
  }
};
			
Listing 14

Here we used another template type<B>, returning a type by its ID, e.g., implementing the reverse class-ID mapping. Since we have custom class IDs, this mapping has to be custom as well. The mapping and supply of the maximal class ID are related responsibilities, so we may delegate them to a single concept, further named domain. We have two input parameters and they may belong to different domains, thus we need two custom domains, which we will get as the parameters of our matrixdispatch. When both parameters share the same domain, the same domain class will be used in place of both domain parameters. All these design decisions can be implemented with the code in Listing 15.

template<typename FunctionType, class DomainA, class DomainB, auto ... Entries>
class matrixdispatch {
public:
  using entry = function_traits<FunctionType>;
  using result_type = typename entry::result_type;
  using parama_type = 
    typename entry::template nth_arg_type<0>;
  using paramb_type = 
    typename entry::template nth_arg_type<1>;
  constexpr matrixdispatch() noexcept {}
private:
  template<size_t A, size_t B>
  struct func {
    static result_type function(parama_type& a,
      paramb_type& b) {
      //See code snippet above
    }
  };
  static constexpr jumpmatrix<func, DomainA::size,
    DomainB::size> matrix {};  
public:
  static result_type dispatch(parama_type arg1,
      paramb_type arg2) {
    return matrix[arg1.classID()][arg2.classID()]
      (arg1, arg2);
  }
};
			
Listing 15

With some more work, we may improve this template to support methods, functions and combinations of them. Live example for this template is available on the following link: https://godbolt.org/z/Y89ThK

Performance

The matrix dispatch shows much better performance – 40 instructions (vs 700 in linear) for a list of 40 functions. However, it is also much more resource consuming for the compiler: O(pnk²) where p is a number of parameters, n is the number of functions, and k is the number of classes. Compilation of an example with 25 classes and 40 functions takes 20 sec more, when the matrixdispatch template is actually used. Also, the 15-times decrease of the instruction count per dispatch does not lead to the same decrease of the dispatch time. An experiment on x64 for 10,000,000 dispatches complete in 1.2 sec vs 6.4 sec for the linear dispatch.

Automatic identifier assignment

To make the class identifier assignment simple, we may craft a domain template (see Listing 16).

template<class ... Classes>
struct domain {
  static constexpr auto size = sizeof...(Classes);
  template<size_t ID>
  using type = std::tuple_element_t<ID,
    std::tuple<Classes...>>;
  template<class Class>
  static constexpr size_t id_of() noexcept {
    constexpr auto value = index_of<Class,
      Classes...>();
    return value;
  }
};
			
Listing 16

This template accepts a list of classes, and implements forward (id_of<MyClass>()) and reverse (type<ID>) mapping. This template does not require the listed classes to be completely defined, just forward declarations of them is sufficient.

To reduce the compilation complexity, we may exclude abstract classes from the matrix – instances of such classes cannot be created, and thus, they will never participate in the dispatch. However, to make this exclusion efficient, we need to assign abstract classes IDs from a lower diapason [0..M]. To address this challenge in a simple way we may assume that all abstract classes listed prior the concrete classes and provide a validation facility to check, whether this assumption is true.

Performance comparison

The results of performance tests are summarized in the table below. In this table, test std::visit denotes a reference implementation with std::visit, dispatching over variant-of-object arguments, std::visit* dispatching over variant-of-pointers, obtained via virtual calls to the objects. Wall time column lists timing for 10,000,000 dispatches over 40 functions/methods.

  Instructions per call Wall time (sec)
  G++-10 CLANG++-11 G++-10 CLANG++-11
std::visit 38 25 0.64 1.0
std::visit* 58 50 0.93 1.3
multimethod 750 702 5.8 6.4
matrixdispatch 54 47 0.88 1.2

Final notes

  1. gcc compiler for some examples, published on godbolt.org, generates code with static dispatching instead of dynamic. To make it truly dynamic, the test functions should be compiled in different compilatons units, as in examples on github.
  2. Examples from this study are also available on https://gist.github.com/hutorny:

    calculus multidispatcher

    calculus multifunction

    shapes multimethod

    matrix dispatch

  3. Ready to use templates are available as include-only library:https://github.com/hutorny/multimethods
  4. The sources of performance test are available in the same repository.

References

[Bettini] L. Bettini ‘Doublecpp – double dispatch in C++’ – http://doublecpp.sourceforge.net/

[Filipek18] B. Filipek, ‘How To Use std visit With Multiple Variants’ – https://www.bfilipek.com/2018/09/visit-variants.html

[Hutorny] E. Hutorny, ‘FNV-1b hash function with extra rotation’ – https://gist.github.com/hutorny/249c2c67255f842fae08e542f00131b5

[LeGoc14] Y. Le Goc and A. Donzé (2014) ‘EVL: A framework for multi-methods in C++’ – https://www.sciencedirect.com/science/article/pii/S0167642314003360

[Loki] Loki Library, Multiple dispatcher – https://sourceforge.net/projects/loki-lib/ Reference/MutiMethod.h

[Mertz18] A. Mertz, ‘Modern C++ Features – std::variant and std::visit’ – https://arne-mertz.de/2018/05/modern-c-features-stdvariant-and-stdvisit/

[Pirkelbauer07] P. Pirkelbauer, Y. Solodkyy, B. Stroustrup (2007) ‘Open Multi-Methods for C++’ – https://www.stroustrup.com/multimethods.pdf

[Shopyrin06a] D. Shopyrin, ‘MultiMethods in C++: Finding a complete solution’ – https://www.codeproject.com/Articles/7360/MultiMethods-in-C-Finding-a-complete-solution

[Shopyrin06b] D. Shopyrin, ‘Multimethods in C++ Using Recursive Deferred Dispatching’ – https://www.computer.org/csdl/magazine/so/2006/03/s3062/13rRUxBa5ve

[Smith03a] J. Smith ‘Draft proposal for adding Multimethods to C++’ – http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1529.html

[Smith03b] J. Smith ‘Multimethods’ – http://www.op59.net/accu-2003-multimethods.html

[stfairy11] stfairy ‘Multiple Dispatch and Double Dispatch’ – https://www.codeproject.com/Articles/242749/Multiple-Dispatch-and-Double-Dispatch

[Wikipedia-1] ‘Multiple dispatch’ – https://en.wikipedia.org/wiki/Multiple_dispatch

[Wikipedia-2] Separation of Concerns – https://en.wikipedia.org/wiki/Separation_of_concerns

[Wikipedia-3] Single-responsibility principle – https://en.wikipedia.org/wiki/Single-responsibility_principle

Eugene Hutorny is a software engineer from Ukraine. He started his professional career in his last year in the Kyiv Polytechnic Institute back in 1994. Since then, Eugene has participated in many different projects using various technology stacks, keeping a passionate interest in C++ through the years and advocating its wider use in the software engineering in general, and particularly in embedded systems.