Compile Time Constants Part 2: Compile Time Calculations

I have written about what we need compile time constants for last week. This time I will dig a bit into where we can get compile time constants from, and how we can do compile time calculations. 

Sources of compile time constants

Most examples in the last post used some kind of literals or enumerators. Think of `Answer<42ul, ‘d’, BLUE> theAnswer;` Where I used an integer literal, a character literal and the enumerator `BLUE` of the enum `Color`.

In general, any literals that are not user defined are constant expressions. A constant expression is an expression that has a value that can be calculated at compile time. It is not guaranteed to be calculated at compile time unless it is used in a context that requires compile time evaluation.

Another source for constants is the builtin `sizeof` operator. The compiler knows at compile time how much memory an object of a given class will occupy. Therefore this value can easily be used as a compile time constant as well.

int i = 42;
unsigned char buffer[sizeof(i)] = {};

Of course constant variables with values that are known at compile time are also – well – compile time constants.

class Dalmatian {
  //...
};
int const count = 101;
Dalmatian theMovie[count] = { /* ... */};

Constant variables can appear in several different locations. Probably the most used locations are static class variables. A variant that has been used in the past due to issues with static variables in some compilers are enums in classes:

struct SomeStruct {
  static unsigned const size1 = 44;
  enum { size2 = 45 };
  int someIntegers[size1];
  double someDoubles[size2];
};

Compile time calculations

As the term “constant expression” suggests, we are not restricted to literals and enumerators. We can do all sorts of compile time calculations. In fact, there is not much we can not do if we compose our expressions of subexpressions that are known at compile time themselves.

We can use some pretty simple calculations, e.g.

int const count = 47;
unsigned char buffer[ count * sizeof(double) ] = {};

There are many operators we can use, e.g. consider this nasty piece of code:

std::string nonsense(char input) {
  switch (input) {
  case "foobar"[(sizeof(void*) == 4) ? 0 : 1]:
    return "beef";
  default:
    return "lettuce";
  }
}

This first case mark does not make much sense, but it actually compiles. What does it do? Well, the innermost nontrivial expression we can see is `sizeof(void*) == 4`. This is simply a check if we are compiling for a 32 bit system. It is the first argument for the ternary operator.

The result of that ternary operator will be `0` for 32 bit systems, `1` otherwise. It is passed to the array index operator which is applied to the string literal `”foobar”`. So this first case label is `’f’` for 32 bit systems, `’o’` for other systems.

Besides the obvious nonsensical logic going on there, you can also see that this is barely readable. Thanks to constant variables we can improve the readability like this:

std::string nonsense(char input) {
  auto const index = (sizeof(void*) == 4) ? 0 : 1;
  auto const beefCase = "foobar"[index];
  switch (input) {
  case beefCase:
    return "beef";
  default:
    return "lettuce";
  }
}

Using templates for compile time calculations

I wrote earlier that integral constants can be used as template parameters. Together with the possibility of having const static class members as compile time constants, we get the possibility of writing templates that serve as functions for compile time calculations.

Here’s an example for a template meta function that calculates Fibonacci numbers:

template <unsigned N> 
struct Fibonacci;

template <>
struct Fibonacci<0> {
  static unsigned const value = 0;   
};

template <>
struct Fibonacci<1> {
  static unsigned const value = 1;   
};

template <unsigned N> 
struct Fibonacci {
  static unsigned const value = Fibonacci<N-1>::value + Fibonacci<N-2>::value;
};

The last template is the interesting one: It instantiates recursively the two versions with lower `N`. The recursion ends on the two specializations for 0 and 1.

This kind of template meta programming may look rather complicated and wordy. It was however the only way to do more complex compile time calculations before C++11 arrived. It has been proven to be Turing complete in theory, however compilers usually have a maximum template instantiation depth to avoid endless instantiation loops.

Conclusion

There are amazing things that can be done at compile time, even in C++03. Remember that compile time calculations can save runtime execution time and memory.

In C++11/14 we did not only get variadic templates which allow for even more complex metaprogramming techniques but also so-called generalized constant expressions aka `constexpr`. I’ll write an introduction to those next week.

Facebooktwittergoogle_plusredditlinkedinFacebooktwittergoogle_plusredditlinkedinby feather
Posted in

7 Comments




  1. Björn Fahller

    A few errors this time.

    The ‘Dalmatians’ example won’t compile, since you cannot define an array of a forward declared type. Use ‘class Dalmatian{};’ to define it.

    sizeof(void*) will not be 32 on a 32-bit system. It will almost certainly be 4, given that CHAR_BITS (or std::numeric_limits::digits()) == 8.

    Reply
    1. Arne Mertz

      Thanks for the hints. I probably was dreaming too much of the Canary Islands writing that post 😉

      Reply

  2. Remember compile time calculations can waste compile time and/or link time 😉

    Reply
    1. Arne Mertz

      Of course they do cost compile time. They waste the time only if they are unnecessary. As almost always it’s a tradeoff. Compile time cost vs. run time cost or memory or maintenance or other costs.

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *