Exploring the Visitor Design Pattern: A benchmark of the pattern and its alternatives

The Visitor is one of those underrated Design Patterns I wish I’d see more often. I mean, if you’ve been coding for a while, surely you have come across this abomination and thought there must be a better way:

1
2
3
4
5
6
7
8
9
if (instance is ChildClassA childA)
{
    // Do some stuff specific to class A
}
else if (instance is ChildClassB childB)
{
    // Do some stuff specific to class B
}
// Repeat for as many classes as you have

Well, there is! And it’s called the Visitor Design Pattern! I won’t explain here how to use that pattern since that’s not the purpose of this article. But should you want to find out more on the visitor, I recommend you check out this article.

Like all patterns, the visitor has some pros and some cons:

Pros:

  • Adding new behaviours to a class hierarchy is a breeze and doesn’t require to modify the hierarchy. If you are a fan of the Open/Closed Principle, that’s a good thing.
  • The same behaviours will end up in the same class. Which follows the Single Responsibility Principle.
  • It’s possible to accumulate some data in a visitor. Thus, allowing us to use a visitor while iterating over a list of objects.

Cons:

  • Adding classes to the class hierarchy is a pain since it requires us to modify each visitor.
  • Private fields and methods are off limit. The visitors can’t access them.
  • Relying on Double Dispatch, there is a slight overhead (Not a huge one, but still an overhead).

So, with those in mind, let’s see what alternatives we can use to replace the visitor, and how well do they perform compared to the visitor?



Why?

Now, you may be wondering why I am writing this article. After all, the Visitor pattern, like most other patterns in Design Patterns: Elements of Reusable Object-Oriented Software, has been discussed over and over again. So, is there truly something new I can bring to the table?

Well, it all started with the following piece of code:

1
2
3
4
5
6
7
8
9
if (instance is ChildClassA childA)
{
    // Do some stuff specific to class A
}
else if (instance is ChildClassB childB)
{
    // Do some stuff specific to class B
}
// Repeat for as many classes as you have

Seeing this abomination way too many codebases, I wanted to record a video talking about how we can clean it up with the visitor pattern. When came the time to list the pros and cons, performance issues came up quickly since it’s no secret that virtual methods have an overhead. But to be thorough, I decided to look up some benchmarks and some possible alternatives to the visitor. To my great surprise, I could not find anything of much use. At best, there were a couple articles that mentioned some alternatives, but not much more.

So that’s why I decided to do that work myself! So that if ever someone, like my past self, needs that kind of information, this article will be ready to be discarded since it’s not on the first Google search page.



Example

Age of Empires 2

To illustrate how each alternative to the Visitor works, I’ll be taking Real-Time Strategy game Units as an example. In Real-Time Strategy games (RTS if you’re a friend), the player can create all sorts of units such as swordmen, priests, archers, … And each unit will have some unique properties and behaviours.  As such, we’ll have a base class for all units that will simply be called Unit. And each type of unit (Swordsman Unit, Boat Unit, …) will have its own class.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Unit
{
};

class SwordsmanUnit : public Unit
{
};

class ArcherUnit : public Unit
{
};

// And many more classes

To be extra thorough, I have performed my benchmarks in both C# and C++. In some cases, I relied on some specific C# language features. In those cases, there is no C++ version. Furthermore, I have performed the tests with 4, 8, and 16 classes. That way, I could verify how well a given solution scales when we add more classes.

Now just as a quick disclaimer, I don’t actually recommend you use this architecture to implement units in a RTS Game. It serves solely as an example to illustrate the various alternatives one could use to replace the Visitor. In fact, since units have lots of behaviours that can be shared, we may not even need more than a single Unit class to handle units. Elements such as the movement behaviour (ground, air, water), damage, appearance are mere parameters a unit could have. To make things more efficient, I’d maybe consider a more Data-Oriented approach and split that unit into smaller components. Anyway, we’re getting a bit off track.

Now, should you want to check out the exact code I have written for this article, you can find it in the following Github Repository. You’ll find in that repository the C# and C++ versions of the examples as well as the raw results on my benchmarks.



Alternatives

So obviously, the Visitor has some issues. That’s why I have compiled a bunch of alternative solutions and have benchmarked each one in C# and C++. Hopefully, with that, we’ll have a more precise idea of what we can do to improve our code.

Now, when we check out the various solutions, we can see that almost none fix the 2 first cons (adding classes is a pain and no access to privates). The main area of improvement is performance.

That is why I’ll be using the following criteria to evaluate each solution:

  • Has the same advantages as a visitor,
  • The style of the solution (which is a completely subjective),
  • The performance of the solution.

As a reference, here are the grades I have given to the visitor:

  • Visitor Benefits: 5/5
  • Style: 4/5
  • Performance: 3/5

Checking the class type with if statements

