Optimize Template Replacement of a Switch

Optimize template replacement of a switch

This is what I call the magic switch problem -- how to take a (range of) run time values and turn it into a compile time constant.

Abstractly, you want to generate this switch statement:

switch(n) {
  (case I from 0 to n-1: /* use I as a constant */)...
}

You can use parameter packs to generate code that is similar to this in C++.

I'll start with c++14-replacing boilerplate:

template<unsigned...> struct indexes {typedef indexes type;};
template<unsigned max, unsigned... is> struct make_indexes: make_indexes<max-1, max-1, is...> {};
template<unsigned... is> struct make_indexes<0, is...>:indexes<is...> {};
template<unsigned max> using make_indexes_t = typename make_indexes<max>::type;

Now we can create a compile-time sequence of unsigned integers from 0 to n-1 easily. make_indexes_t<50> expands to indexes<0,1,2,3, ... ,48, 49>. The c++14 version does so in O(1) steps, as most (all?) compilers implement std::make_index_sequence with an intrinsic. The above does it in linear (at compile time -- nothing is done at run time) recursive depth, and quadratic compile time memory. This sucks, and you can do better with work (logarithmic depth, linear memory), but do you have more than a few 100 types? If not, this is good enough.

Next, we build an array of callbacks. As I hate C legacy function pointer syntax, I'll throw in some pointless boilerplate to hide it:

template<typename T> using type = T; // pointless boilerplate that hides C style function syntax

template<unsigned... Is>
Base_Type construct_runtime_helper( indexes<Is...>, Base_Type::type_enum e, QVariant const& v ) {
  // array of pointers to functions:  (note static, so created once)
  static type< Base_Type(const QVariant&) >* const constructor_array[] = {
    (&Base_Type::construct<Is>)...
  };
  // find the eth entry, and call it:
  return constructor_array[ unsigned(e) ](v);
}
Base_Type construct_runtime_helper( Base_Type::type_enum e, QVariant const& v ) {
  return construct_runtime_helper( make_indexes_t< Base_Type::num_types >(), e, v );
}

and Bob is your Uncle^{1. An O(1) array lookup (with an O(n) setup, which in theory could be done prior to your executable launching) for dispatch.}

---

1 "Bob's your Uncle" is a British Commonwealth saying that says "and everything is finished and working" roughly.

Replacing switch statements when interfacing between templated and non-templated code

Just to expand YoungJohn's comment, it looks like this (I've included a single initialization of the operator, and it could be made simpler if there was no parameters, but if there are no parameters there is little reason to do this anyway :-P).

#include <functional>
#include <map>

////////////////////////////////////
//////specific impmenetation code
class base{public: virtual void foo() = 0;};

template <typename x>
struct derived : public base
{
    virtual void foo() {std::cout << "Ima " << typeid(x).name() << std::endl;}
};

struct my_op
{
    int some_param_; /// <shared parameter

    my_op(int some_param) : some_param_(some_param){} /// <constructor

    template<typename T>
    base* do_stuff() const
    {
        std::cout << "Use some parameter: " << some_param_ << std::endl;
        base* ret = new derived<T>();
        ret->foo();
        return ret;
    }
};

base* init_from_params(int some_param, char key)
{
    my_op op(some_param);
    using factoryFunction = std::function<base*()>;
    std::map<char, factoryFunction> mp
    {
        { 'a', std::bind(&my_op::do_stuff<int>, &op)},
        { 'b', std::bind(&my_op::do_stuff<long int>, &op)},
        { 'c', std::bind(&my_op::do_stuff<double>, &op)}
    } ;
    factoryFunction& f = mp[key];
    if (f)
    {
        return f();
    }
    return NULL;
}

int main(int argc, char** argv)
{
    volatile int parameters = 10;

    while (true)
    {
        std::cout << "Press a, b, or c" << std::endl;
        char key;
        std::cin >> key;

        base* value = init_from_params(parameters, key);

        std::cout << (void*)value << std::endl;
    }
}

Pros: so much shorter, so much more standard, so much less weird template stuff. It also doesn't require the templated arguments to all be types, we can select whatever we want to initialize the function.

Cons: In theory, it could have more overhead. In practice, I totally doubt that the overhead would ever matter.

I like it!

Optimize switch(x), x is a constant number passed as a parameter

In your demo the call f(0); in main is optimized out as you can see from the assembly for main:

main:
        mov     r0, #0
        bx      lr

The code for f(int) looks pretty optimal already to me, I think it would be less optimal to call a function instead of just issuing one assembly instruction.

Using template instead of switch

Building off Andrew's answer...

Note that the EnumSensorFamily family must be known at compile time. If it is not known until run time, then you'll have to write a switch to choose the template, putting you back where you started.

Another way to do this is with the Traits pattern:

template <EnumSensorFamily family>
struct SensorTraits;

template <>
struct SensorTraits<FAM1>
{
    const EnumSensorFamily kFamilyID = ExpectedFam1;
};

template <>
struct SensorTraits<FAM2>
{
    const EnumSensorFamily kFamilyID = ExpectedFam2;
};

