Templates across API boundaries: Implementing template generators

April 05, 2016

scross-April 05, 2016

C++ is controversial. For every discussion about it, a certain percentage of people will love it and another substantial group will hate it. Above all, one feature highlights this divide: templates. Templates have many problems: they slow compile times, force implementations to be specified in headers and can bloat generated code. However they’re also a powerful mechanism for programming against generic types.

In the first article in this series, we saw how C++ templates have significant limitations, most notably that they can’t be used across API boundaries. We also investigated a few implementations for run-time templates, but found they either didn’t work or had unacceptable costs. In this part I’ll explain how run-time templates can be implemented in an efficient way using a new technique called ‘Template Generators’.

Template Generators
It turns out the stack isn’t workable, because the stack frames can disappear before we’ve actually used the interface reference to call a method. We can’t use the heap, since it requires management overhead and is largely opaque to optimizations.

Fortunately we can use generated code to solve this problem. Template generators are functions emitted by the compiler which can be called and will return template arguments. Sounds simple, right?

OK, let’s look at this example again:

void f() {
   g<int>();
}
 
template <typename T>
void g() {
   h<T, float>();
}
 
template <typename A, typename B>
void h() { }

 

Clearly, no one function knows all of the arguments to h(). g() knows the second argument will be, but has no idea about the first argument. f() knows what it’s giving to g(), but doesn’t know anything about h().

However we can see there’s a clear stack pattern here. The top of the stack is f(), which passes its template arguments down into g(), etc. As we saw previously though, this ‘template’ stack outlives the run-time stack. Conveniently, however, this stack is unchanging.

So let’s write functions to represent this stack:

void root_template_generator(type* args) {
   args[0] = { int_vtable };
   g_template_generator(args);
}
 
void g_template_generator(type* args) {
   args[1] = { float_vtable };
   h_template_generator(args);
}
 
void h_template_generator(type* args) {
   // Nothing to do.
}

 

If you call root_template_generator() with a large enough array it’ll fill the array with the template arguments of h(). This is a start, but we need a way to get the template arguments of g() as well.

Paths
The issue we’ve hit here is that we have a tree with a root template generator, an intermediate template generator and a leaf template generator and we want to be able to specify a path through that tree that supports early exit. Fortunately we can represent the path extremely compactly via a binary string.

For example:

  • To get arguments of g(): ‘1’
  • To get arguments of h(): ‘10’

Firstly, we start every path with a ‘1’ so that we can compute the beginning of the path efficiently when it’s represented as a integer. Then at each node in the template generator tree there are a number of possible exit transitions. One of these transitions is to return immediately with the current template arguments. Other transitions would be to continue down the tree.

In this case, we have the following transitions:

  • root_template_generator() sets up arguments for the first templated function and then always calls the next intermediate generator, so no bits required for path. It does however need the initial ‘1’ for determining where the path begins.
  • g_template_generator() can either return template arguments (indicated by the path ending) or continue to h_template_generator() (represented with ‘0’).
  • h_template_generator() can only return template arguments; an unambiguous choice. Hence no bits required in the path.

So we’ll have code like the following:

void root_template_generator(type* args, path_t path) {
   args[0] = { int_vtable };
   g_template_generator(args, path, get_path_start(path));
}
 
void g_template_generator(type* args, path_t path, size_t position) {
   if (position == 0) {
       // Path end.
       return;
   }
 
   // Expecting to see a ‘0’.
   assert(((path >> (position - 1)) & 0x1) == 0x0);
 
   args[1] = { float_vtable };
   h_template_generator(args, path, position - 1);
}
 
void h_template_generator(type* args, path_t path, size_t position) {
   assert(position == 0);
   return;
}

 

If we call root_template_generator with path = ‘1’, then we’ll get the template arguments for g(). If we call it with path = ‘10’, we’ll get the arguments for h(). Excellent.

Next page >>

 

< Previous
Page 1 of 2
Next >

Loading comments...

Most Commented