PHP Compile-time class generation for loop unrolling

AceInfinity · Mar 6, 2015

So, this may be a bit more complex than most intermediate C++ programmers are used to, but I'm going to provide an example of template metaprogramming used for compile-time class generation for optimizing code and allowing loop unrolling in this case.

Code:

[NO-PARSE]#include <iostream>
#include <vector>

template <typename T, int length>
struct vec
{
  vec(std::vector<T> &v) : data(&v) { }
  std::vector<T> &values() const { return *data; }
  std::vector<T> *data;
};

template <typename T, int length>
vec<T, length> &operator+=(vec<T, length> &lhs, const vec<T, length> &rhs)
{
  for (int i = 0; i < length; ++i)
    lhs.values() += rhs.values();
  return lhs;
}

int main()
{
  std::vector<int> v = { 1, 2, 3 };

  // check contents of v beforehand
  std::cout << "Contents of 'v':\n\t";
  for (const auto &it : v)
    std::cout << it << ' ';
  std::cout << '\n';

  vec<int, 3> obj(v); // construct a object grabbing pointer from v
  obj += obj; // add object constructed from v2 to previous object

  // values contained within vector pointed to within obj
  std::cout << "Contents of dereferenced 'obj' internal pointer:\n\t";
  for (const auto &it : obj.values())
    std::cout << it << ' ';
  std::cout << '\n';

  // values contained within v
  std::cout << "Contents of 'v':\n\t";
  for (const auto &it : v)
    std::cout << it << ' ';
  std::cout << '\n';

}[/NO-PARSE]

Here we define a vector from the STL as a type of int within main, and we have a helper object which contains a pointer to some typeof std::vector<T>, along with an internal helper function to return a reference to this dereferenced object pointer. This may seem redundant right now, but I'll get to the purpose soon.

Next we have an overloaded operator (combinational), for this user-defined struct which adds and assigns the result of the 2 vec<T, int> objects being added together element by element. The T can be inferred by means of type deduction, it's the length parameter which causes issues here if we were to try and add these objects together dynamically, but the whole point of compile-time code is not to be dynamic, but to have values that are known during compile time so that the compiler can generate optimized code to return a result, without having to calculate this value at runtime.

Our main() functiond demonstrates code in which displays the contents of the std::vector beforehand to show that it's values remain the same as what it is instantiated with via the brace-initializer list. Next you'll see that we create an object of vec by passing in 'v' as an argument to the constructor--this constructor takes the address of 'v' and assigns it to the internal pointer within this object ('data'), and the type being pre-defined as int, along with a length of 3 being templated as well.

obj += obj, is where the magic begins. The overloaded operator is called to add the left operand to the right, and assign to the original object (the left operand). Because the overloaded operator operates on the dereferenced pointer, at this point the contents of the original std::vector (, the one that we passed in as a param to the constructor for the vec object,) is now changed, and this is shown by the last 2 range for loops at the end of main().

What's so special about this? 2 things:

1. The compiler can now specialize the overloaded operator with a length of 3 and of type int for generated code at compile time.
2. Because both template arguments are known at compile-time, the compiler can substitute that for loop with some other code and essentially unroll this. The resulting code may look something similar to that of:

Code:

[NO-PARSE]template <> vec<int, 3> &operator+=(vec<int, 3> &lhs, const vec<int, 3> &rhs) { /* loop unrolling */ lhs.values()[0] += rhs.values()[0]; lhs.values()[1] += rhs.values()[1]; lhs.values()[2] += rhs.values()[2]; return lhs; }[/NO-PARSE]

Note: The C++11 constexpr keyword simplifies a lot of this kind of coding, as template metaprogramming is not really something common in terms of familiarity of syntax for most programmers. I do think that understanding how it works though, and how constexpr simplifies this task, is very important to being able to use the constexpr keyword appropriately however!

Search

Search

PHP Compile-time class generation for loop unrolling

AceInfinity

Emeritus, Contributor