C++ convert variables to template arguments

Question

I would like to use templates for optimization as described here. However, with a growing number of bool template arguments, instantiating the template might have too many branches. And it gets even more branchy if you use larger enums instead of bools.

#include <iostream>
using namespace std;

template <bool b1, bool b2>
int HeavyLoop_impl(int arg)
{
    for (int i = 0; i < 10000000; i++)
    {
        // b1 is known at compile-time, so this branch will be eliminated
        if (b1) { arg += 1; }
        else    { arg += 2; }

        // b2 is known at compile-time, so this branch will be eliminated
        if (b2) { arg += 10; }
        else    { arg += 20; }
    }
    return arg;
}

// This function could be generated automatically
void HeavyLoop(bool b1, bool b2, int arg)
{
    int res;
    if (b1) {
        if (b2) { res = HeavyLoop_impl<true, true>(arg); }
        else    { res = HeavyLoop_impl<true, false>(arg); }
    } else {
        if (b2) { res = HeavyLoop_impl<false, true>(arg); }
        else    { res = HeavyLoop_impl<false, false>(arg); }
    }
    cout << "res: "<<res<<endl;
}

int main(int argc, char**argv)
{
    bool b1 = true;
    bool b2 = false;
    int arg = 0;
    HeavyLoop(b1, b2, arg);
    return 0;
}

Is there any way to automatically generate the HeavyLoop function? I would like something like this:

vars_to_template_function<bool, bool>(HeavyLoop_impl, b1, b2, arg);

Would that be possible somehow? Thanks for any hints.

Note: this is only a very simplified example. The actual loop is is of course more complicated :o)

Answer 1

I decided to have some more fun with the code, here's an improved version over my first attempt which has the following benefits:

• Supports enum types
• Explicitly specify how many parameters should be converted
• Generic implementation for the complicated part, one small helper for each function that uses it.

The code:

#include <iostream>
#include <utility>
#include <type_traits>

// an enum we would like to support
enum class tribool { FALSE, TRUE, FILE_NOT_FOUND };

// declare basic generic template
// (independent of a specific function you'd like to call)
template< template< class > class CB, std::size_t N, typename = std::tuple<> >
struct var_to_template;

// register types that should be supported
template< template< class > class CB, std::size_t N, typename... Cs >
struct var_to_template< CB, N, std::tuple< Cs... > >
{
    // bool is pretty simple, there are only two values
    template< typename R, typename... Args >
    static R impl( bool b, Args&&... args )
    {
        return b
          ? var_to_template< CB, N-1, std::tuple< Cs..., std::true_type > >::template impl< R >( std::forward< Args >( args )... )
          : var_to_template< CB, N-1, std::tuple< Cs..., std::false_type > >::template impl< R >( std::forward< Args >( args )... );
    }

    // for each enum, you need to register all its values
    template< typename R, typename... Args >
    static R impl( tribool tb, Args&&... args )
    {
        switch( tb ) {
        case tribool::FALSE:
          return var_to_template< CB, N-1, std::tuple< Cs..., std::integral_constant< tribool, tribool::FALSE > > >::template impl< R >( std::forward< Args >( args )... );
        case tribool::TRUE:
          return var_to_template< CB, N-1, std::tuple< Cs..., std::integral_constant< tribool, tribool::TRUE > > >::template impl< R >( std::forward< Args >( args )... );
        case tribool::FILE_NOT_FOUND:
          return var_to_template< CB, N-1, std::tuple< Cs..., std::integral_constant< tribool, tribool::FILE_NOT_FOUND > > >::template impl< R >( std::forward< Args >( args )... );
        }
        throw "unreachable";
    }

    // in theory you could also add int, long, ... but
    // you'd have to switch on every possible value that you want to support!
};

// terminate the recursion
template< template< class > class CB, typename... Cs >
struct var_to_template< CB, 0, std::tuple< Cs... > >
{
    template< typename R, typename... Args >
    static R impl( Args&&... args )
    {
        return CB< std::tuple< Cs... > >::template impl< R >( std::forward< Args >( args )... );
    }
};

// here's your function with the template parameters
template< bool B, tribool TB >
int HeavyLoop_impl( int arg )
{
    for( int i = 0; i < 10000000; i++ ) {
        arg += B ? 1 : 2;
        arg += ( TB == tribool::TRUE ) ? 10 : ( TB == tribool::FALSE ) ? 20 : 30;
    }
    return arg;
}

