Contents
Introduction
Template functions and classes tend to cause consternation amongst programmers. The conversation tends to go something like this:
- I understand the syntax of templates (although it’s ugly)
- I get the idea of replacing function-like macros with template functions
- I can see the application of template classes for containers
- Most containers and generic functions are library code
- I don’t write libraries
- What’s the point of me using templates?
In this article we’re going to look at an application of templates beyond writing library code – replacing run-time polymorphism (interfaces) with compile-time polymorphism. This idea is known as a Policy. The idea is reminiscent of the Strategy Pattern, but uses templates rather than interfaces.
I’m going to assume you already have an understanding of basic template syntax and semantics. If you’re a little rusty on these things look here and here for a refresher.
Setting the scene
In a multi-threaded environment it’s typical for threads to communicate asynchronously using First-In-First-Out message queues. (Don’t fret at this point about multi-threaded design; it’s the construction of the queue we’re going to worry about here, not how it would be used)
Because of the potential for race conditions within the queue (both threads trying to modify the queue ‘simultaneously’ – see here for a more detailed description) we should protect it with a mutual exclusion mechanism. For the purposes of this article we’ll deliberately keep the queue code simplistic (in other words: don’t try and use this queue in your production code!)
Here’s our first pass at the queue code:
For this example we’ve written the code as an adapter for the Standard Library queue class (using a variation of the Class Adapter Pattern). You can explore the semantics of template inheritance here if you’re not familiar with it.
The flexibility of our design is limited by the fact we have hard-coded a concrete Mutex object into the MessageQueue. This could be a serious penalty if:
- We want to port to a different operating system (perhaps with more efficient mutual exclusion mechanisms)
- We want to use the MessageQueue in non-threaded code, where we don’t want (or require) the overhead of locking/unlocking a Mutex object.
Let’s look at a couple of solutions that can improve our design.
An interface solution
Firstly, we want to de-couple our MessageQueue class from any particular Mutex implementation. The usual way to do that is via an Interface.
The MessageQueue has an association to the Interface; and we can substitute classes that realise the interface.
Here’s the code:
If you’re familiar with using Interfaces the code above should be very familiar. The association between the MessageQueue and the Interface is implemented as a pointer. The binding between a MessageQueue object and a (concrete) Mutex class is done during the construction of the MessageQueue.
Now we have a mechanism for dealing with our above problems.
If we move to a new OS we can substitute a new class that realises the I_Mutex interface. (You might want to consider using the Abstract Factory Pattern for this code to eradicate a host of conditional compilation).
For non-threaded code we may implement a ‘Null Mutex’ – that is, a concrete implementation with empty methods. These calls will typically be optimised away by the compiler to leave a sequential version of the MessageQueue, with no lock/unlock overheads.
However this flexibility comes at a cost. The run-time lookup for virtual functions requires additional code and data. Each dynamic polymorphic class requires a virtual table (v-table), and each object of that type a v-table pointer (vtptr). To call the polymorphic function the run-time system requires indexing into the v-table via the object’s vtptr to actually call the function. In certain environments this can be up to twice as slow as a normal function call.
The template policy
One of the benefits of Interfaces is that it allows substitution of implementation even at run-time. However, you have to ask: are you likely to replace your operating system during program run-time? Reasonably, you’re more likely to select the OS at compile time (like the example above) and not change it. Thus we are paying the price for flexibility we aren’t going to use.
Step up, templates.
One of the characteristics of templates is that they impose certain requirements on the types that can be used to instantiate the template. It could be particular attributes, but it’s more likely to be particular behaviours (for example, the need for types to support operator< if they want to be sorted in a container).
Let’s redefine our MessageQueue class using a template parameter to enforce a Policy: whatever type is used to instantiate the template must support the methods lock() and unlock(). The MessageQueue class is referred to as a host class
Please note, this is the only requirement we are demanding. There is no need to support any other methods, or realise an Interface; in fact, we’re even being pretty lenient on the parameters and return types of the functions.
We define our ‘policy’ when we instantiate the MessageQueue class by specifying the type of mutex implementation we want.
Notice in the above code the VxWorksMutex supports a far richer interface than required by our MessageQueue. This does not affect its usage in our code. In this example, the default timeout parameter is used for the calls to lock(); and the error return codes are ignored.
Since there are no interfaces or virtual functions in the template code all calls are statically-bound at compile time, meaning there is no overhead of virtual tables or v-table pointers.
Summary
Polymorphism is one of the cornerstones of building extensible, flexible software in C++. Dynamic polymorphism, via substitution, virtual functions and Interfaces provide a mechanism to enact this. However, that flexibility comes at a run-time cost.
Templates offer a similar flexibility – and in many ways even more flexibility – without the run-time overheads of dynamic polymorphism. The trade-off now is the fact that the flexibility is fixed at compile-time – what we might call Compile-Time polymorphism.
The purpose of Interfaces (and Policies) is to provide architectural flexibility in our systems by defining clear code ‘seams’ – points in the architecture where elements can be removed and replaced with minimal effort. Many of those seams are related to hardware or other system factors and will never be reconfigured during system operation. In such cases it makes sense to replace Interfaces with template policies to help improve the run-time performance of the code.
Next time, we’ll explore
He specialises in C++, UML, software modelling, Systems Engineering and process development.
- Practice makes perfect, part 3 – Idiomatic kata - February 27, 2020
- Practice makes perfect, part 2– foundation kata - February 13, 2020
- Practice makes perfect, part 1 – Code kata - January 30, 2020
Glennan is an embedded systems and software engineer with over 20 years experience, mostly in high-integrity systems for the defence and aerospace industry.
He specialises in C++, UML, software modelling, Systems Engineering and process development.
The best way to teach c++...covered not only templates and polymorphism but also design patterns...
very nice example ....Glen
Explained very well...not all in this field can do both! This was helpful. Thank you.