Fast RTTI in C++ for a class hierarchy

c++
design
performance

An example that shows compile time type id generation for a performant runtime type inference.

Author

Bimal Gaudel

Published

April 28, 2022

The Problem

Let’s write a polymorphic operator base class for the arithmetic operators in a basic calculator.

// polymorphic operator base class
class Operator {
 protected:
  Operator() = default;

 public:
  virtual ~Operator() = default;
};

The calculator supports the four basic operations. Let’s derive an operator type for each from the base.

class Plus final : public Operator {};

class Minus final : public Operator {};

class Times final : public Operator {};

class Divide final : public Operator {};

Here’s an incomplete evaluation function.

//
// requires C++20
// required headers
//   <stdexcept>
//   <type_traits>
//   <vector>
//
template <typename Elem>
requires std::is_arithmetic_v<Elem> Elem
evaluate(std::vector<Elem> const& elems,
         std::vector<Operator const*> const& ops) {
  auto e = elems.empty() ? Elem{} : elems[0];
  for (size_t i = 1,                        // iter elems
       j = 0;                               // iter ops
       i < elems.size() && j < ops.size();  //
       ++i, ++j) {
    auto op = ops[j];                             // [0]
    if (/* op points to Plus type */) {           // [1]
      e += elems[i];
    } else if (/* op points to Minus type */) {   // [2]
      e -= elems[i];
    } else if (/* op points to Times type */) {   // [3]
      e *= elems[i];
    } else if (/* op points to Divide type */) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
  }
  return e;
}

Now we need to determine the derived type of an Operator at the lines labelled 1 through 4.

Why not use an overloaded evaluation function?

Before reaching for RTTI, why not just make evaluation a virtual function on the operator hierarchy?

template <typename E>
class Operator {
  //...
  public:
  virtual E evaluate(E lhs, E rhs) const = 0;
  //...
};

template <typename E>
class Plus final : public Operator<E> {
  private:
  E evaluate(E lhs, E rhs) const override {
    return lhs + rhs;
  }
}

// ...
// ...

That is fine for simple cases. But adding more functionality to the base class means modifying the base class and every derived class.

Alternatively, you could add a second base class for the new functionality and derive new operator classes from both it and the corresponding Plus, Minus, Times, or Divide. Either way, it’s cumbersome.

C++ provides two RTTI features: dynamic_cast (available because the base class is polymorphic) and the typeid operator.

Using dynamic_cast

// ...
// for ( ... ) {
// ...
    auto op = ops[j];                              // [0]
    if (dynamic_cast<Plus const*>(op)) {           // [1]
      e += elems[i];
    } else if (dynamic_cast<Minus const*>(op)) {   // [2]
      e -= elems[i];
    } else if (dynamic_cast<Times const*>(op)) {   // [3]
      e *= elems[i];
    } else if (dynamic_cast<Divide const*>(op)) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
// ...
// }
// ...

Problems with dynamic_cast

Using typeid

// required header: <typeinfo>

// ...
// for ( ... ) {
// ...
    auto const& ti = typeid(*ops[j]);   // [0]
    if (typeid(Plus) == ti) {           // [1]
      e += elems[i];
    } else if (typeid(Minus) == ti) {   // [2]
      e -= elems[i];
    } else if (typeid(Times) == ti) {   // [3]
      e *= elems[i];
    } else if (typeid(Divide) == ti) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
// ...
// }
// ...

Problems with typeid

typeid comparison can still be slow: operator==() on the returned std::type_info is implementation defined and might use string comparison. We can do better. The idiom in the next section also works with RTTI disabled at compile time, whereas typeid needs it enabled.

An example evaluation

// C++20

#include <iostream>
#include <vector>
#include <stdexcept>
#include <type_traits>
#include <typeinfo> // if using typeid

// <<Operator base class definition from above>>
// <<Operator derived class definitions from above>>
// <<evaluate function definition from above>>

int main() {
  auto const Op = Plus{};
  auto const Om = Minus{};
  auto const Ot = Times{};
  auto const Od = Divide{};

  // evaluating ((((2 * 3) + 6) - 2) / 2)
  auto const nums = std::vector<double>{2, 3, 6, 2, 2};
  auto const ops = std::vector<Operator const*>{&Ot, &Op, &Om, &Od};

  std::cout << "result: " << evaluate(nums, ops) << std::endl;  // result: 5
  return 0;
}

Fast RTTI

Here’s the full implementation, with a runnable example:

// C++20
#include <atomic>
#include <iostream>
#include <stdexcept>
#include <type_traits>
#include <vector>

// abstract Operator class
struct Operator {
 public:
  using type_id_t = int;

  virtual ~Operator() = default;

  template <typename T>
  bool is() const {
    return this->type_id() == id_for_type<std::decay_t<T>>();
  }

 protected:
  Operator() = default;

  // each derived class implements this method
  virtual type_id_t type_id() const = 0;

  // type id is computed once for a type T
  // and returns the same id whenever called with T
  template <typename T>
  static type_id_t id_for_type() {
    static auto id = next_id();
    return id;
  }

 private:
  static type_id_t next_id() {
    static std::atomic<type_id_t> grand_type_id = 0;
    return ++grand_type_id;
  }
};

struct Plus final : Operator {
  type_id_t type_id() const override { return id_for_type<Plus>(); }
};

struct Minus final : Operator {
  type_id_t type_id() const override { return id_for_type<Minus>(); }
};

struct Times final : Operator {
  type_id_t type_id() const override { return id_for_type<Times>(); }
};

struct Divide final : Operator {
  type_id_t type_id() const override { return id_for_type<Divide>(); }
};

template <typename Elem>
requires std::is_arithmetic_v<Elem> Elem
evaluate(std::vector<Elem> const& elems,
         std::vector<Operator const*> const& ops) {
  auto e = elems.empty() ? Elem{} : elems[0];
  for (std::size_t i = 1,                   // iter elems
       j = 0;                               // iter ops
       i < elems.size() && j < ops.size();  //
       ++i, ++j) {
    auto o = ops[j];               // [0]
    if (o->is<Plus>()) {           // [1]
      e += elems[i];
    } else if (o->is<Minus>()) {   // [2]
      e -= elems[i];
    } else if (o->is<Times>()) {   // [3]
      e *= elems[i];
    } else if (o->is<Divide>()) {  // [4]
      e /= elems[i];
    } else {
      throw std::runtime_error("Invalid operator encountered!");
    }
  }
  return e;
}

int main() {
  auto const Op = Plus{};
  auto const Om = Minus{};
  auto const Ot = Times{};
  auto const Od = Divide{};

  // evaluating ((((2 * 3) + 6) - 2) / 2)
  auto const nums = std::vector<double>{2, 3, 6, 2, 2};
  auto const ops = std::vector<Operator const*>{&Ot, &Op, &Om, &Od};

  std::cout << "result: " << evaluate(nums, ops) << std::endl;  // result: 5

  return 0;
}