To begin, let’s start by analysing the abomination. This “solution”, if one can call it that, is to simply try to downcast our unit instance until we find the right type. Once we do find the right type, we call the appropriate logic.

1
2
3
4
5
6
7
8
9
if (SwordsmanUnit* swoardsman = dynamic_cast<SwordsmanUnit*>(unit))
{
    // Do stuff
}
else if (ArcherUnit* archer = dynamic_cast<ArcherUnit*>(unit))
{
    // Do stuff
}
// ...

Stylistically, I find this solution to be horrendous. With a limited number of classes, it may seem alright, but quickly, as you add new classes, your operations will quickly explode in size. This is probably THE worst solution we could imagine as far as the coding style goes. Not only does it look awful, but it also makes adding new classes to our hierarchy harder since we have to grep the code to find our downcasts.

C# Results
C++ Results

Unsurprisingly, performance wise, this “solution” performs worse than the visitor. Better yet, it doesn’t even scale well. That means that for each class we add to our hierarchy, the worse performance will get. In C++, this is even worse since dynamic_cast must take into account the possibility of having multiple parent classes. Whereas C# can perform some optimizations knowing that there’ll always be at most one parent class.

  • Visitor Benefits: 5/5
  • Style: 0/5 DON’T USE THIS “SOLUTION”!!! KILL IT WITH FIRE!!!
  • Performance: 1/5

Adding Virtual functions in the base class

The next solution I’ll be talking about is to give up. Give up on the visitor pattern, and regress back to our lowly Is-A instincts. By that, I mean that we can add operations to our hierarchy by adding abstract functions to the base class. Those operations would then be implemented in each child class.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Unit
{
    virtual void DoStuff() = 0;
};

class SwordsmanUnit : public Unit
{
    void DoStuff() override
    {
        // Do Stuff
    }
};

class ArcherUnit : public Unit
{
    void DoStuff() override
    {
        // Do Stuff
    }
};

// And many more classes

This is another non solution since we lose the main benefit of the visitor: adding operations without modifying the hierarchy. Furthermore, it won’t even be an option if working with classes from an external library since modifying the classes would not be allowed. However, this option does have some undeniable advantages. After all, adding new classes to the hierarchy becomes trivial. All that’s needed is to write a class that overrides the abstract functions. And adding operations can be fairly easy since the code will not compile if there are some unimplemented abstract functions. But as another downside, working that way would lead to managing multiple responsibilities within the same class. As such, we may end up mixing some UI code with some AI code with some rendering code, …

C# Results

C++ Results

Performance wise, calling those virtual functions is a bit faster that the visitor pattern. This makes sense since the visitor relies on two virtual function calls. So that means that in the case of the Visitor, we end up paying for the cost of an extra virtual function call. Personally, even though this solution is faster than the visitor, I would probably still choose the visitor since it allows much more flexibility.

  • Visitor Benefits: 0/5
  • Style: 2/5
  • Performance: 4/5

