Improving Performance in C++ with Compile Time Polymorphism
by Ben Sunshine-Hill

Introduction

Virtual functions are one of the most interesting and useful features of classes in C++. They allow for thinking of an object in terms of what type it is (Apple) as well as what category of types it belongs with (Fruit). Further, virtual functions allow for operating on objects in ways that respect their actual types while refering to them by category. However, the power and flexibility of virtual functions comes at a price that a good programmer must weigh against the benefits. Let's take a quick look at using virtual functions and abstract base classes and from there examine a way in which we can improve program performance while retaining the power and flexbility of virtual functions.

Along with modeling different kinds of fruit and different kinds of animals, modeling different kinds of shapes accounts for most of the polymorphism examples found in C++ textbooks. More importantly, modeling different kinds of shapes readily lends itself to an area of game programming where improving performance is a high priority, namely graphics rendering. So modeling shapes will make a good basis for our examination.

Now, let's begin.

class Shape
{
public:
  Shape()
  {
  }

  virtual ~Shape()
  {
  }

  virtual void DrawOutline() const = 0;
  virtual void DrawFill() const = 0;
};

class Rectangle : public Shape
{
public:
  Rectangle()
  {
  }

  virtual ~Rectangle()
  {
  }

  virtual void DrawOutline() const
  {
    ...
  }

  virtual void DrawFill() const
  {
    ...
  }
};

class Circle : public Shape
{
public:
  Circle()
  {
  }

  virtual ~Circle()
  {
  }

  virtual void DrawOutline() const
  {
    ...
  }

  virtual void DrawFill() const
  {
    ...
  }
};

All good so far, right? We can, for example, write...

Shape *myShape = new Rectangle;
myShape->DrawOutline();
delete myShape;

...and trust C++'s runtime polymorphism to decide that the myShape pointer actually points to a Rectangle and that Rectangle's DrawOutline() method should be called. If we wanted it to be a circle instead, we could just change "new Rectangle" to "new Circle", and Circle's DrawOutline() method would be called instead.

But wait a second. Thanks, C++, for the runtime polymorphism, but it's pretty obvious from looking at that code that myShape is going to be a Rectangle; we don't need fancy vtables to figure that out. Consider this code:

void DrawAShapeOverAndOver(Shape* myShape)
{
  for(int i=0; i<10000; i++)
  {
    myShape->DrawOutline();
  }
}

Shape *myShape = new Rectangle;
DrawAShapeOverAndOver(myShape);
delete myShape;

Look at what happens there! The program picks up myShape, inspects it, and says "Hmm, a Rectangle. Ok." Then it puts it down. Then it picks it up again. "Hmm. This time, it's a Rectangle. Ok. Hmm, and this time it's a... Rectangle. Ok." Repeat 9,997 times. Does all this type inspection eat up CPU cycles? Darn tootin' it does. Although virtual function calls aren't what you'd call slow, even a small delay really starts to add up when you're doing it 10,000 times per object per frame. The real tragedy here is that we know that the program doesn't really need to check myShape's type each time through the loop. "It's always going to be the same thing!", we shout at the compiler, "Just have the program look it up the first time!" For that matter, it doesn't really need to be looked up the first time. Because we are calling it on a Rectangle that we have just created, the object type is still going to be a Rectangle when DrawAShapeOverAndOver() gets to it.

Let's see if we can rewrite this function in a way that doesn't require runtime lookups. We will make it specifically for Rectangles, so we can just flat-out tell the dumb compiler what it is and forego the lookup code.

void DrawAShapeWhichIsARectangleOverAndOver(Shape* myShape)
{
  for(int i=0; i<10000; i++)
  {
    reinterpret_cast<Rectangle*>(myShape)->DrawOutline();
  }
}

Unfortunately, this doesn't help one bit. Telling the compiler that the object is a Rectangle isn't enough. For all the compiler knows, the object could be a subclass of Rectangle. We still haven't prevented the compiler from inserting runtime lookup code. To do that we must remove the virtual keyword from the declaration of DrawOutline() and thereby change it into a non-virtual function. That means in turn, however, that we have to declare a separate DrawAShapeOverAndOver() for each and every subclass of Shape that we might want to draw. Alas, pursuing our desire for efficiency has driven us further and further away from our goal, to the point where there is barely any polymorphism left at all. So sad.

Thanks But No Thanks, C++

Reading over the last few paragraphs, the astute programmer will notice an interesting point: At no time did we actually need runtime polymorphism. It helped us write our DrawAShapeOverAndOver() function by letting us write a single function that would work for all classes derived from Shape, but in each case the run-time lookup could have been done at compile-time.

