Calculation at compile-time by help of constant expression

Introduction

Some time ago I have posted article about calculation at compile-time by help of templates. I must say that such method is huge, but helpful. Everything what I said is based on C++98 standard, but I think you have already heard about C++11 standard. At least I have mentioned it a couple of times in my previous articles.

This standard has some good stuff for you which helps to write compile-performed code without templates. It has name constexpr and is a shortening of constant expression.

Today I will use this one from C++11 and write similar code as before, but much smaller. Yep, I will re-implement calculation of my mathematics series at compile-time in a more elegant way. Let's see.

New keyword constexpr

or mark for compiler

As in previous time I'm beginning with an example of factorial calculation. Now it resembles a regular recursive implementation of factorial. Take a look at the following code:

constexpr int FactorialExpr(int number)
{
 return number == 0 ? 1 : number * FactorialExpr(number-1);
}

Last time it took approximately 18 lines. Currently you see 4 lines (yes, I counted brackets) and it has only one new thing for you: a constexpr keyword. This keyword is a hint for compiler that result of this function can be evaluated at compile-time. It has some usage restrictions, but will'll discuss them later. Let's see how we can use it at first.

Probably some of you will write the following code:

void SomeFunc()
{
 int value = FactorialExpr(4);
}

and will expect assignment of result of calculation a factorial to value variable at compile-time. I want to look under the hood into an assembler code of such function. Don't worry it won't hurt you. I will add some comments for better understanding. My compiler generates the following assembler instructions for SomeFunc:

# Create a variable on stack.
push %rbp
mov %rsp,%rbp
sub $0x10,%rsp

# Put 4 in register for the first argument of function.
mov $0x4,%edi

# There is an explicit call of FactorialExpr function!
callq 0x400781 <FactorialExpr(int)>

# Write result of FactorialExpr to variable on stack.
mov %eax,-0x4(%rbp)

# Free resources on stack and return from SomeFunc.
leaveq
retq

Wait a minute... We were expecting that everything would be calculated at compile-time and to see just the result generated assembly, but we see that calculation will be performed at run-time. If you try to debug this code, you will be able to enter in FactorialExpr() function and see calculation. Do you think I lied when said about calculation at compile-time?

Of course no. Check out the correct code:

void SomeFunc()
{
 constexpr int value = FactorialExpr(4);
}

and assembly code now looks like the following:

# Create a variable on stack.
push %rbp
mov %rsp,%rbp

# Set 0x18 in hex (24 in dec) to the variable on stack.
movl $0x18,-0x4(%rbp)

# Free resources on stack and return from SomeFunc.
pop %rbp
retq

Do you see this? There is no call of FactorialExpr function. Here is just putting ready result to the variable. Really factorial of 4 is 24, which we see in the assembly code. We got this when we added constexpr keyword for the variable.

So at the moment we know that constexpr can be used for functions and variables and they interact. It is time to say about rules of this keyword.

Rules of constexpr

Let's begin with the simplest - using constexpr for variables. It has the following rules:

the variable must be immediately constructed or assigned a value;
the constructor parameters or the value to be assigned must contain constexpr variables;
the constructor parameters or the value to be assigned must contain constexpr functions;
the constructor used to construct the object must satisfy the requirements of constexpr constructor (I will write about this further).

Before describing of constexpr functions I need to give definition of literal type. It can be:

scalar type (bool, short, int, double, pointers, etc.);
reference type;
an array of literal type;
class type that has all of the following properties:
- has a trivial destructor (destructor that performs no action);
- is either an aggregate type or a type with at least one constexpr constructor that is not a copy or move constructor;
- all non-static data members and base classes are of non-volatile literal types.

OK, now you are ready to see rules for functions\methods with constexpr keyword:

it must not be a virtual method;
its return type must be a literal type;
each of its parameters must be a literal type;
the function body can contain:
- static_assert declarations;
- typedef declarations and alias declarations that do not define classes or enumerations;
- using declarations or directives;
- exactly one return statement that contains only literal values, constexpr variables and functions.

There is harder story with constexpr constructors. Constructor of class can be declared with constexpr like function as well, but with following additional rules:

the class must have no virtual base classes;
the constructor must not have a function-try-block;
body of the constructor can have only: null statements, static_assert declarations, typedef declarations, using declarations and directives;
every base class and every non-static member must be initialized, either in the constructor's initialization list or in place of declaration.

As you see constexpr can be used for simple situations needed for evaluating code at compile-time. C++14 standard expands possible actions with constexpr, but for me it is enough to rewrite calculation of mathematics series from my previous article with C++11.

Re-implementing calculation of mathematics series

We already have implementation of factorial, now it is turn of exponentiation. As with factorial thanks to constexpr it is very easy:

constexpr int PowerExprImpl(int base, int degree, int multiply_adder)
{
 return degree == 0 ?
   multiply_adder :
   PowerExprImpl(base, degree -1 , base * multiply_adder);
}

constexpr int PowerExpr(int base, int degree)
{
 return PowerExprImpl(base, degree, 1);
}

As in previously I have written a wrapper for hiding start state of variable that keeps serial multiplying base on its value "degree" times. I don't think that there is something to review more, because there is elementary realization by recursive calls of PowerExprImpl function. Now we can write code for calculation of single series:

constexpr double SingleSerieExpr(int x, int n)
{
 return PowerExpr(x,n) / static_cast<double>(FactorialExpr(n));
}

Here we just call other constexpr function and divide each other with casting from int to double to prevent losing of necessary information.

For implementing mathematics series we need an accumulator. There it is:

constexpr double AccumulateExpr(double (*func) (int, int) , int value, int i)
{
 return i == 1 ?
   func(value, i) :
   func(value, i) + AccumulateExpr(func, value, i-1);
}

There is one unusual thing – the first argument of the function. It is a pointer to function and it can be used in constexpr function because pointer is a scalar type. If you don't know syntax of such pointers in C++, you can read about this here.

Now we have everything what we need to finish implementation of the calculation. Get into this:

constexpr double CalcMathematicsSeriesExpr(int value, int count)
{
 return AccumulateExpr(&SingleSerieExpr, value, count);
}

void MathematicsSeriesCompileTime()
{
 constexpr double value = CalcMathematicsSeriesExpr(2, 3);
}

Here &SingleSerieExpr is getting of function address which I have mentioned above. The rest is a wrapper with call of the accumulator with correct arguments and usage of wrapper with some data.

If you look at an assembler code of MathematicsSeriesCompileTime(), you will see something like this:

# Create a variable on stack.
push %rbp
mov %rsp,%rbp

# $0x4015555555555555 is a representation of 5.3333
# what is a result of calculation.
movabs $0x4015555555555555,%rax

# Write result to variable on stack.
mov %rax,-0x8(%rbp)

# Free resources on stack and return from MathematicsSeriesCompileTime.
pop %rbp
retq

You see? We get same results as we did it with help of templates in previous article[link here], but this time our implementation is more understandable for programmer. Thanks to new constexpr keyword from C++11 standard.

Conclusion

Calculation at compile-time by usage of templates is great, but in such case programmer writes code which is hard to understand for other programmers. Such implementation can be huge and bulky. C++11 standard has pretty cool instrument for avoiding this. It has name constexpr, which means constant expression. In this article I have described rules of usage this keyword and abused my previous implementation for calculation of mathematics series by writing small and clear code with constexpr. So if your compiler supports C++11, it is an awesome practice to use new constexpr keyword with the Force.

My previous articles from “.CPP files” series are: