Is there life without RTTI or How we wrote our own dynamic_cast
Tags: cpp, architecture, tutorial, productivity
Published: 2022-10-21 09:14:01

There aren't many things left in modern C\+\+ that don't fit the "Don't pay for what you don't use" paradigm\. One of them is dynamic\_cast\. In this article, we'll find out what's wrong with it, and after that — try to find an alternative\.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s5vm2l8f9qy457t2t8fd.png)

## About dynamic\_cast

Let's refresh our memory about the C\+\+ basics\. If you find that part boring, you can always skip it\.

So, suppose we have the following class hierarchy:

```cpp
struct Shape
{
  virtual void Draw() const = 0;
};

struct Circle : Shape
{
  void Draw() const override;
};

struct Triangle : Shape
{
  void Draw() const override;
};

struct Rectangle : Shape
{
  void Draw() const override;
};
```

According to the object\-oriented paradigm, we can safely perform *upcasting* —expand a pointer to the child class object and turn it into a pointer to the base class:

```cpp
#include <memory>

void foo(const Shape *);

void bar()
{
  std::unique_ptr<Shape>   circle = std::make_unique<Circle>();
  std::unique_ptr<Shape> triangle = std::make_unique<Triangle>();
  std::unique_ptr<Shape>     rect = std::make_unique<Rectangle>();

  foo(circle.get());
  foo(triangle.get());
  foo(rect.get());
}
```

Since the derived classes \(*Circle*, *Triangle*, and *Rectangle*\) are guaranteed to have an instance of the *Shape* base class, the compiler can perform such transformation without any additional actions\.

What if we now want to turn the pointer to the base class into the pointer to the the derived class? Any class derived from* Shape* can hide beneath the pointer to it\. We need to somehow understand at runtime what's actually stored under the pointer\. And here comes the *runtime type identification* \(*RTTI*\)\.