Bearing this in mind, let's approach polymorphism again, but this time with more caution. We won't be making the DrawOutline() method virtual again, since so far that has done us no good at all. Instead, let's rewrite DrawAShapeOverAndOver() as a templated function. This way we are not forced to write both DrawAShapeWhichIsARectangleOverAndOver() and DrawAShapeWhichIsACircleOverAndOver().

template<typename ShapeType>
void DrawAShapeOverAndOver(ShapeType* myShape)
{
  for(int i=0; i<10000; i++)
  {
    myShape->DrawOutline();
  }
}

Rectangle *myRectangle = new Rectangle;
DrawAShapeOverAndOver(myRectangle);
delete myRectangle;

Hey! Now we're getting somewhere! We can pass in any kind of Shape to DrawAShapeOverAndOver(), just like before, except this time there is no runtime checking of myShape's type! Interestingly enough, Rectangle and Circle don't even have to be derived from Shape. They just have to be classes with a DrawOutline() function.

Making Our Lives More Difficult

Let's go back to our original example, but this time let's make more use of the other features of subclassing. After all, derived classes and base classes with no private members, nontrivial constructors, or internal calls of virtual functions are a rather severe oversimplification of subclassing. Let's also supply an actual implementation of DrawOutline() and DrawFill(), albeit using a completely fictional Graphics object that will nevertheless allow us to illustrate how functions in derived classes may use functions in base classes.

Now, let's pull out the big guns.

class Shape
{
public:
  Shape(const Point &initialLocation,
     const std::string &initialOutlineColor,
     const std::string &initialFillColor) :
    location(initialLocation),
    outlineColor(initialOutlineColor),
    fillColor(initialFillColor)
  {
  }

  virtual ~Shape()
  {
  }

  virtual void DrawOutline() const = 0;
  virtual void DrawFill() const = 0;

  void SetOutlineColor(const std::string &newOutlineColor)
  {
    outlineColor = newOutlineColor;
  }

  void SetFillColor(const std::string &newFillColor)
  {
    fillColor = newFillColor;
  }

  void SetLocation(const Point & newLocation)
  {
    location = newLocation;
  }

  const std::string &GetOutlineColor() const
  {
    return outlineColor;
  }

  const std::string &GetFillColor() const
  {
    return fillColor;
  }

  const Point &GetLocation() const
  {
    return location;
  }

  void DrawFilled() const
  {
    DrawOutline();
    DrawFill();
  }

private:
  std::string outlineColor;

  std::string fillColor;

  Point location;
};

class Rectangle : public Shape
{
public:
  Rectangle(const Point &initialLocation,
       const std::string &initialOutlineColor,
       const std::string &initialFillColor(),
       double initialHeight,
       double initialWidth) :
    Shape(initialLocation, initialOutlineColor,
          initialFillColor),
    height(initialHeight),
    width(initialWidth)
  {
  }

  virtual ~Rectangle()
  {
  }

  virtual void DrawOutline() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawRectangleLines(height, width);
  }

  virtual void DrawFill() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawRectangleFill(height, width);
  }

  void SetHeight(double newHeight)
  {
    height = newHeight;
  }

  void SetWidth(double newWidth)
  {
    width = newWidth;
  }

  double GetHeight() const
  {
    return height;
  }

  double GetWidth() const
  {
    return width;
  }

private:
  double height;
  double width;
};

class Circle : public Shape
{
public:
  Circle(const Point &initialLocation,
      const std::string &initialOutlineColor,
      const std::string &initialFillColor,
      double initialRadius) :
    Shape(initialLocation, initialOutlineColor,
          initialFillColor),
    radius(initialRadius)
  {
  }

  virtual ~Circle()
  {
  }

  virtual void DrawOutline() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawCircularLine(radius);
  }

  virtual void DrawFill() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawCircularFill(radius);
  }

  void SetRadius(double newRadius)
  {
    radius = newRadius;
  }

  double GetRadius() const
  {
    return radius;
  }
private:
  double radius;
};

Whew! Let's see what we added there. First of all, Shape objects now have data members. All Shape objects have a location, and an outlineColor and a fillColor. In addition, Rectangle objects have a height and a width, and Circle objects have a radius. Each of these members has corresponding getter and setter functions. The most important new addition is the DrawFilled() method, which draws both the outline and the fill in one step by delegating these methods to the derived class.

We Can Rebuild It; We Have The Technology

Now that we have this all set up, let's rip it apart! Let's tear it down and rebuild it into a class structure which invites compile-time polymorphism.