Pattern Switch (C# specific)

Next up, we have a C# language feature: the Pattern Switch. This method is somewhat similar to manually checking the class type with if statements but instead we rely on a switch. It is no secret that switches are faster than if-else-ifs since switches rely on jump tables. As such, I had to try out this method to see if the C# compiler could perform some optimizations.

1
2
3
4
5
6
switch (unit)
{
    case SwordsmanUnit swordsman: { /*Do Stuff*/ break; }
    case ArcherUnit archer: { /*Do Stuff*/ break; }
    // ...
};

Stylistically, I’d say that this solution is a bit better than the if-else-if solution since it allows us to write a bit less code. I also find that in some cases it can even be more elegant. However, it is no easier to add classes or operations with this solution.

C# Results

As for speed, we can notice that it behaves fairly similarly to the if-else-if solution. As if under the hood, both solutions were exactly the same. As such, Pattern Switches will not scale well either if we were to add new classes. Now don’t get me wrong, Pattern Switches can still be a powerful language feature. However, I do believe it is not a suitable replacement for the Visitor Pattern.

  • Visitor Benefits: 5/5
  • Style: 3/5
  • Performance: 1/5

Casting with the dynamic keyword (C# specific)

Our next solution is yet again a C# language feature. And that is to use the dynamic keyword to cast out unit instance. By having a bunch of functions all named the same but taking different parameters, this cast can automatically choose the right function to call.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
static void DoStuff(SwordsmanUnit swordsman)
{
    // Do Stuff
}

static void DoStuff(ArcherUnit archer)
{
    // Do Stuff
}

// ...


1
2
// Somewhere else in the code
DoStuff((dynamic)unit);

Stylistically, I must admit that I am divided on the subject of the dynamic keyword. On the one hand, it can simplify the code by forcing us to write a function for each case. However, this solution makes adding units and operations no easier that other solutions I have mentioned thus far.

C# Results

It’s the performance that convinced me that using the dynamic keyword is a terrible idea (at least to replace the Visitor pattern). It can be several orders of magnitude slower than the Visitor and it doesn’t scale well either. There probably are some cases where using the dynamic keyword can be justified, but this doesn’t seem to be one.

  • Visitor Benefits: 5/5
  • Style: 3.5/5
  • Performance: 0/5

Switching over an enum

Next up, let’s try to reduce the number of virtual calls. One way to do so is to have an enum with as many entries as we have Unit classes. The base Unit class would have a virtual function that would return that enum. And each child would override that function to return the appropriate enum entry.

This enum can basically replace the RTTI we have been relying on so far with something a lot more lightweight. Here, we can use a switch block to find out the type of class our unit has and execute the right logic accordingly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
enum class UnitType
{
    Swordsman,
    Archer,
    // ...
};

class Unit
{
public:
    virtual ~Unit() = default;
    virtual UnitType GetUnitType() const = 0;
}

class SwordsmanUnit : public Unit
{
public:
    UnitType GetUnitType() const override { return UnitType::Swordsman; }
}

class ArcherUnit : public Unit
{
public:
    UnitType GetUnitType() const override { return UnitType::Archer; }
}

// ...


1
2
3
4
5
6
7
// Somewhere else in the code
switch (unit->GetUnitType())
{
    case UnitType::Swordsman: { /*Do Stuff*/ break; }
    case UnitType::Archer: { /*Do Stuff*/ break; }
    // ...
}

This solution is just about as elegant as using a Pattern Switch. So, let’s just focus on performance.

C# Results

C++ Results

As we can see, this solution has some radically different results depending on the language. In C++, this solution is close to being as performant as having a single virtual call. The extra cost comes from the switch block, which is almost negligeable. However, in C#, I was surprised to notice that even the visitor performs better. My guess was that that overhead came from the switch. So, in my arrogance, I attempted to make my own jump table to see if I could do any better but ended up with some similar results. At the very least, we can notice that that solution scales pretty well.

  • Visitor Benefits: 5/5
  • Style: 3/5
  • Performance (C#): 2/5
  • Performance (C++): 4/5

Improved Switch + enum

To make the previous solution even better, we can totally remove all virtual calls. We can do that by storing the enum value directly in the Unit base class. That value would then be set from the constructors of the child classes. That would mean that we’d reduce the performance cost by increasing the memory cost.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
enum class UnitType
{
    Swordsman,
    Archer,
    // ...
};

class Unit
{
public:
    Unit(UnitType type)
        : m_Type{ type }
    {
    }

    virtual ~Unit() = default;
    UnitType GetUnitType() const { return m_Type; }

private:
    UnitType m_Type;
}

class SwordsmanUnit : public Unit
{
public:
    SwordsmanUnit()
        : unit(UnitType::Swordsman)
    {
    }
}

class ArcherUnit : public Unit
{
public:
    ArcherUnit()
        : unit(UnitType::Archer)
    {
    }
}

// ...


1
2
3
4
5
6
7
// Somewhere else in the code
switch (unit->GetUnitType())
{
    case UnitType::Swordsman: { /*Do Stuff*/ break; }
    case UnitType::Archer: { /*Do Stuff*/ break; }
    // ...
}

As far as the visitor benefits and the style go, this solution is pretty much the same as the previous one, so let’s check out the performance.

C# Results
C++ Results

Just like the previous solution, we can notice that depending on the language, this solution can yield some different results. In C++, this is where the solution shines the brightest. Having eliminated all virtual call, this solution performs several orders of magnitude better than the visitor. However, in C#, doing so still isn’t enough due to the impact of the switch. At the very least, the performance of this method is closer to that of the visitor.

  • Visitor Benefits: 5/5
  • Style: 3/5
  • Performance (C#): 3/5
  • Performance (C++): 5/5


Conclusion

So now that we have evaluated all of those solutions, which is actually the best?

C# Results Recap

In C#, the Visitor appears to be the undisputed champion. The only “solution” that performs better is to add some virtual functions to the base class of our hierarchy. However, as we have seen, doing so loses all the benefits of the visitor. There are of course some other solutions that come close to the performance of the visitor. However, in my opinion, those solutions are still inferior to the visitor. As such, the Visitor is the solution I’d favour in C#.

C++ Results Recap

In C++, it’s possible to drastically improve performance by removing all virtual calls. This can be done with a switch and an enum. However, stylistically, I still find that the visitor is better. So, if performance isn’t a huge issue, I’d say that it’s perfectly fine to keep a Visitor. But if it does matter, I recommend you use the enum + switch solution.

As some last few words, I would like to remind you that this architecture is not ideal. The issues we have been facing stem from relying too much on inheritance. I believe we could achieve something much better by relying on composition instead. So, unless you are stuck with the class hierarchy, I’d recommend you reconsider this architecture as a whole. But if you are stuck with the hierarchy, stick to using the best option the language offers.

Comments

Post a Comment