RTTI is a special mechanism that allows us to determine the data type of a variable at runtime\. RTTI is used every time you use the *[dynamic\_cast](https://en.cppreference.com/w/cpp/language/dynamic_cast)* and *[typeid](https://en.cppreference.com/w/cpp/language/typeid)* operators\. The C\+\+ standard does not determine how exactly RTTI is implemented, and its implementation is "delegated" to the *application binary interface* \(*ABI*\)\. Most compilers store information in a virtual table \(*vtable*\)\. If you need details, you can look at the vtable implementation on the [x86\_64](https://itanium-cxx-abi.github.io/cxx-abi/abi.html#rtti) platform\.

To correctly *downcast* from the pointer to a base class to the pointer to the child class, let's use the *dynamic\_cast* operator:

```cpp
void Visit(const Shape *ptr)
{
  if (auto circle = dynamic_cast<const Circle *>(ptr))
  {
    // do smth with circle
  }
  else if (auto triangle = dynamic_cast<const Triangle *>(ptr))
  {
    // do smth with triangle
  }
  else if (auto rect = dynamic_cast<const Rectangle *>(ptr))
  {
    // do smth with rect
  }
}
```

Of course, *dynamic\_cast* is not so common in user code, *typeid* is used even lesser\. Someone may think that such operators are a sign of poor application design\. But what about applications where these operations are forced measure and their number may be up to millions? Does looking into *vtable* drastically slow down the program? That's what we're going to talk about\.

## Issue

Static analyzers, as well as compilers, work with source code via its intermediate representation\. Abstract syntax tree \(AST\) is one of them\. In AST, nodes represent various language constructs\.

A convenient way to implement AST in code is via class hierarchy\. In the Clang compiler, for example, tree nodes are derived from such classes as *[Decl](https://clang.llvm.org/doxygen/classclang_1_1Decl.html)* \(interface for function and type declarations\) and *[Stmt](https://clang.llvm.org/doxygen/classclang_1_1Stmt.html)* \(interface for constructions\)\. 

Look at the example\. Let's assume we have the synthetic code block which looks as follows:

```cpp
{
  for (size_t i = 0; i < 10; ++i) ;
  if (true) ;
}
```

According to the grammar of [C](https://en.cppreference.com/w/c/language/statements) and [C\+\+](https://en.cppreference.com/w/cpp/language/statements), this is a compound statement \(block\) that contains the *for* loop and the *if* branch\. If we try to implement this in the object\-oriented paradigm, we'll have the following entities:

```cpp
// Base class for all type of statements
struct Stmt { /* .... */ };

// Base class for all type of expressions
struct Expr { /* .... */ };

// Base class for all types of declarations
struct Decl { /* .... */ };

struct IfStmt : Stmt
{
  const Expr& GetCondition() const noexcept;
  const Stmt& GetBody()      const noexcept;
  const Stmt* GetElse()      const noexcept;

  // ....
};

struct ForStmt : Stmt
{
  const Decl* GetInit()         const noexcept;
  const Expr* GetCondition()    const noexcept;
  const Expr* GetPostBodyExpr() const noexcept;
  const Stmt& GetBody()         const noexcept;

  // ....
};

using StatementList = ....;

struct CompoundStmt : Stmt
{
  auto begin() const noexcept { return stmts.begin(); }
  auto end() const noexcept { return stmts.end(); }
  
private:
  StatementList stmts;

  // ....
};
```

We'll put all constructs located the block in a container \(for example, *std::vector*\)\. Since there are way more than one construct, we'll work with them via pointers to the *Stmt* base class\. Now we can iterate over all constructs:

```cpp
void foo(const CompoundStmt *compStmt)
{
  for (auto stmt : compStmt)
  {
    // do smth
  }
}
```

And finally, call our custom logic for every specialized node:

```cpp
void Visit(const IfStmt &);
void Visit(const ForStmt &);
```

Here we face a problem: we need to know at runtime what construct lies under the pointer to *Stmt* and call the necessary overload:

```cpp
void foo(const Stmt *stmt)
{
  for (auto stmt : compStmt)
  {
    if (auto ifStmt = dynamic_cast<const IfStmt *>(stmt))
    {
      Visit(*ifStmt);
    }
    else if (auto forStmt = dynamic_cast<const ForStmt *>(stmt))
    {
      Visit(*forStmt);
    }
  }
}
```

However, there's a small detail because of which the code above **may** not compile\. If the *Stmt* base class is not polymorphic, then *dynamic\_cast* won't work its magic\. To fix this issue, we need to add at least one virtual function\. Like this:

```cpp
struct Stmt { virtual void Dummy(); /* .... */ };
```

Now everything's fine and the code works in most cases\. Until it turns out that RTTI is off in the project and there are reasons for it\. For example, in GCC/Clang we can do it by passing the *\-fno\-rtti* flag; In MSVC — via */GR\-*\. Note that disabling RTTI dies not affect the [exception mechanism](https://godbolt.org/z/zcso7rTcz) and [dynamic dispatch](https://godbolt.org/z/KeEM88vP9)\.

By the way, while I was writing the article, I found an interesting survey on [isocpp\.org](https://isocpp.org/files/papers/CppDevSurvey-2019-04-summary.pdf)\. Out of *2058* respondents, *14%* said that they partly disable RTTI on their programs, and *18%* completely disable it\.

In conclusion, *dynamic\_cast* is bad because:

* It work only on polymorphic types\.
* It doesn't work with the *\-fno\-rtti* flag\.
* ABI\-specific information about types is required for its work\.
* Downcasting works via the *vtable* view, and this is a slow operation\.

The [visitor](https://en.wikipedia.org/wiki/Visitor_pattern) design pattern can be one of the solutions\. It eliminates the need to perform *dynamic\_cast* at cost of one\-two virtual function calls\. However, let's see how we can do the other way\.

## Writing our own dynamic\_cast

### Set the stage

The recipe is simple\. We'll implement a field with the type information in the parent class and check it ourselves\. This is how it looks:

```cpp
struct Stmt
{ 
  enum Type { IfStmt, ForStmt, DoStmt, WhileStmt, ....  };
  const Type m_kind;
  Stmt(Type kind) : m_kind { kind } { /* .... */ }
  /* .... */
};

struct IfStmt : Stmt
{
  IfStmt() : Stmt { Stmt::Type::IfStmt } { /* .... */ }
  /* .... */
};

struct ForStmt : Stmt
{
  ForStmt() : Stmt { Stmt::Type::ForStmt } { /* .... */ }
  /* .... */
};
```

Then when creating an object of the child class, we'll write the class type in the *m\_kind* field\. Now we can check the type like this:

```cpp
void foo(const Stmt *stmt)
{
  if (stmt->m_kind == Stmt::Type::IfStmt)
  {
    auto ifStmt = static_cast<const IfStmt *>(stmt)
    Visit(*ifStmt);
  }
  else if (stmt->m_kind == Stmt::Type::ForStmt)
  {
    auto forStmt = static_cast<const ForStmt *>(stmt)
    Visit(*forStmt);
  }
}
```

The pros of this approach are as follows:

* Polymorphism of classes is now optional\.
* The code can be compiled without RTTI\.
* We control the size of the type information\. We also know the additional information about the class — it's the size of enumeration\.
* Quick check and conversion via *static\_cast* in theory is quicker than *dynamic\_cast*\.

However, there are cons as well:

* We write more code\.
* With multiple inheritance, the logic of checks will not be that simple\.
* *static\_cast* can't work with [virtual inheritance](https://godbolt.org/z/Kb175eh4E), and the code won't compile\. But how many people use virtual inheritance in 2022?

After looking at the code, you may wonder: "Where is the analog of *dynamic\_cast* here?" Of course, writing checks like that is not convenient\. To fix it, let's add a bit of abstraction\. Let's look at how it is implemented in PVS\-Studio and LLVM\.

### Make it neat\. The PVS\-Studio approach

Let's go back to our example:

```cpp
struct Stmt
{ 
  enum Type { IfStmt, ForStmt, DoStmt, WhileStmt, ....  };
  Stmt(Type kind) : m_kind { kind } { /* .... */ }
  Type Kind() const { return m_kind; }
private:
  const Type m_kind;
  /* .... */
};
```

Let's implement the *IsA* function template which will accept the pointer to an object and the intended type\. Inside, this function will check for a null pointer and the needed *kind*\.

```cpp
template <typename T, typename Kind>
bool IsA(T *p, Kind kind) noexcept
{
  return p && p->Kind() == kind;
}
```

Next, we'll implement a couple of struct templates without definition:

```cpp
template <Stmt::Type K>
struct type_from_kind;

template <typename T>
struct kind_from_type;
```

The templates are needed to further specialize structs for each derived class\. Thus, we will link the tree node type and the enumeration constant located within the class\.

```cpp
template <> struct type_from_kind<Stmt::IfStmt>
{
  using type = IfStmt;
};

template <> struct kind_from_type<IfStmt>
{
  static constexpr auto value = Stmt::Type::IfStmt;
};
```

Of course, writing such specializations for each class is not very great\. Here the "macro magic" comes to the rescue\.

```cpp
#define MAKE_STMT_TRAITS(t, k) \
  template <> struct type_from_kind<k> \
  { \
    using type = t; \
  }; \

  template <> struct kind_from_type<t> \
  { \
    static constexpr auto value = k; \
  };
```

Then the definition of child classes will look like this:

```cpp
struct IfStmt : Stmt { /* .... */ };
MAKE_STMT_TRAITS(IfStmt, Stmt::IfStmt)

struct ForStmt : Stmt { /* .... */ };
MAKE_STMT_TRAITS(ForStmt, Stmt::ForStmt)
```

Now we can implement our own* dyn\_cast* that encapsulates *static\_cast* with a check for the desired type via the *IsA* function:

```cpp
template <typename To, typename From>
  requires std::is_pointer_v<To> && std::convertible_to<From, To>
auto dyn_cast(From *p) noexcept
{
  using ResultType = std::remove_cvref_t<std::remove_pointer_t<To>>;
  return IsA(p, kind_from_type<ResultType>::value)
           ? static_cast<To>(p)
           : nullptr;
}
```

Thanks to this approach, we can achieve consistency with the way when we just wrote *dynamic\_cas*t:

```cpp
void foo(const Stmt *stmt)
{
  for (auto stmt : compStmt)
  {
    if (auto ifStmt = dyn_cast<const IfStmt *>(stmt))
    {
      Visit(*ifStmt);
    }
    else if (auto forStmt = dyn_cast<const ForStmt *>(stmt))
    {
      Visit(*forStmt);
    }
  }
}
```

Now let's inspect another approach\.

### Make it neat\. The LLVM approach

Let's go back to the *Stmt* struct:

```cpp
struct Stmt
{ 
  enum Type { IfStmt, ForStmt, DoStmt, WhileStmt, ....  };
  Stmt(Type kind) : m_kind { kind } { /* .... */ }
  Type Kind() const { return m_kind; }
private:
  const Type m_kind;
  /* .... */
};
```

We implement *classof*, a static member function, in each descendant class\. It takes the pointer to the base class and checks it for a match with kind of the child class:

```cpp
struct IfStmt : Stmt
{
  static bool classof(const Stmt *stmt) noexcept
  {
    return stmt->Kind() == Stmt::Type::IfStmt;
  }
  /* .... */
};

struct ForStmt : Stmt
{
  static bool classof(const Stmt *stmt) noexcept
  {
    return stmt->Kind() == Stmt::Type::ForStmt;
  }
  /* .... */
};
```

Next, in the *IsA* function we need to simply call *classof* from the type that the first template parameter  passed to us:

```cpp
template <typename To, typename From>
bool IsA(From *p) noexcept
{
  using ResultType = std::remove_cvref_t<
    std::remove_pointer_t< std::remove_cv_ref_t<To> >
  >;

  return ResultType::classof(p);
}
```

Then our *dyn\_cast* will perform the same *IsA* check, as it the first method\. Depending on whether it matches or not, either *static\_cast* is performed to the desired type or a null pointer is returned:

```cpp
template <typename To, typename From>
  requires std::is_pointer_v<To> && std::convertible_to<From *, To>
auto dyn_cast(From *p) noexcept
{
  using res_type = std::remove_cv_t < 
    std::remove_pointer_t< std::remove_cvref_t<To> >
  >;
 
  return IsA<res_type>(p) ? static_cast<To>(p) : nullptr;
}
```

## Benchmarks

When I talked about benchmarks at the conference, I mentioned only synthetic tests\. I suspected this wouldn't be enough, and one of my teammates also noted this\. At the conference I was told that without knowing the performance gain of a given option, we can't rush and rewrite the code according to it\. In this article, I decided to make amends and give statistics on how much the analyzer core will slow down if *dynamic\_cast* is returned\.

### Synthetic example

A synthetic example looks like this \([link](https://quick-bench.com/q/v-3hraub6v8nlitjtx8ybgDT7PA) to Quick C\+\+ Benchmark\)\.

1. We define the *Stmt\_RTTI* struct from which the *IfStmt\_RTTI* and *ForStmt\_RTTI* structs will be inherited\. We will later convert them using *dynamic\_cast\.*
2. Let's define the struct of *Stmt\_WithEnum* from which *IfStmt\_WithEnum* and *ForStmt\_WithEnum* will be inherited\. We will convert them by checking with the *IsA* function, implemented in the two ways described above, and by converting using *static\_cast*\.
3. We form a vector of 1'000'000 smart pointers to the type *Stmt\_RTTI* / *Stmt\_WithEnum*, initialize them pseudo\-randomly with inheritors\.
4. Iterate over the vector and convert to one of the child types\.



[Benchmark code](https://gist.github.com/Vezhur/a29596a8387f513aad0c5b35b14c758e)

Results:

![0998_Implement_dynamic_cast/image2.png](https://import.viva64.com/docx/blog/0998_Implement_dynamic_cast/image2.png)

As you can see, the *dynamic\_cast* option in 3\-4 times slower than the two other options\. 

However, let's not rush to conclusions just yet\. We need to see how PVS\-Studio behaves on real projects\.

### Real benchmark

Of course, we want to answer the question: does it give the analyzer any performance gain? Obviously, the analyzer spends most of its time not in pointer conversion functions, but, for example, in diagnostic rules\.

* To measure, we changed our optimized conversion operations only in the function that performs conversions between the nodes of the tree and its specializations\. Note that it's not the only entity that carries such functionality\.

We will take measurements on *SelfTester* – this is our own utility that takes a pool of 123 test projects and analyzes them with PVS\-Studio\. The utility simultaneously runs the analysis of 4 projects, each project is checked in 8 threads\. We use real open source projects as test projects\. As a result, an analyzer warning log is generated for each project\. This log is compared with the reference log for the same project\. After that, SelfTester creates a log comparison report in a form that is convenient for the developer to understand\.

We ran *SelfTester* on a machine with the following configuration:

* Intel Core i7\-9700k;
* 32 GB RAM;
* Samsung SSD 970 EVO Plus 500GB as a system disk;
* WDC WD10EZEX\-22MFCA0, *SelfTester* is located here\.

For the benchmark, we ran the analysis on projects twice\. The first time we ran the tool with a core where our *dyn\_cast* analog was changed to *dynamic\_cast*\. The second time — with our optimized option\. Both times we ran the analysis on the up\-to date version of the PVS\-Studio core\.

Results of measurements on 15 projects from the pool:

|Project|The project size, KLOC|Time: dynamic\_cast|Time: check \+ static\_cast|
|---|---|---|---|
|SObjectizer|17\.2|0:01:10|0:00:56|
|StrongDC|102|0:00:46|0:00:41|
|Notepad\+\+|111|0:02:48|0:02:55|
|WinMerge|172|0:11:02|0:09:48|
|db\_10|213|0:36:58|0:32:20|
|pcsx2|302|0:04:44|0:04:57|
|dosbox|302|0:05:54|0:04:12|
|CamStudio|327|0:09:49|0:08:34|
|Shareaza|400|0:40:32|0:36:17|
|mpc\-hc|872|0:40:46|0:34:30|
|QtParts|1361|0:03:31|0:02:35|
|miranda32|1811|0:32:03|0:27:07|
|awesome\-hpp|2196|0:12:01|0:11:37|
|ffdshow|2213|0:36:23|0:34:08|
|Freeswitch|3690|0:37:33|0:33:30|

Then we tried to eliminate the statistical error a bit and repeated the experiment:

|Project|The project size, KLOC|Time: dynamic\_cast|Time: check \+ static\_cast|
|---|---|---|---|
|SObjectizer|17\.2|0:01:04|0:00:51|
|StrongDC|102|0:00:49|0:00:47|
|Notepad\+\+|111|0:03:11|0:02:58|
|WinMerge|172|0:11:23|0:09:44|
|db\_10|213|0:37:38|0:32:50|
|pcsx2|302|0:04:49|0:04:35|
|dosbox|302|0:06:05|0:05:20|
|CamStudio|327|0:10:19|0:09:15|
|Shareaza|400|0:40:48|0:36:39|
|mpc\-hc|872|0:37:37|0:34:18|
|QtParts|1361|0:03:52|0:03:05|
|miranda32|1811|0:33:04|0:31:28|
|awesome\-hpp|2196|0:12:09|0:11:18|
|ffdshow|2213|0:39:32|0:36:04|
|Freeswitch|3690|0:36:54|0:32:16|

![0998_Implement_dynamic_cast/image4.png](https://import.viva64.com/docx/blog/0998_Implement_dynamic_cast/image4.png)

From benchmarks we can see that the larger the project's size, the stronger *dynamic\_cast* affects the final time of the analysis\. And for small projects that are quickly analyzed, the change is not so significant\.

## Results

As a result, we can really say that for some projects, disabling RTTI can lead to a significant performance gain\. After all, Clang compiles with *\-fno\-rtti* for a reason\. However, don't get too hung up on this and fight RTTI everywhere\. Sometimes the convenience of writing code can be more important than the performance gain \(especially if it is only hypothetical\)\.