combinatorial explosion of compiled versions of templated function (perhaps using lambdas)

Started by
19 comments, last by Khatharr 7 years, 3 months ago

Ok c++ gurus, I have been playing with lambdas so far and have been using them basically to pass a function to a function:

e.g.


auto myfunc = [](int &i) -> void {i = i+1;};
ApplyFunction(myfunc);

///////////////////////////////////////

template <typename Func> void ApplyFunction(Func lambda_func)
{
 for (int n=0; n<10; n++)
 {
  int s=0;
  lambda_func(s);
  OutputInteger(s);
 }
}

I now want to perform something considerably more funky (excuse the pun). I want to perform several (3 or so) lambda functions on a large number of elements, however the function to be used is not known ahead of time, and in each case the function chosen is from a selection:

Here's some pseudocode:


void DoStuff(eCol enum_col_func, eBright enum_bright_func)
{

auto func_colour;
auto func_brightness;

switch (enum_col_func)
{
 case COL_RED:
  func_colour = [](int &col) -> void {col = 10;};
  break;
 case COL_BLUE:
  func_colour = [](int &col) -> void {col = 5;};
  break;
}

switch (enum_bright_func)
{
 case BRIGHT_FULL:
  func_bright = [](int &br) -> void {br = 255;};
  break;
 case BRIGHT_MED:
  func_bright = [](int &br) -> void {br = 127;};
  break;
}

IterateElements(func_colour, func_bright);
}

////////////////////////////////////////////////////
template <typename CFunc, typename BFunc> void IterateElements(CFunc fcolour, BFunc fbrightness)
{
 for (unsigned int n=0; n<10000; n++)
 {
  fcolour(m_Colour[n]);
  fbrightness(m_Brightness[n]);  
 }
}

////////////////////////////////////////////////////

Now try not to get obsessed with the minutiae (or suggesting profiling etc), as this is just an example to try and illustrate the kind of problem I am attempting to solve.

It is essentially an optimisation issue. What I want to end up with, is a array of machine code functions for all possible combinations of IterateElements (compile time) so that when the tight loop is called there are:

  1. No branches
  2. No function pointers used

So the question is can I use lambdas to force the compiler to output each combination, and what would be the correct syntax? I know I can do it using macros, but this in itself would become quite verbose, and I would prefer to use the 'modern' method.

Just for illustration, in actual use there would be:

Function 1 (10 possibilities)

Function 2 (2 possibilities)

Function 3 (2 possibilities)

Function 4 (2 possibilities)

Function 5 (2 possibilities)

Thus 10 * 2 * 2 * 2 * 2 = 160 combinations, different versions of the loop function that I'd want in the executable.

Advertisement
I'm not a wizard with recent developments in C++ code generation, so don't assume this is the final word on the subject - but I don't think you can do that, at least not as worded in the OP.

Ordinarily, if you have a template<typename X, typename Y> and want to pregenerate instances for some possible Xs and Ys, you'd use explicit template instantiation syntax.

The trouble with explicit instantiation is that you have to be able to write the names of what goes into slot X and slot Y. In the case of lambdas, lambda types can be un-utterable, i.e. you can't spell them at all in any valid way.

This means that there exist a category of lambdas (I believe any capturing closure is the right criteria but again I'm not a guru here) where you cannot pre-instantiate a template with that lambda's type.

Ordinarily you could rely on types of non-capturing lambdas, but at that point, you're literally just obscuring a set of function pointers and may as well do the simple thing instead.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

Thanks ApochPiQ. :) If there isn't a supported way of doing this I may have a look tomorrow and see if I can do similar with macros.

It's a bit annoying as it would seem to be a useful feature to be able to get the compiler to build these functions out of 'components', but maybe this is one of the few cases where there isn't a good alternative to macros.

I want to perform several (3 or so) lambda functions on a large number of elements, however the function to be used is not known ahead of time, and in each case the function chosen is from a selection:

Why? What is the end result you are trying to achieve? Why can't the functions --- or more critically, their signatures --- be known beforehand? Why must the code select between options it doesn't know? Why the restrictions on branching? Why forbidding function pointers?

In short: What is the REAL problem you are trying to solve?

http://en.cppreference.com/w/cpp/utility/functional/function

Prototypes have to match.

Withholding comments about advisability.
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