// a helper class, required once per function that you'd like to forward
template< typename > struct HeavyLoop_callback;
template< typename... Cs >
struct HeavyLoop_callback< std::tuple< Cs... > >
{
    template< typename R, typename... Args >
    static R impl( Args&&... args )
    {
        return HeavyLoop_impl< Cs::value... >( std::forward< Args >( args )... );
    }
};

// and here, everything comes together:
int HeavyLoop( bool b, tribool tb, int arg )
{
    // you provide the helper and the number of arguments
    // that should be converted to var_to_template<>
    // and you provide the return type to impl<>
    return var_to_template< HeavyLoop_callback, 2 >::impl< int >( b, tb, arg );
}

int main()
{
    bool b = true;
    tribool tb = tribool::FALSE;
    int arg = 0;
    int res = HeavyLoop( b, tb, arg );
    std::cout << "res: " << res << std::endl;
    return 0;
}

And here's a live example in case you want to play with it.

Answer 2

Here's how you can do it:

#include <iostream>
using namespace std;

template <bool b1, bool b2>
struct HeavyLoopImpl
{
    static int func(int arg)
    {
        for (int i = 0; i < 10000000; i++) {
            arg += b1 ? 1 : 2;
            arg += b2 ? 10 : 20;
        }
        return arg;
    }
};

template <template<bool...> class Impl,bool...Bs>
struct GenericJump
{
    template<typename... Args>
    static int impl(Args&&... args)
    {
        return Impl<Bs...>::func(std::forward<Args>(args)...);
    }

    template<typename... Args>
    static int impl(bool b, Args&&... args)
    {
        return b
            ? GenericJump<Impl,Bs...,true >::impl(std::forward<Args>(args)...)
            : GenericJump<Impl,Bs...,false>::impl(std::forward<Args>(args)...);
    }
};

int HeavyLoop(bool b1, bool b2, int arg)
{
    return GenericJump<HeavyLoopImpl>::impl(b1,b2,arg);
}

int main()
{
    bool b1 = true;
    bool b2 = false;
    int arg = 0;
    int res = HeavyLoop(b1, b2, arg);
    cout << "res: "<<res<<endl;
    return 0;
}

This is basically Daniels solution, but it allows you to use functions other than HeavyLoop_impl() as implementation. Only being able to call a single template function kind of defeats the purpose of being a generic solution. The GenericJump template class can call other functions also. You only have to change the HeavyLoop_impl() template function into a template class with a static function func(). It works marvellously. It compiles with gcc 4.7.3 and gives the correct output.

Answer 3

Have you considered passing a function as template argument? This way you can tailor your inner loop to your own wishes.

Function passed as template argument

However, the function call will have a small overhead.

Answer 4

The ideal generic solution really depends on what you want to vary. The possibilities for variation are:

• The number of branches, and the types of the variables being branched on.
• The operation to be performed and the number and types of its arguments.

I would recommend not making an completely generic solution unless you really need to vary all of those things. Consider only the things you want to vary and your life will be much easier.

Assuming that the total number of branches is less than 2^64, you can use a switch statement to do the dispatch. The following solution demonstrates how this could work:

template<unsigned permutation>
struct Permutation
{
    static_assert(permutation < 4, "permutation must be in the range [0, 4)");
    static const bool b1 = permutation & (1 << 0);
    static const bool b2 = permutation & (1 << 1);
};

unsigned makePermutation(bool b1, bool b2)
{
    return (b1 << 0) | (b2 << 1);
}

template<unsigned p>
int HeavyLoop_impl(int arg)
{
    return HeavyLoop_impl<Permutation<p>::b1, Permutation<p>::b2>(arg);
}

int HeavyLoop_impl(unsigned permutation, int arg)
{
    switch(permutation)
    {
    case 0: return HeavyLoop_impl<0>(arg);
    case 1: return HeavyLoop_impl<1>(arg);
    case 2: return HeavyLoop_impl<2>(arg);
    case 3: return HeavyLoop_impl<3>(arg);
    }
}

[Note: It would be trivial to use Boost.Preprocessor to generate the above switch statement.]

