compile time loops

Question

I would like to know if it is possible to have sort of compile time loops.
For example, I have the following templated class:

template<class C, int T=10, int B=10>
class CountSketch
{
public:
    CountSketch()
    {   
         hashfuncs[0] = &CountSketch<C>::hash<0>;
         hashfuncs[1] = &CountSketch<C>::hash<1>;
         // ... for all i until i==T which is known at compile time
    };
private:
    template<int offset>
    size_t hash(C &c)
    {
        return (reinterpret_cast<int>(&c)+offset)%B;
    }
    size_t (CountSketch::*hashfuncs[T])(C &c);
};

I would thus like to know if I can do a loop to initialize the T hash functions using a loop. The bounds of the loops are known at compile time, so, in principle, I don't see any reason why it couldn't be done (especially since it works if I unroll the loop manually).

Of course, in this specific example, I could just have made a single hash function with 2 parameters (although it would be less efficient I guess). I am thus not interested in solving this specific problem, but rather knowing if "compile time loops" existed for similar cases.

Thanks!

Answer 1

Nope, it's not directly possible. Template metaprogramming is a pure functional language. Every value or type defined through it are immutable. A loop inherently requires mutable variables (Repeatedly test some condition until X happens, then exit the loop).

Instead, you would typically rely on recursion. (Instantiate this template with a different template parameter each time, until you reach some terminating condition).

However, that can solve all the same problems as a loop could.

Edit: Here's a quick example, computing the factorial of N using recursion at compile-time:

template <int N>
struct fac {
  enum { value = N * fac<N-1>::value };
};

template <>
struct fac<0> {
  enum { value = 1 };
};

int main() {
  assert(fac<4>::value == 24);
}

Template metaprogramming in C++ is a Turing-complete language, so as long as you don't run into various internal compiler limits, you can solve basically any problem with it.

However, for practical purposes, it may be worth investigating libraries like Boost.MPL, which contains a large number of data structures and algorithms which simplify a lot of metaprogramming tasks.

Answer 2

Yes. Possible using compile time recursion.

I was trying with your code but since it was not compilable here is a modified and compiling exmaple:

template<class C, int T=10>
class CountSketch
{
  template<int N>
  void Init ()
  {
    Init<N-1>();
    hashfuncs[N] = &CountSketch<C>::template hash<N>;
    cout<<"Initializing "<<N<<"th element\n";
  }

public:
    CountSketch()
    {
      Init<T>();
    }
private:
   template<int offset>
   size_t hash(C &c)
   {
     return 0;
   }
   size_t (CountSketch::*hashfuncs[T])(C &c);
};

template<>
template<>
void CountSketch<int,10>::Init<0> ()
{
  hashfuncs[0] = &CountSketch<int,10>::hash<0>;
  cout<<"Initializing "<<0<<"th element\n";
}

Demo. The only constraint of this solution is that you have to provide the final specialized version as, CountSketch<int,10>::Init<0> for whatever type and size.

Answer 3

You need a combination of boost::mpl::for_each and boost::mpl::range_c.

Note: This will result in run-time code and this is what you actually need. Because there is no way to know the result of operator& at compile time. At least none that I'm aware of.

The actual difficulty with this is to build a struct that is templated on an int parameter (mpl::int_ in our case) and that does the assignment when operator() is called and we also need a functor to actually capture the this pointer.

This is somewhat more complicated than I anticipated but it's fun.

#include <boost/mpl/range_c.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/mpl/copy.hpp>

// aforementioned struct
template<class C, class I>
struct assign_hash;

// this actually evaluates the functor and captures the this pointer
// T is the argument for the functor U
template<typename T>
struct my_apply {
  T* t;
  template<typename U>
  void operator()(U u) {
    u(t);
  }
};

template<class C, int T=10, int B=10>
class CountSketch
{
public:
  CountSketch()
    {   
      using namespace boost::mpl;

      // we need to do this because range_c is not an ExtensibleSequence
      typedef typename copy< range_c<int, 0, T>,
                             back_inserter< vector<> > >::type r;
      // fiddle together a vector of the correct types
      typedef typename transform<r, typename lambda< assign_hash<C, _1 > >::type >
        ::type assignees;

      // now we need to unfold the type list into a run-time construct
      // capture this
      my_apply< CountSketch<C, T, B> > apply = { this };
      // this is a compile-time loop which actually does something at run-time
      for_each<assignees>(apply);
    };

  // no way around
  template<typename TT, typename I>
  friend struct assign_hash;

private:
  template<int offset>
  size_t hash(C& c)
    {
      return c;
      // return (reinterpret_cast<int>(&c)+offset)%B;
    }
  size_t (CountSketch::*hashfuncs[T])(C &c);
};

// mpl uses int_ so we don't use a non-type template parameter 
// but get a compile time value through the value member
template<class C, class I>
struct assign_hash {
  template<typename T>
  void operator()(T* t) {
    t->hashfuncs[I::value] = &CountSketch<C>::template hash<I::value>;
  }
};

int main() 
{
  CountSketch<int> a;
}

Answer 4

with C++20 and consteval compile time loops became possible without doing template hell unless the value can have multiple types:

consteval int func() {
    int out = 0;
    for(int i = 10; i--;) out += i;
    return out;
}
int main() {
    std::cout << func(); // outputs 45
}

Answer 5

Here is, I think, a better version of the solution given above.
You can see that we use the compile-time recursive on the function params.
This enables putting all the logic inside your class, and the base case of Init(int_<0>) is very clear - just do nothing :)
Just so you won't fear performance penalty, know that the optimizer will throw away these unused parameters.
As a matter of fact, all these function calls will be inlined anyway. that's the whole point here.

#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

template <class C, int N = 10, int B = 10>
class CountSketch {
 public:
  CountSketch() {
    memset(&_hashFunctions, sizeof(_hashFunctions), 0); // for safety
    Init(int_<N>());
  }

  size_t HashAll(C& c)
  {
      size_t v = 0;
      for(const auto& h : _hashFunctions) 
      {
        v += (this->*h)(c); // call through member pointer
      }
      return v;
  }

 private:
    template<int offset>
    size_t hash(C &c)
    {
        return (reinterpret_cast<size_t>(&c)+offset)%B;
    }

  size_t (CountSketch::*_hashFunctions[N])(C &c);

 private: // implementation detail

  // Notice: better approach.
  // use parameters for compile-time recursive call.
  // you can just override for the base case, as seen for N-1 below
  template <int M>
  struct int_ {};

  template <int M>
  void Init(int_<M>) {
    Init(int_<M - 1>());
    _hashFunctions[M - 1] = &CountSketch<C, N, B>::template hash<M>;
    printf("Initializing %dth element\n", M - 1);
  }

  void Init(int_<0>) {}
};

int main() {
  int c;
  CountSketch<int, 10> cs;

  int i;
  cin >> i;

  printf("HashAll: %d", cs.HashAll(c));
  return 0;
}

Compiler Explorer

Answer 6

There are compilers that will see the loop and unroll it. But it's not part of the language specification that it must be done (and, in fact, the language specification throws all sorts of barriers in the way of doing it), and there's no guarantee that it will be done, in a particular case, even on a compiler that "knows how".

There are a few languages that explicitly do this, but they are highly specialized.

(BTW, there's no guarantee that the "unrolled" version of your initializations would be done "at compile time" in a reasonably efficient fashion. But most compilers will, when not compiling to a debug target.)