If I understand the question correctly you could use some template metaprogramming to generate all the combinations at compile time. The boost MPL (http://www.boost.org/doc/libs/1_63_0/libs/mpl/doc/index.html) has the required tools, if you are brave enough. That said...

I don't understand why you need to explicitly instantiate the template function IterateElements() before hand. Why not just call IterateElements() when you need to, with the lambda's needed supplied at the call site, and the compiler will automatically instantiate it.

I want to perform several (3 or so) lambda functions on a large number of elements, however the function to be used is not known ahead of time, and in each case the function chosen is from a selection:

Why? What is the end result you are trying to achieve? Why can't the functions --- or more critically, their signatures --- be known beforehand? Why must the code select between options it doesn't know? Why the restrictions on branching? Why forbidding function pointers?

In short: What is the REAL problem you are trying to solve?

The function signatures (I had to look up what this meant lol, function args and return values?) are known beforehand, just which particular version to use is not.

This is more a generalized question of 'how can I achieve this with c++?'. There are alternative ways of approaching the same problems of course, and the difference may not be massive, some may even be faster. But I think it is good to always expand my knowledge! :)

So my question is NOT, 'how do I write the fastest code to do such and such', it is, is there a good / best way in c++ of achieving this particular aim of getting these combinations done for me?

http://en.cppreference.com/w/cpp/utility/functional/function

Prototypes have to match.

Withholding comments about advisability.

Thanks! :) I will do some more reading into std::function, it did come up a few times when I was googling, although if I remember right there were warnings that it could degrade into a function pointer so you had to watch the assembly being output.

If I understand the question correctly you could use some template metaprogramming to generate all the combinations at compile time. The boost MPL (http://www.boost.org/doc/libs/1_63_0/libs/mpl/doc/index.html) has the required tools, if you are brave enough. That said... I don't understand why you need to explicitly instantiate the template function IterateElements() before hand. Why not just call IterateElements() when you need to, with the lambda's needed supplied at the call site, and the compiler will automatically instantiate it.

Ah yes, template metaprogramming, those chapters I always started but skipped over because they looked too much like gobbledygook, they might be just the answer! Must revisit! :)

Why not just call IterateElements() when you need to, with the lambda's needed supplied at the call site, and the compiler will automatically instantiate it.


You mean like this: ?


void DoStuff(eCol enum_col_func, eBright enum_bright_func)
{

auto func_colour_red = [](int &col) -> void {col = 10;};
auto func_colour_blue = [](int &col) -> void {col = 5;};
auto func_brightness_full = [](int &br) -> void {br = 255;};
auto func_brightness_med = [](int &br) -> void {br = 127;};


switch (enum_col_func)
{
 case COL_RED:
  {
   switch (enum_bright_func)
   {
    case BRIGHT_FULL:
     IterateElements(func_colour_red, func_brightness_full);
     break;
    case BRIGHT_MED:
     IterateElements(func_colour_red, func_brightness_med);
     break;
   }
  }
  break;
  case COL_BLUE:
  {
   switch (enum_bright_func)
   {
    case BRIGHT_FULL:
     IterateElements(func_colour_blue, func_brightness_full);
     break;
    case BRIGHT_MED:
     IterateElements(func_colour_blue, func_brightness_med);
     break;
   }
  }
  break;
}

This is pretty much what the aim is, however, with 160 combinations that's a lot of nested switch statements to type, and horrible for making changes .. which is why automation is key! :)

Variations in functionality like that tend to be better handled with a virtual function.

You might provide a function like IterateElements that the object specializes for its color. You might have RedObject, BlueObject, GreenObject, all derived from ColoredObject. ColoredObject has an IterateElements, which calls a virtual function DoColorSpecificIteration that each object implements. Then you can iterate over the collection of ColoredObjects and call the function, which will automatically dispatch to the correct function. Something like (*ColoredObjectIterator)->IterateElements() will call the object's preferred implementation.

If the objects aren't unique like that, give them an object instead that has that function. They have an object that contains a function like that. So part of the object's construction or initialization will assign it an object. You might call it ColorAttributes type. Then you can create a non-virtual function on the object that calls the function on the color attributes.

If you're just assigning two values based on those parameters you show, a simple lookup table can be short and simple. If your colors are all a basic enumeration or sequenced list, an array of colors and another array of brightness can work: int color_table[] = { 10, 5,...}; color = color_table[COL_RED]; Similarly for brightness, brightness_table[COL_RED]. If they aren't continuous or are a more varied type you might build an unordered_map that gets reused between calls. It takes a little effort to build those two tables, but using them is fast. Then instead of a giant nested switch tree you've got two direct lookups.

This topic is closed to new replies.

Advertisement