Write faster code with C++ Expression Templates for optimized compile-time evaluation

Deprecated since C++20. Use std::ranges instead.

Source: https://unsplash.com/photos/wl5AypUmamo

Write code that saves your time and space with expression templates. Expression templates are used heavily in Linear Algebra libraries for compile-time evaluation.

What are templates?

Templates are used for generic programming in C++. Templates allow us to define Classes and functions which are type independent(of int, double, or even classes) which perform similar operations. The type is either explicitly specified or deduced at compile time.

Consider the below code to square two elements:

The above code can be simplified into:

Now square accepts doubles, int and floats as well as any class object.

PS: Of course the program will run successfully only if * operation is defined for the class.

Expression Template Metaprogramming

Expression Templating is the name of the optimization technique which reduces overhead computation space using lazy evaluation.

This is used heavily in most of the linear algebra libraries.

What is lazy evaluation?

The process of delaying an evaluation until the value of that process is required. Consider the following:

v = x*x + y*y;
std::cout << v[2];

Here x and y are vectors. The problem with naïve approaches is that it increases the computation time spent in computing the entire of vector when the only required value is that of v[2].

Naïve Approach

First we overload the operators + and * for std::vector so that we can write v3=v1+v2 and v3=v1*v2;

Here, we use operator keyword and define a function like entity that takes two vectors and returns pairwise sum. Should probably add a check for size of vectors.

Let’s do the same for operator * .

Simple replaced + with *.

Now we can write:

The output is 45.

The problem is the wasted space every time x * x, y * y and their sum. More efficient way of calculating(in this case) would be (x[2]*x[2]) + (y[2]*y[2]), but doing this impractical in most cases where n is much greater.

Expression Templates to the rescue

Before we get down to expression templates we will define a wrapper class for std::vector. We will get down to why we are doing this later.

In the above code, we define a class view_vec_add which lets us chain vector addition without complete evaluation.

Well, it looks like gibberish, so let’s break it down.

The class view_vec_add has two private variables. Keep in mind that &l and &r are templates. Meaning their types will get instantiated at runtime.

And next, we overload the operator[] to return us the of left and right.

If I were to call a addition on two vectors, the sum is only calculated of the index on which the operator is called.

Let’s look at the following code and see how:

In the above instead of doing a loop and calculating sum of entire vector, only v[2] is calculated.

In the above code v now has value stored of ((x + y) + x) and the only evaluation takes place when we call the operator[].

This saves both time and space.

This is where the magic happens. Now in calling x+y+x, we do not have copies of data of (x+y) or (x+y)+x. The value is yet to be found, but we have stored references to those values, and we calculate only those numbers that we require of.

Some Note

You can ignore this part but it might help in better understanding. This is how to compiler evaluates the expressions.

Another thing here, the type of v here is vec_view_add<vec_view_add<std::vector<int>,std::vector<int>>,std::vector<int>>

How, so? Here, (vec_view_add(x,y) evaluates to vec_view_add<std::vector<int>,std::vector<int>> with [Left=std::vector<int> && Right=std::vector<int>].

This expression is then passed as Left template again to vec_view_add with Right as std::vector<int>

Now we can do the same for dot product and overload operators.

Entire Code:

Can you guess the type of v now?

About me:

My Website: http://aniketbiprojit.me/

Other Articles: https://medium.com/@aniketbiprojit/practical-federated-learning-76dd2034b1b0