Is Template Metaprogramming faster than the equivalent C code?

Question

Is Template Metaprogramming faster than the equivalent C code ? ( I'm talking about the runtime performance) :)

Answer 1

First, a disclaimer: What I think you're asking about is not just template metaprogramming, but also generic programming. The two concepts are closely related, and there's no exact definition of what each encompasses. But in short, template metaprogramming is essentially writing a program using templates, which is evaluated at compile-time. (which makes it entirely free at runtime. Nothing happens. The value (or more commonly, type) has already been computed by the compiler, and is available as a constant (either a const variable, or an enum), or as a typedef nested in a class (if you've used it to "compute" a type).

Generic programming is using templates and when necessary, template metaprogramming, to create generic code which works the same (and with no loss in performance), with all and any type. I'm going to use examples of both in the following.

A common use for template metaprogramming is to enable types to be used in generic programming, even if they were not designed for it.

Since template metaprogramming technically takes place entirely at compile-time, your question is a bit more relevant for generic programming, which still takes place at runtime, but is efficient because it can be specialized for the precise types it's used with at compile-time.

Anyway...

---

Depends on how you define "the equivalent C code".

The trick about template metaprogramming (or generic programming in general) is that it allows a lot of computation to be moved to compile-time, and it enables flexible, parametrized code that is just as efficient as hardcoded values.

The code displayed here for example computes a number in the fibonacci sequence at compile-time.

The C++ code 'unsigned long fib11 = fibonacci<11uL>::value', relies on the template metaprogram defined in that link, and is as efficient as the C code 'unsigned long fib11 = 89uL'. The templates are evaluated at compile-time, yielding a constant that can be assigned to a variable. So at runtime, the code is actually identical to a simple assignment.

So if that is the "equivalent C code", the performance is the same. If the equivalent C code is "a program that can compute arbitrary fibonacci numbers, applied to find the 11th number in the sequence", then the C version will be much slower, because it has to be implemented as a function, which computes the value at runtime. But this is the "equivalent C code" in the sense that it is a C program that exhibits the same flexibility (it is not just a hardcoded constant, but an actual function that can return any number in the fibonacci sequence).

Of course, this isn't often useful. But it's pretty much the canonical example of template metaprogramming.

A more realistic example of generic programming is sorting.

In C, you have the qsort standard library function taking an array and a comparator function pointer. The call to this function pointer can not be inlined (except in trivial cases), because at compile-time, it is not known which function is going to be called.

Of course the alternative is a hand-written sorting function designed for your specific datatype.

In C++, the equivalent is the function template std::sort. It too takes a comparator, but instead of this being a function pointer, it is a function object, looking like this:

struct MyComp {
  bool operator()(const MyType& lhs, const MyType& rhs) {
     // return true if lhs < rhs, however this operation is defined for MyType objects
  }
};

and this can be inlined. The std::sort function is passed a template argument, so it knows the exact type of the comparator, and so it knows that the comparator function is not just an unknown function pointer, but MyComp::operator().

The end result is that the C++ function std::sort is exactly as efficient as your hand-coded implementation in C of the same sorting algorithm.

So again, if that is "the equivalent C code", then the performance is the same. But if the "equivalent C code" is "a generalized sorting function which can be applied to any type, and allows user-defined comparators", then the generic programming-version in C++ is vastly more efficient.

That's really the trick. Generic programming and template metaprogramming are not "faster than C". They are methods to achieve general, reusable code which is as fast as handcoded, and hardcoded C

It is a way to get the best of both worlds. The performance of hardcoded algorithms, and the flexibility and reusability of general, parameterized ones.

Answer 2

Template Metaprogramming (TMP) is 'run' at compile time, so it's not really comparing apples to apples when comparing it to normal C/C++ code.

But, if you have something evaluated by TMP, then there's no runtime cost at all.

Answer 3

If you mean reusable code, then yes without a doubt. Metaprogramming is a superior way to produce libraries, not client code. Client code is not generic, it is written to do specific things.

For example, look at the qsort from C standard library, and C++ standard sort. This is how qsort works :

int compare(const void* a, const void* b)
{
    return (*(int*)a > *(int*)b);
}

int main()
{
    int data[5] = {5, 4, 3, 2, 1};

    qsort(data, 5, sizeof(int), compare);
}

Now look at sort :

struct compare
{
    bool operator()(int a, int b)
    { return a < b; }
};

int main()
{
    int data[5] = {5, 4, 3, 2, 1};
    std::sort(data, data+5, compare());
}

sort is cleaner, safer and more efficient because the comparison function is inlined inside the sort. That is the benefit of metaprogramming in my opinion, you write generic code, but the compiler produce code like the hand-coded one!

---

Another place where I find metaprogramming very beautiful is when you write a library like boost::spirit or boost::xpressive, with spirit you can write EBNF inside C++ and let the compile check the EBNF syntax for you and with xpressive you can write regex and let the compiler check the regex syntax for you also!

---

I am not sure if the questioner means by TMP calculating values at compile time. This is an example I wrote using boost :)

unsigned long greatestCommonDivisor = boost::math::static_gcd<25657, 54887524>::value;

What ever you do with C you can't mimic the above code, basically you have to hand-calculate it then assign the result to greatestCommonDivisor!

Answer 4

The answer is it depends.

Template metaprogramming can be used to easily write recursive descent language parsers and these can be inefficient compared to a carefully crafted C program or a table-based implementation (e.g. flex/bison/yacc).

On the other hand, you can write metaprograms that generate unrolled loops which can be more efficient than a more an conventional C implementation that uses loops.

The main benefit is that metaprograms allow the programmer to do more with less code.

The downside is that it also gives you a gatling gun to shoot yourself in the foot with.

Answer 5

Template metaprogramming can be thought of as compile-time execution.

The compile-time is going to take longer to compile your code since it has to compile and then execute the templates, generate code, then compile again.

The run-time overhead I am not sure about, it shouldn't be much more than if you wrote it yourself in C code I would imagine.

Answer 6

I worked on a project where another programmer had tried out metaprogramming. It was terrible. It was a complete headache. I'm an average programmer with a lot of C++ experience, and trying to devise what the hell they were trying to do took way more time than if they had written it straight out to begin with.

I'm jaded against C++ MetaProgramming because of this experience.

I'm a firm believer that the best code is most easily readable by an average developer. It's the readability of the software that is the #1 priority. I can make anything work using any language... but the skill is in making it readable and easily workable for the next person on the project. C++ MetaProgramming fails to pass muster.

Answer 7

I do not think there is any hype, but a clear and simple answer about templates is given by C++ FAQ: https://isocpp.org/wiki/faq/templates#overview-templates

About the original question: it cannot be answered, as those things are not comparable.

Answer 8

Template metaprogramming does not give you any magical powers in terms of performance. It's basically a very sophisticated preprocessor; you can always write the equivalent in C or C++, it just might take you a very long time.