• 11/07/03 10:46 AM
    Sign in to follow this  

    Improving Performance in C++ with Compile Time Polymorphism

    General and Gameplay Programming

    Myopic Rhino
    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. [code] 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 { ... } }; [/code] All good so far, right? We can, for example, write... [code] Shape *myShape = new Rectangle; myShape->DrawOutline(); delete myShape; [/code] ...and trust C++'s runtime polymorphism to decide that the [tt]myShape[/tt] pointer actually points to a [tt]Rectangle[/tt] and that [tt]Rectangle[/tt]'s [tt]DrawOutline()[/tt] method should be called. If we wanted it to be a circle instead, we could just change "[tt]new Rectangle[/tt]" to "[tt]new Circle[/tt]", and [tt]Circle[/tt]'s [tt]DrawOutline() [/tt]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 [tt]myShape[/tt] is going to be a [tt]Rectangle;[/tt] we don't need fancy vtables to figure that out. Consider this code: [code] void DrawAShapeOverAndOver(Shape* myShape) { for(int i=0; i<10000; i++) { myShape->DrawOutline(); } } Shape *myShape = new Rectangle; DrawAShapeOverAndOver(myShape); delete myShape; [/code] Look at what happens there! The program picks up [tt]myShape[/tt], inspects it, and says "Hmm, a [tt]Rectangle[/tt]. Ok." Then it puts it down. Then it picks it up again. "Hmm. This time, it's a [tt]Rectangle[/tt]. Ok. Hmm, and this time it's a... [tt]Rectangle[/tt]. 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 [i]know[/i] that the program doesn't really need to check [tt]myShape[/tt]'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 [tt]Rectangle[/tt] that we have just created, the object type is still going to be a [tt]Rectangle[/tt] when [tt]DrawAShapeOverAndOver()[/tt] 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 [tt]Rectangle[/tt]s, so we can just flat-out [i]tell[/i] the dumb compiler what it is and forego the lookup code. [code] void DrawAShapeWhichIsARectangleOverAndOver(Shape* myShape) { for(int i=0; i<10000; i++) { reinterpret_cast(myShape)->DrawOutline(); } } [/code] Unfortunately, this doesn't help one bit. Telling the compiler that the object is a [tt]Rectangle[/tt] isn't enough. For all the compiler knows, the object could be a subclass of [tt]Rectangle[/tt]. We still haven't prevented the compiler from inserting runtime lookup code. To do that we must remove the [tt]virtual[/tt] keyword from the declaration of [tt]DrawOutline()[/tt] and thereby change it into a non-virtual function. That means in turn, however, that we have to declare a separate [tt]DrawAShapeOverAndOver()[/tt] for each and every subclass of [tt]Shape[/tt] 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 [i]need[/i] runtime polymorphism. It helped us write our [tt]DrawAShapeOverAndOver()[/tt] function by letting us write a single function that would work for all classes derived from [tt]Shape[/tt], 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 [tt]DrawOutline()[/tt] method virtual again, since so far that has done us no good at all. Instead, let's rewrite [tt]DrawAShapeOverAndOver()[/tt] as a templated function. This way we are not forced to write both [tt]DrawAShapeWhichIsARectangleOverAndOver()[/tt] and [tt]DrawAShapeWhichIsACircleOverAndOver()[/tt]. [code] template void DrawAShapeOverAndOver(ShapeType* myShape) { for(int i=0; i<10000; i++) { myShape->DrawOutline(); } } Rectangle *myRectangle = new Rectangle; DrawAShapeOverAndOver(myRectangle); delete myRectangle; [/code] Hey! Now we're getting somewhere! We can pass in any kind of [tt]Shape[/tt] to [tt]DrawAShapeOverAndOver()[/tt], just like before, except this time there is no runtime checking of [tt]myShape[/tt]'s type! Interestingly enough, [tt]Rectangle[/tt] and [tt]Circle[/tt] don't even have to be derived from [tt]Shape[/tt]. They just have to be classes with a [tt]DrawOutline()[/tt] 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 [tt]DrawOutline()[/tt] and [tt]DrawFill()[/tt], albeit using a completely fictional [tt]Graphics[/tt] 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. [code] 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; }; [/code] Whew! Let's see what we added there. First of all, [tt]Shape[/tt] objects now have data members. All [tt]Shape[/tt] objects have a [tt]location[/tt], and an [tt]outlineColor[/tt] and a [tt]fillColor[/tt]. In addition, [tt]Rectangle[/tt] objects have a height and a width, and [tt]Circle[/tt] objects have a radius. Each of these members has corresponding getter and setter functions. The most important new addition is the [tt]DrawFilled()[/tt] 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 [tt]virtual[/tt] keyword from the declarations of [tt]DrawOutline()[/tt] and [tt]DrawFill()[/tt]. 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 [tt]Rectangle[/tt], 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 [tt]DrawFilled()[/tt] function, which calls the now nonexistent base class functions [tt]DrawOutline()[/tt] and [tt]DrawFill()[/tt]. 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 [tt]DrawFilled()[/tt] 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. [code] template class Shape { ... protected: Shape( ... ) { } }; class Rectangle : public Shape { public: Rectangle( ... ) : Shape( ... ) { } ... }; [/code] Whaaa? That's right: [tt]Rectangle[/tt] no longer inherits from [tt]Shape[/tt]; now it inherits from a special [i]kind[/i] of [tt]Shape[/tt]. [tt]Rectangle[/tt] creates its own special [tt]Shape[/tt] class, [tt]Shape[lessthan]Rectangle>[/tt], to inherit from. In fact, [tt]Rectangle[/tt] is the only class that inherits from this specially crafted [tt]Shape[lessthan]Rectangle>[/tt]. To enforce this, we declare the constructor of the templated [tt]Shape[/tt] class [tt]protected[/tt] so that an object of this type can not be instanced directly. Instead, this special kind of [tt]Shape[/tt] must be inherited from and instanced within the [tt]public[/tt] 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 [tt]Shape[/tt] now knows that it really is the [tt]Shape[/tt] part of a [tt]Rectangle[/tt] 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 [tt]Shape[lessthan]Rectangle>[/tt] is [tt]Rectangle[/tt]. If [tt]Shape[lessthan]ShapeType>[/tt] ever wonders what subclass it's a part of, it can just check its [tt]ShapeType[/tt] 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 [tt]dynamic_cast[/tt] 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 [tt]reinterpret_cast[/tt] to convince our compiler that [tt]myShape[/tt] was a [tt]Rectangle[/tt]. 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 [tt]DrawFilled()[/tt]. [code] template class Shape { void DrawFilled() { reinterpret_cast(this)->DrawOutline(); reinterpret_cast(this)->DrawFill(); } }; [/code] Take a moment to cogitate on this code. It's possibly the most crucial part of this entire article. When [tt]DrawFilled()[/tt] is called on a [tt]Rectangle[/tt], even though it is a method defined in [tt]Shape[/tt] and thus called with a [tt]this[/tt] pointer of type [tt]Shape[/tt], it knows that it can safely treat itself as a [tt]Rectangle[/tt]. This lets [tt]Shape[/tt] [tt]reinterpret_cast[/tt] itself down to a [tt]Rectangle[/tt] and from there call [tt]DrawOutline()[/tt] on the resultant [tt]Rectangle[/tt]. Ditto with [tt]DrawFill()[/tt].

    Putting It Together

    So let's put it all together. [code] template 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(this)->DrawOutline(); reinterpret_cast(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 { 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) { } ~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 { public: Circle(const Point &initialLocation, const std::string &initialOutlineColor, const std::string &initialFillColor, double initialRadius) : Shape(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; }; [/code] 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 [tt]non-virtual[/tt] [tt]DrawOutline()[/tt] function in [tt]Shape[/tt] (rather than leaving it in only as a comment), it would be optional for [tt]Circle[/tt] and [tt]Rectangle[/tt] 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 [tt]DrawAShapeOverAndOver()[/tt]. [code] template void DrawAShapeOverAndOver(ShapeType* myShape) { for(int i=0; i<10000; i++) { myShape->DrawOutline(); // OR myShape->DrawFilled(); } } Rectangle *rectangle = new Rectangle; DrawAShapeOverAndOver(rectangle); delete rectangle; [/code] 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 [tt]GetRadius()[/tt]), the templated function will not compile if used with a class that does not have those member functions. For example, calling [tt]GetRadius()[/tt] on a [tt]Rectangle[/tt] 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 [tt]Rectangle[/tt], we can't do it through a pointer to a [tt]Shape[/tt]. In fact, there is no such thing as a pointer to a [tt]Shape[/tt], since there is no [tt]Shape[/tt] class without a template argument. This is less of a limitation than you might think. Take another look at our rewritten [tt]DrawAShapeOverAndOver()[/tt]: [code] template void DrawAShapeOverAndOver(ShapeType* myShape) { for(int i=0; i<10000; i++) { myShape->DrawOutline(); } } [/code] 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 [i]much[/i] 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.


      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.