| Angelika Langer - Training & Consulting |
|
|
| HOME | |
|
|
|
|
OVERVIEW
BY COLUMN
BY MAGAZINE
|
|
| GENERICS | |
| LAMBDAS | |
| IOSTREAMS | |
| ABOUT | |
| CONTACT |
Compile-Time Computations in C++
Novel Template Programming Techniques
Whitepaper, 2000
Angelika Langer
Using compile time computations in C++
Templates are known as a means to express parameterized types. True and useful, but C++ templates allow more than just that. Today, template programming has become a paradigm of its own. Compile-time polymorphism, generic programming, template meta-programming are only some of the buzz words in the field. Today, only few programmers exploit the full power of template features in C++.
Let us explore a couple of advanced template programming techniques that can replace corresponding object oriented idioms.
Parameterized Types
Traditionally, the template language feature is used for implementation of container classes such a stack for example. Typically, such a class template has the type of the contained elements as a template parameter. However, templates can not only be parameterized by types. Standard C++ also allows non-type template parameters and template template parameters. Below is sketch of the respective syntax for each of these argument categories:
template < class PlaceHolderForType>
template < typename PlaceHolderForType>
non-type template parameter
template
<NameOfType PlaceHolderForValue>
template template parameter
template
<
template
<
template_argument_list
>
class
PlaceHolderForTemplate>
class Buffer {
public:
Buffer() : sz(s) {}
private:
T v[s];
int sz;
};
Buffer<char,127> cbuf;
Buffer<Record,8> rbuf;
- The property can be added to the state of each object, that is, the existing type is extended by adding another data member that represents the new property. As a result, objects with and without the new property are exchangeable because they are of the same type.
- Alternatively, new types can be defined in addition to the existing type, so that the new property would be reflected by the type of the object, not by its state. The effect is that objects with and without the new property are not exchangeable because they are of the distinct type.
If the latter approach is the design option of choice then non-type template arguments often help to express the design. The new types, that must be defined, can be generated from a class template that has the new property as a non-type template argument.
Let's explore a trivial example for illustration. Imagine we had a class time that represents time values, say, internally stored as seconds since 1.1.1970. These can be points in time like "now", expressed in seconds since 1.1.1970, but also periods of time like "5 seconds". Part of the time package is a function diff() that calculates the difference between two time values.
Next, we are instructed to extend the time type by adding a precision: time values shall be measured not only in seconds, but also in minutes, days, years, etc. The goal is that we can also express values like "today" or "Xmas" or "half an hour". How do we design this extension?
One design option is to add a precision data member to the time class. If we take that approach, we must also figure out what the diff() function should do in case that it is provided with two time values of different precision. What is the difference between "Xmas" and "5 minutes"? Sure, we can find a way to give "Xmas minus 5 minutes" a halfway reasonable meaning. We could also argue that this is not a reasonable thing to do and alternatively decide that the attempt to calculate the difference between to time values of different precision is always an error. In that case, the diff() function would have to examine the precision data member each time it is invoked and would raise an exception if necessary.
The time class is an admittedly trivial class, but this contrived example already shows that we create run-time overhead by adding a property, such as the precision, to the state of each object. In our example, the overhead is the check for identical precision and the resulting error handling.
Another design option is to add the precision to the type of the time value, that is, we would define new types for time values measured in minutes, days, years, etc.
With this design, the issue of "Xmas minus 5 minutes" can be solved easily by turning the diff() function into a function template. For each type of time value another diff() function would be generated and each such function would take two arguments of identical type. As a result, only time values with the same precision can be used for calculating time differences. Here is the sketch of a suggested implementation:
class PTime {
public:
PTime<p>();
PTime<p>(long sec) : Time(sec);
TUnit diff(const PTime<p>& rhs)
{ return ((_t/p) - (rhs._t/p)); }
private:
long _t;
};
const long second = 1;
const long minute = 60 * second;
// ... and so on ...
void main()
{
PTime<minute> pt1;
PTime<minute> pt2(time(NULL)
- 2*hour);
cout << "diff is: "
<< pt1.diff(pt2) << endl;
}
Note, that this solution does not create any run-time overhead. The check for identical precision is performed at compile-time, because we expressed the new property, the precision, in terms of types rather than in terms of object state. Type information can be used at compile-time, object state must always be processed at run-time. Moreover, the diff() function is relatively trivial and has a good chance to be inlined, whereas under the alternative design the diff() function inevitably has a higher complexity, which impairs its performance.
This trivial case study illustrates two things:
- Often we have the choice between expressing a property in terms of type information or in form of object state. More often than necessary the second option is chosen, although properly designed types often result in clearer abstractions.
- When information is contained in the type already, rather than in the object state, compile-time computations can be performed, such as the error detection in our example. In general, properly designed "lean" types have a great potential for better run time characteristics.
Compile time polymorphism . Template programming in C++ facilitates function dispatch at compile time using function templates. In object-oriented theory, polymorphic behaviour is implemented by means of virtual member functions, which are dispatched at run time using the virtual function table mechanism. The exact same thing can be achieved using function templates in which case the compiler performs the function dispatch at run time.
Compile time policy mix-ins . Template programming in C++ allows specification of policies (or strategies) at compile time. In classic C++ policies are often provided as function pointers; different comparison functions might be supplied to a sort function as an argument, for instance. The same effect can be achieved using templates where the policy can be specified at compile time, thus eliminating run time overhead entirely.
Compile time computations . The template instantiator evaluates templates recursively. This behaviour can be used to compute values or to evaluate expressions at compile time. Practical examples include evaluation of vector dot product or matrix operations, or calculation of the square root at compile time.
In sum, template programming in C++ has a lot more to
offer than just parameterized types. In the process of standardisation
the template language feature was enhanced and refined, numerous features
were added such as template specialisation, explicit function template
argument specification, function template overloading, etc. As a result,
we nowadays can often choose between compile-time and run-time computations.
We are not limited to object oriented programming and its bias towards
run-time computations any longer. A whole new programming paradigm - generic
programming - emerged and has already found its way into the software shops.
The STL, which is a major part of the standard C++ library, is an exemplary
implementation of generic programming. Multi-paradigm programming in C++
has become reality.
If you are interested to hear more about this and related topics you might want to check out the following seminar: |
||
Seminar
|
||
URL:
<
http://www.AngelikaLanger.com/Articles/Papers/TemplateProgramming/Paper.htm>
last update: 23 Oct 2003