Angelika Langer - Training & Consulting
HOME | COURSES | TALKS | ARTICLES | GENERICS | LAMBDAS | IOSTREAMS | ABOUT | CONTACT | Twitter | Lanyrd | Linkedin
 
HOME 

  OVERVIEW

  BY TOPIC
    JAVA
    C++

  BY COLUMN
    EFFECTIVE JAVA
    EFFECTIVE STDLIB

  BY MAGAZINE
    JAVA MAGAZIN
    JAVA SPEKTRUM
    JAVA WORLD
    JAVA SOLUTIONS
    JAVA PRO
    C++ REPORT
    CUJ
    OTHER
 

GENERICS 
LAMBDAS 
IOSTREAMS 
ABOUT 
CONTACT 
Compile Time Computations in C++

Compile Time Computations in C++
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:

type template parameter
template < class PlaceHolderForType>
template < typename PlaceHolderForType>

non-type template parameter
template <NameOfType PlaceHolderForValue>

template template parameter
template < template < template_argument_list > class PlaceHolderForTemplate>

While template template parameters is a more exotic language feature, that few, if any, compilers support, non-type template parameters turned out to be quite useful in practice. Here is a classical example that demonstrates the use of type and non-type template parameters for definition of a fixed-sized buffer class: template <class T, int s>
class Buffer {
public:
  Buffer() : sz(s) {}
private:
  T v[s];
  int sz;
};

Buffer<char,127> cbuf;
Buffer<Record,8> rbuf;

The notion that a class can be parameterized by values, such as the buffer size in the example above, opens interesting design options. In principle, when a property shall be added to a given type of objects, then there are two options:
  • 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.
The first approach typically leads to so-called "fat" classes which can become a true maintenance nightmare, especially if more and more properties are added and the combination of property values explodes. The second approach leads to cleaner abstractions, where every type represents exactly one precisely defined concept.

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:

template<long p>
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;
}

The attempt to calculate "Xmas minus 5 minutes" would result in a compile time error message, because "Xmas" would be of type Ptime<day> , while "5 minutes" would be of type Ptime<minute> , and neither class has a diff() member function that accepts the other type of time value.

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.
Let's spend a few final thoughts on performance. The more computations can be performed at compile time already, the better will the run time behaviour be. With templates it is easy to have the compiler do much of the work. Just to give you some ideas:

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
 
Template Programming - All you ever wanted to know about templates
3 day seminar (open enrollment and on-site)
 

  © Copyright 1995-2003 by Angelika Langer.  All Rights Reserved.    URL: < http://www.AngelikaLanger.com/Articles/Papers/TemplateProgramming/Paper.htm  last update: 23 Oct 2003