How shall we do this? First, let's remove the virtual keyword from the declarations of DrawOutline() and DrawFill(). As we touched on earlier, virtual functions add runtime overhead which is precisely what we are trying to avoid. For that matter, let's go one step further and remove the declarations of those functions from the base class altogether, as they do us no good anyway. Let's leave them in as comments, though, so that it remains clear that they were omitted on purpose.

Now, what have we broken? Not much, actually. If we have a Rectangle, we can get and set its height and width and colors and location, and we can draw it. Life is good. However, one thing that we have broken is the DrawFilled() function, which calls the now nonexistent base class functions DrawOutline() and DrawFill(). Base classes can only call functions of derived classes if those functions are declared as virtual in the base class--which is precisely what we do not want.

In order to fix the broken DrawFilled() function, we will use templates in a very strange and interesting way. Here's a bit of code to broadly illustrate the insanity that is to come.

template <typename ShapeType>
class Shape
{

...
protected:
  Shape( ... )
  {
  }

};

class Rectangle : public Shape<Rectangle>
{

public:
  Rectangle( ... ) :
    Shape<Rectangle>( ... )
  {
  }
...

};

Whaaa? That's right: Rectangle no longer inherits from Shape; now it inherits from a special kind of Shape. Rectangle creates its own special Shape class, Shape<Rectangle>, to inherit from. In fact, Rectangle is the only class that inherits from this specially crafted Shape<Rectangle>. To enforce this, we declare the constructor of the templated Shape class protected so that an object of this type can not be instanced directly. Instead, this special kind of Shape must be inherited from and instanced within the public constructor of the derived class.

Yes, it's legal. Yes, it's strange. Yes, it's necessary. It's called the "Curiously Recurring Template Pattern" (or Idiom, depending on who you ask).

But why? What could this strange code possibly gain us??

What we gain is the template parameter. The base class Shape now knows that it really is the Shape part of a Rectangle because we have told it so through the template parameter, and because we have taken a solemn oath that the only class that ever inherits Shape<Rectangle> is Rectangle. If Shape<ShapeType> ever wonders what subclass it's a part of, it can just check its ShapeType template parameter.

What this knowledge gains us, in turn, is the ability to downcast. Downcasting is taking an object of a base class and casting it as an object of a derived class. It's what dynamic_cast does for virtual classes, and it's what virtual function calls do. It's also what we tried to do way back near the beginning of this article, when we tried to use reinterpret_cast to convince our compiler that myShape was a Rectangle. Now that the functions aren't virtual anymore, however, this will work much better (in other words, it'll work). Let's use it to rewrite DrawFilled().

template <typename ShapeType>
class Shape
{
  void DrawFilled()
  {
    reinterpret_cast<const ShapeType *>(this)->DrawOutline();
    reinterpret_cast<const ShapeType *>(this)->DrawFill();
  }
};

Take a moment to cogitate on this code. It's possibly the most crucial part of this entire article. When DrawFilled() is called on a Rectangle, even though it is a method defined in Shape and thus called with a this pointer of type Shape, it knows that it can safely treat itself as a Rectangle. This lets Shape reinterpret_cast itself down to a Rectangle and from there call DrawOutline() on the resultant Rectangle. Ditto with DrawFill().

Putting It Together

So let's put it all together.

template<typename ShapeType>
class Shape
{
public:
  ~Shape()
  {
  }

/* Omitted from the base class and
   declared instead in subclasses */
/* void DrawOutline() const = 0; */
/* void DrawFill() const = 0; */

  void SetOutlineColor(const std::string &newOutlineColor)
  {
    outlineColor = newOutlineColor;
  }

  void SetFillColor(const std::string &newFillColor)
  {
    fillColor = newFillColor;
  }

  void SetLocation(const Point &newLocation)
  {
    location = newLocation;
  }

  const std::string &GetOutlineColor() const
  {
    return outlineColor;
  }

  const std::string &GetFillColor() const
  {
    return fillColor;
  }

  const Point &GetLocation() const
  {
    return location;
  }

  void DrawFilled() const
  {
    reinterpret_cast<const ShapeType *>(this)->DrawOutline();
    reinterpret_cast<const ShapeType *>(this)->DrawFill();
  }

protected:
  Shape(const Point &initialLocation,
     const std::string &initialOutlineColor,
     const std::string &initialFillColor) :
    location(initialLocation),
    outlineColor(initialOutlineColor),
    fillColor(initialFillColor)
  {
  }

private:
  std::string outlineColor;

  std::string fillColor;

  Point location;
};

class Rectangle : public Shape<Rectangle>
{
public:
  Rectangle(const Point &initialLocation,
        const std::string &initialOutlineColor,
        const std::string &initialFillColor,
        double initialHeight,
        double initialWidth) :
    Shape<Rectangle>(initialLocation, initialOutlineColor,
                     initialFillColor),
    height(initialHeight),
    width(initialWidth)
  {
  }

  ~Rectangle()
  {
  }

  void DrawOutline() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawRectangleLines(height, width);
  }

  void DrawFill() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawRectangleFill(height, width);
  }

  void SetHeight(double newHeight)
  {
    height = newHeight;
  }

  void SetWidth(double newWidth)
  {
    width = newWidth;
  }

  double GetHeight() const
  {
    return height;
  }

  double GetWidth() const
  {
    return width;
  }