void HeavyLoop(bool b1, bool b2, int arg)
{
    int res = HeavyLoop_impl(makePermutation(b1, b2), arg);
    cout << "res: "<<res<<endl;
}

Answer 5

I think the best answer to your question is actually not to generate it automatically and leave it how you already have it in the question.

Making an automatic template function to generate the middle ground just obfuscates the invariant switching you're doing in the first place.

I much prefer to try to understand how the middle layer works in your question, than any of the answers people have offered for you.

I have a similar example. In my case I can apply a number of different operations between an array of values. The arrays are equal size. However I also have a structure that maps sub-ranges of the array with weight values that affect my operations. So for instance, I might be working with arrays of 100 values, and have ranges with weights like this:

[0,25] rangeWeight = 0
[26,35] rangeWeight = 0.25
[36,50] rangeWeight = 0.5
[51,99] rangeWeight = 1.0

So each operation looks something like (pseudo):

for each subrange:
    alias to the dst buffer
    alias to the src buffer
    determine the number of elements in the range
    if there's any
        weight = weightPassedIn * rangeWeight;

        Op(dst, src, weight, numElements);

For me, there were several optimizations involving whether or not the destination is touched or not (if it was still at the cleared value, some assumptions can be made to simplify the math per operation), Also if the weight happens to be full, 1.0, there are other shortcuts.

At first I was writing the same loop over and over with all of the same setup, and once I refactored all the loops around each op into functions, I pretty much naturally had the form of your invariant wrapper. There actually turned out to be several wrappers which mainly just wrap the high level operation happening inside the loop, and otherwise just handle the individual optimizations like this:

if (weight == 1.0f)
{
    if ( arrayIsCleared )
        Blend<BlendOpSet, true, false>(otherBuff, subRangesMask, 1.0f);
    else
        Blend<BlendOpAccumulate, true, false>(otherBuff, subRangesMask, 1.0f);
}
else
{
    if ( arrayIsCleared )
        Blend<BlendOpSet, false, false>(otherBuff, subRangesMask, weight);
    else
        Blend<BlendOpAccumulate, false, false>(otherBuff, subRangesMask, weight);
}

Answer 6

Here is another solution with boost::hana, which can handle also enums:

#include <cstdio>
#include <type_traits>
#include <boost/hana.hpp>

namespace hana = boost::hana;

template <typename F, typename TArgs, typename TIn, typename TOut>
void fun_arg_combinations_impl(F&& f, TArgs targs, TIn tin, TOut tout) {
    if constexpr (hana::is_empty(tin)) {
        hana::unpack(tout, f);
    } else {
        hana::for_each(hana::front(tin), [&](auto v){
            if (v == hana::front(targs)) {
                fun_arg_combinations_impl(f, hana::drop_front(targs), hana::drop_front(tin), hana::append(tout, v));
            }
        });
    }
}

template <typename F, typename TArgs, typename TIn>
void fun_arg_combinations(F&& f, TArgs targs, TIn tin) {
    fun_arg_combinations_impl(f, targs, tin, hana::tuple<>());
}

enum Shape {LINE, CIRCLE, SQUARE};

int main()
{
    auto f_heavy_loop = [](auto b1t, auto b2t, auto st) {
        constexpr bool b1 = decltype(b1t)::value;
        constexpr bool b2 = decltype(b2t)::value;
        constexpr Shape s = decltype(st )::value;

        printf("out:%d %d %d\n", b1, b2, s);
    };

    //constexpr auto bools = hana::make_tuple(std::true_type{}, std::false_type{});
    constexpr auto bools = hana::tuple<std::true_type, std::false_type>{};
    constexpr auto shapes = hana::tuple<
        std::integral_constant<Shape, LINE>,
        std::integral_constant<Shape, CIRCLE>,
        std::integral_constant<Shape, SQUARE>>{};

    // Using volatile to not allow the compiler to optimize for hard-coded values
    volatile bool b1 = true;
    volatile bool b2 = false;
    volatile Shape s = SQUARE;
    fun_arg_combinations(
        f_heavy_loop,
        hana::make_tuple(b1   , b2   , s     ),
        hana::make_tuple(bools, bools, shapes));
}

b1, b2 and s inside the f_heavy_loop() lambda are all constexpr, so we can use if constexpr on them.

output:

out:1 0 2

Have a look at the generated assembly here: https://godbolt.org/z/nsF2l5