template <>
struct SensorTraits<FAM3>
{
    const EnumSensorFamily kFamilyID = ExpectedFam3;
};

template <EnumSensorFamily family>
bool doTest(const StructSensorProposal& proposed)
{
  return (SensorTraits<family>::kFamilyID == proposed.Fam1SensorId);
}

If you try to use doTest with a sensor family that lacks a traits specialization, you get a compile error. Also note that you never instantiate a traits object, you just use its definitions.

This lets you reuse constants, typedefs, whatever in several functions. Additionally, adding a new family does not involve combing through all the code looking for every switch statement that cares. All you have to do is create a new SensorTraits specialization.

EDIT: You can make the field dependent on the sensor family with a pointer to member:

template <>
struct SensorTraits<FAM1>
{
    const EnumSensorFamily kFamilyID = ExpectedFam1;
    int StructSensorProposal::*proposalField = &StructSensorProposal::fam1field;
};

// ...

template <EnumSensorFamily family>
int getProposedField(const StructSensorProposal& proposed)
{
    return proposed.*SensorTraits<family>::proposalField;
}

You can also put in, say, a typedef for the sensor's data type:

template <>
struct SensorTraits<FAM1>
{
    const EnumSensorFamily kFamilyID = ExpectedFam1;
    typedef uint16_t data_type;
    data_type StructSensorProposal::*proposalField = &StructSensorProposal::fam1field;
};

// ...

template <EnumSensorFamily family>
SensorTraits<family>::data_type getProposedField(const StructSensorProposal& proposed)
{
    return proposed.*SensorTraits<family>::proposalField;
}

I haven't tested these; you might need a const or static in there.

Eliminating `switch` statements

Switch-statements are not an antipattern per se, but if you're coding object oriented you should consider if the use of a switch is better solved with polymorphism instead of using a switch statement.

With polymorphism, this:

foreach (var animal in zoo) {
    switch (typeof(animal)) {
        case "dog":
            echo animal.bark();
            break;

        case "cat":
            echo animal.meow();
            break;
    }
}

becomes this:

foreach (var animal in zoo) {
    echo animal.speak();
}

Templates and optimization of conditional branching

The C++ standard allows the C++ compiler to perform any optimization that has no observable effects. However the C++ compiler is not obligated to do so.

In your specific case, there does not seem to be any observable effects of the described optimization, and it is a fairly simple optimization. Therefore it's likely that your C++ compiler will not generate the code that will never be used. However there is no formal requirement to do so, so in order to determine whether this is the case it will be necessary to examine the compiled code with a debugger.

Whether or not the C++ compiler performs this kind of an optimization also often depends on the compilation options, too. It is also possible to force the compiler's hand and force it to avoid compiling the unneeded code. The approach depends on the C++ version. C++17's simplest solution is if constexpr. Alternatives, that work with earlier C++ versions, usually involve some refactoring and template specializations.

Switch on template argument: does gcc remove the switch?

Yes, this is optimized. There are a few things that make reading assembly easier, such as demangling names (example: _ZNK3Mdp12expectedCostILi1EEEdiiiii is the mangled form of double Mdp::expectedCost<1>(int, int, int, int, int) const), stripping comments and text (and using Intel syntax):

double expectedCost<1>(int, int, int, int, int):           # @double expectedCost<1>(int, int, int, int, int)
        jmp     expectedCost_exact(int, int, int, int, int) # TAILCALL
double expectedCost<2>(int, int, int, int, int):           # @double expectedCost<2>(int, int, int, int, int)
        jmp     expectedCost_approx(int, int, int, int, int) # TAILCALL
double expectedCost<3>(int, int, int, int, int):           # @double expectedCost<3>(int, int, int, int, int)
        jmp     expectedCost_exact(int, int, int, int, int) # TAILCALL
double expectedCost<4>(int, int, int, int, int):           # @double expectedCost<4>(int, int, int, int, int)
        jmp     expectedCost_approx(int, int, int, int, int) # TAILCALL

https://godbolt.org/z/ZtoKFH

The above site simplifies this whole process for you.

In this case I didn't provide definitions for expectedCost_approx so the compiler just leaves a jump. But in any case, compilers are definitely smart enough to realize that each template function has a constant value in the switch.

Runtime typeswitch for typelists as a switch instead of a nested if's?

You'll need the preprocessor to generate a big switch. You'll need get<> to no-op out-of-bound lookups. Check the compiler output to be sure unused cases produce no output, if you care; adjust as necessary ;v) .

Check out the Boost Preprocessor Library if you care to get good at this sort of thing…

template <typename L>
  struct type_switch
  {
    template< typename F >
      void operator()( size_t i, F& f )
      {
        switch ( i ) {
         #define CASE_N( N ) \
         case (N): return f.operator()<typename impl::get<L,N>::type>();
         CASE_N(0)
         CASE_N(1)
         CASE_N(2)
         CASE_N(3) // ad nauseam.
      }
  };

---

Related Topics