private:
  double height;
  double width;
};

class Circle : public Shape<Circle>
{
public:
  Circle(const Point &initialLocation,
      const std::string &initialOutlineColor,
      const std::string &initialFillColor,
      double initialRadius) :
    Shape<Circle>(initialLocation, initialOutlineColor,
                  initialFillColor),
    radius(initialRadius)
  {
  }

  ~Circle()
  {
  }

  void DrawOutline() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawCircularLine(radius);
  }

  void DrawFill() const
  {
    Graphics::SetColor(GetOutlineColor());
    Graphics::GoToPoint(GetLocation());
    Graphics::DrawCircularFill(radius);
  }

  void SetRadius(double newRadius)
  {
    radius = newRadius;
  }

  double GetRadius() const
  {
    return radius;
  }
private:
  double radius;
};

This is just what we need! Base class functions can defer certain functionality to derived classes and derived classes can decide which base class functions to override. If we had declared a non-virtual DrawOutline() function in Shape (rather than leaving it in only as a comment), it would be optional for Circle and Rectangle to override it. This approach allows programmers using a class to not concern themselves with whether a function is in the derived class or inherited from the base class. It's the functionality that we had in the last section, but without the added overhead of run-time polymorphism.

While we're at it, let's rewrite DrawAShapeOverAndOver().

template<typename ShapeType>
void DrawAShapeOverAndOver(ShapeType* myShape)
{
  for(int i=0; i<10000; i++)
  {
    myShape->DrawOutline();
    // OR
    myShape->DrawFilled();
  }
}

Rectangle *rectangle = new Rectangle;
DrawAShapeOverAndOver(rectangle);
delete rectangle;

Notice that we can call member functions declared either in the derived class or the base class. Of course, if the templated function uses member functions defined in only a particular derived class (such as GetRadius()), the templated function will not compile if used with a class that does not have those member functions. For example, calling GetRadius() on a Rectangle will not compile.

Limitations

The biggest limitation of compile-time polymorphism is that it's compile-time. In other words, if we want to call a function on a Rectangle, we can't do it through a pointer to a Shape. In fact, there is no such thing as a pointer to a Shape, since there is no Shape class without a template argument.

This is less of a limitation than you might think. Take another look at our rewritten DrawAShapeOverAndOver():

template<typename ShapeType>
void DrawAShapeOverAndOver(ShapeType* myShape)
{
  for(int i=0; i<10000; i++)
  {
    myShape->DrawOutline();
  }
}

Essentially, wherever you once had functions that took in base class pointers, you now have templated functions that take in derived class pointers (or derived classes). The responsibility for calling the correct member function is delegated to the outer templated function, not to the object.

Templates have drawbacks. Although the best way to get a feel for these drawbacks is to experience them yourself, it's also a good idea for a programmer to have an idea of what to expect. First and foremost is that most compilers require templates to be declared inline. This means that all your templated functions will have to go in the header, which can make your code less tidy. (If you're using the Comeau compiler, this doesn't apply to you. Congratulations.)

Secondly, templates can lead to code bloat, since different versions of the functions must be compiled for each datatype they are used with. How much code bloat is caused is very specific to the project; switching all of my content loading functions to use this model increased my stripped executable size by about 50k. As always, the best source of wisdom is your own tests.

Summary

Using templates for compile-time polymorphism can increase performance when they are used to avoid needless virtual function binding. With careful design, templates can be used to give non-virtual classes all the capabilities that virtual classes have, except for runtime binding. Although such compile-time polymorphism is not appropriate for every situation, a careful decision by the programmer as to where virtual functions are actually needed can dramatically improve code performance, without incurring a loss of flexibility or readability.

Discuss this article in the forums

Date this article was posted to GameDev.net: 11/7/2003
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
C and C++
Featured Articles