C++ automatic generation of switch statement

Question

Consider the following code

#include <iostream>

enum MyEnum{
    A,    
    B,
    END
};

template <int N>
class Trait {};

template<>
class Trait<A> {
    public:
        static int funct(int i) {return i*3;}
};

template<>
class Trait<B> {
    public:
        static int funct(int i) {return i*24;}
};


using namespace std;

int main(){
    int i = 1;
    switch(i){
        case A: cout << Trait<A>::funct(i) << endl; break;
        case B: cout << Trait<B>::funct(i) << endl; break;
    }   
} 

Which will print 24 on the screen.

Assume now that I have many more values in the enum and that I define all the corresponding template specializations of the class Trait.

To avoid writing all the code necessary in the switch statement I wrote a REPEAT macro which works almost like I want:

#include <iostream>

#define REPEAT(N, macro) REPEAT_##N(macro)
#define REPEAT_0(macro)
#define REPEAT_1(macro) REPEAT_0(macro) macro(0)
#define REPEAT_2(macro) REPEAT_1(macro) macro(1)
#define REPEAT_3(macro) REPEAT_2(macro) macro(2)
#define REPEAT_4(macro) REPEAT_3(macro) macro(3)
// etc...

// enum and class definitions

int main(){
   #define MY_MACRO(N) case N: cout << Trait<N>::funct(i) << endl; break;

   switch(i){
      REPEAT(2, MY_MACRO)
   }
}

The problem I have with this approach is that I cannot use

REPEAT(END, MY_MACRO)

because the preprocessor doesn't know about my enum.

Question: Is there a way to generate automatically the switch statement?

Notes:

• The situation where I have to use this is much more complicated and having something automated would be really helpful.
• It is important for me to use a switch statement because of the speed which can be achieved (speed is crucial for my application).

Thanks!

EDIT 1

More notes:

• It is important that the generation of the switch depends on the value of END defined in the enum.

EDIT 2/3

I decided to make an addition here to explain better my application and why I prefer some solutions to others

• In my real application the enum contains almost 50 different values and it will be extended in the future (hopefully by other people). The enum contains consecutive values.
• the class "Trait" has more than 1 member function (currently 5). Furthermore, I need to use all this in 5 different files. If I don't use an automated way of generating what I need I end up writing many times code which is basically the same.
• the member functions of Trait are used in the same way all the times.

• currently, inside my switch I have a function call which looks like this (in1, in2 and out are all double passed by reference, const for the first two cases).

  case A: Trait::funct(in1, in2, out); break;

Why do I like templates?

Consider the case Trait has 2 functions funct1 and funct2. I could define

template <int N>
class Trait {
    public:
        static int funct1(int i){static_assert(N!=N, "You forgot to define funct1");}
        static int funct2(int i){static_assert(N!=N, "You forgot to define funct2");}
};

Now, if a function definition is missing, the compiler will return a meaningful error. When other people will make additions this will be helpful.

Using the method based on C++11 features suggested by Jarod42 I can avoid maintaining long arrays of function pointers which would be error prone.

Speed tests

So far I experimented with 3 solutions but with only two member functions in Trait:

• the solution suggested by Jarod42
• a simple array of function pointers as suggested by nndru and Ali
• switch statement with the RETURN macro

The first two solutions seem to be equivalent, while the one based on the switch is 5 times faster. I used gcc version 4.6.3 with the flag -O3.

Answer 1

In C++11, you may do the following:

#if 1 // Not in C++11
#include <cstdint>

template <std::size_t ...> struct index_sequence {};

template <std::size_t I, std::size_t ...Is>
struct make_index_sequence : make_index_sequence < I - 1, I - 1, Is... > {};

template <std::size_t ... Is>
struct make_index_sequence<0, Is...> : index_sequence<Is...> {};

#endif

namespace detail {

template <std::size_t ... Is>
int funct(MyEnum e, int i, index_sequence<Is...>)
{
    // create an array of pointer on function and call the correct one.
    return std::array<int(*)(int), sizeof...(Is)>{{&Trait<MyEnum(Is)>::funct...}}[(int)e](i);
}

} // namespace detail

int funct(MyEnum e, std::size_t i)
{
    return detail::funct(e, i, make_index_sequence<std::size_t(END)>());
}

Note: enum should not have hole (so here A=0 and B=1 is ok)

Following macro may help:

#define DYN_DISPATCH(TRAIT, NAME, SIGNATURE, ENUM, ENUM_END) \
    namespace detail { \
    template <std::size_t ... Is> \
    constexpr auto NAME(ENUM e, index_sequence<Is...>) -> SIGNATURE \
    { \
        return std::array<SIGNATURE, sizeof...(Is)>{{&TRAIT<ENUM(Is)>::NAME...}}[(int)e]; \
    } \
    } /*namespace detail */ \
    template <typename...Ts> \
    auto NAME(ENUM e, Ts&&...ts) \
        -> decltype(std::declval<SIGNATURE>()(std::declval<Ts>()...)) \
    { \
        return detail::NAME(e, make_index_sequence<std::size_t(ENUM_END)>())(std::forward<Ts>(ts)...); \
    }

And then use it as:

    DYN_DISPATCH(Trait, funct, int(*)(int), MyEnum, END)

    // now `int funct(MyEnum, int)` can be call.

Answer 2

As you say, your enum is contiguous. In that case you don't need any templates or std::map or switch:

Use simply an array of function pointers and the enum as the index into the function pointer array!

#include <cassert>
#include <cstdio>

enum {
  A,
  B,
  SIZE
};

int A_funct(int i) { return 3*i; }

int B_funct(int i) { return 24*i; }

typedef int (*enum_funct)(int );

enum_funct map[] = { A_funct, B_funct };

// In C++11 use this:
//static_assert( sizeof(map)/sizeof(map[0])==SIZE , "Some enum is missing its function!");

int main() {
  assert(sizeof(map)/sizeof(map[0])==SIZE && "Some enum is missing its function!");
  int i = 1;
  std::printf("case A prints %d\n", map[A](i) );
  std::printf("case B prints %d\n", map[B](i) );
}

---

UPDATE: From your comments:

My only concern about maintainability is about writing down explicitly 5 different function pointer arrays (if I don't automate this).

OK, now I understand the maintenance concern.

I believe you can only achieve this (no matter whether you use function pointer arrays or the switch approach) if you use some sort of source code generation, either with macros or write your own source code generator. You also have to work out some naming conventions so that the function pointer arrays (or the code at the case statements in the switch approach) can be automatically generated.

Since you didn't specify it, I just made up my own naming convention. If you are comfortable with macros, here is what I hacked together with the Boost Preprocessor Library by some mindless editing of the example:

#include <boost/preprocessor/repetition.hpp>

#define ENUM_SIZE 2

#define ENUM(z, n, unused) e##n,
enum { 
  BOOST_PP_REPEAT(ENUM_SIZE, ENUM, ~)  
  SIZE
};
#undef ENUM

int fA_e0(int i) { return 3*i; }
int fA_e1(int i) { return 24*i; }

int fB_e0(int i) { return 32*i; }
int fB_e1(int i) { return  8*i; }

typedef int (*enum_funct)(int );

#define MAP(z, n, case) f ## ##case ## _e##n,

enum_funct map_A[] = {
  BOOST_PP_REPEAT(ENUM_SIZE, MAP, A)
};

enum_funct map_B[] = {
  BOOST_PP_REPEAT(ENUM_SIZE, MAP, B)
};

#undef MAP

Here is what we get after the preprocessor resolved these macros (g++ -E myfile.cpp):

enum { e0, e1, SIZE };

[...]

typedef int (*enum_funct)(int );

enum_funct map_A[] = {
  fA_e0, fA_e1,
};

enum_funct map_B[] = {
  fB_e0, fB_e1,
};

So, as you can see, if you specify your own naming conventions, you can automatically generate the maps (function pointer arrays). The documentation is good.

However, if I were you, I would write my own source code generator. I would specify a simple text file format (key - value pairs on one line, separated by white space) and write my own tool to generate the desired C++ source files from this simple text file. The build system would then invoke my source code generator tool in the pre-build step. In that way, you don't have to mess with macros. (By the way, I wrote a little testing framework for myself and to circumvent the lack of reflection in C++ I use my own source code generator. Really not that difficult.)

---

The first two solutions seem to be equivalent, while the one based on the switch is 5 times faster. I used gcc version 4.6.3 with the flag -O3.

I would have to see your source code, the generated assembly and how you measured the time in order to understand how that happened.

So I also did my own speed tests. Since it would clutter this answer, the source codes are here: switch approach and the function pointer array approach.

As I expected: the switch approach is faster but only if you have a handful of branches. Andrei Alexandrescu also says the same in his talk Writing Quick Code in C++, Quickly, at around 38 min. On my machine, the switch approach is as fast as the function pointer array approach if the enum size is 5. If the enum size is bigger than 5, the function pointer array approach is consistently faster. If the enum size is 200 and there are 10^8 function invocations, it is more than 10% faster on my machine. (The online codes have only 10^7 function invocations otherwise it times out.)

(I used link time optimization (-O3 -flto flag both to the compiler and the linker) and I can only recommend it; it gives a nice performance boost (in my codes up to 2.5x) and the only thing you need to do is to pass one extra flag. However, in your case the code was so simple that it didn't change anything. If you wish to try it: The link time optimization is either not available or only experimental in gcc 4.6.3.)

---

From your comments:

I made new experiments following step by step your benchmark method but I still get better results with the switch statement (when the enum size is 150 the switch is still almost twice as fast as than the solution with pointers). [...] In the test with my code the switch method performs always better. I run also some experiments with your code and I got the same kind of results you got.

I have looked at the generated assembly codes, having at least 5 functions (5 cases). If we have at least this many functions, roughly speaking, what happens is that the compiler turns the switch approach into the function pointer approach with one significant disadvantage. Even in the best case, the switch always goes through 1 extra branch (integer comparison potentially followed by a jump) compared to the hand-coded function pointer array approach when dispatching to the function to be called. This extra branch belongs to the default: label which is generated even if you deliberately omit it in the C++ code; there is no way to stop the compiler from generating the code for this. (If you have at most 4 cases and all 4 function calls can be inlined, then it is different; however you already have 50 cases so it doesn't matter.)

Apart from that, with the switch approach, additional (redundant) instructions and paddings are generated, corresponding to the code at the case: labels. This potentially increases your cache misses. So, as I see it, the the switch is always inferior to the function pointer approach if you have more than a handful of cases (5 cases on my machine). That is what Andrei Alexandrescu says in his talk too; he gives a limit of ~7 cases.

As for the reasons why your speedtests indicate the opposite: These sort of speed testings are always unreliable because they are extremely sensitive to alignment and caching. Nevertheless, in my primitive tests, the switch approach was always slightly worse than the function pointer array, which is in agreement with my above analysis of the assembly codes.

Another advantage of the function pointer arrays is that it can be built and changed at runtime; this is something that you don't get with the switch approach.

The weird thing is that the speed I get with the function pointer array changes depending on the enum size (I would expect it to be roughly constant).

As the enum size grows, you have more functions and the instruction cache misses are more likely to happen. In other words, the program should run slightly slower if you have more functions. (It does on my machine.) Of course the whole thing happens at random, so there will be significant deviations, don't be surprised if it runs faster for ENUM_SIZE=42 than for 41. And as mentioned earlier, alignment adds additional noise to this.

Answer 3

You don't need templates at all to do this. More like good old X macros

#define MY_ENUM_LIST VAL(A) VAL(B)

// define an enum
#define VAL(x) x,
enum MyEnum { MY_ENUM_LIST END };
#undef VAL

// define a few functions doing a switch on Enum values  

void do_something_with_Enum (MyEnum value, int i)
{
   switch (value)
   {
      #define VAL(N) case N: std::cout << Trait<N>::funct(i) << std::endl; break;
      MY_ENUM_LIST
      #undef VAL
   }
}

int do_something_else_with_Enum (MyEnum value)
{
   switch (value)
   {
      #define VAL(x) case x: yet_another_template_mayhem(x);
      MY_ENUM_LIST
      #undef VAL
   }
}

I've wasted enough time with this already. If you think templates are the solution, simply change your question to "templates experts only, preprocessor not good enough" or something.

You will not be the first wasting your time on useless templates. Many people make a fat living on providing bloated, useless solutions to inexisting problems.

Besides, your assumption of a switch being faster than an array of function pointers is highly debatable. It all depends on the number of values in your enum and the variability of the code inside your case statements.

Now if optimization is not such a big issue, you can simply use virtual methods to specialize the behaviour of whatever objects are selected by your enum and let the compiler handle the whole "automatic switch" stuff for you.

The only benefit of this approach is to avoid duplicating code if your objects are similar enough to make you think you will do a better job than the compiler handling them in a specialized way.

What you seem to be asking for is a generic solution for optimizing an unknown code pattern, and that is a contradiction in terms.

EDIT: thanks to Jarod42 for cleaning up the example.

Answer 4

It looks like you would like to associate and integer id with each function and find functions by the id.

If your id's are sequential you can have an array of function pointers indexed by that id, which would give you O(1) lookup complexity, e.g.:

typedef int Fn(int);

enum FnId {
    A,
    B,
    FNID_COUNT
};

int fn_a(int);
int fn_b(int);

Fn* const fns[FNID_COUNT] = {
    fn_a,
    fn_b
};

int main() {
    fns[A](1); // invoke function with id A.
}

If the id's are not sequential, you can still have a sorted array of {id, function_ptr} tuples and do binary search on it, O(lg(N)) lookup complexity.

None of these require macros or templates.

Answer 5

For numeric (database) type identifiers I have a template holding the identifiers. A dispatch via variadic templates calls a functor with the matching type traits:

#include <iostream>
#include <stdexcept>

// Library
// =======

class TypeIdentifier
{
    public:
    typedef unsigned Integer;

    enum Value
    {
        Unknown,
        Bool,
        Int8,
        UInt8,
        Int16,
        UInt16,
        Int32,
        UInt32,
        Int64,
        UInt64,
        Float,
        Double,
        String,
        LargeObject,
        Date,
        Time,
        DateTime
    };

    template <Value ...Ids>  struct ListType {};
    typedef ListType<
        Bool,
        Int8,
        UInt8,
        Int16,
        UInt16,
        Int32,
        UInt32,
        Int64,
        UInt64,
        Float,
        Double,
        String,
        LargeObject,
        Date,
        DateTime,
        // Always the last value:
        Unknown
    >
    List;

    public:
    TypeIdentifier(Integer value = Unknown)
    :   m_id(value)
    {}

    Integer id() const { return m_id; }

    /// Involve a functor having a member function 'Result apply<Traits>()'.
    template<typename Functor>
    typename Functor::result_type dispatch(const Functor&);

    private:
    Integer m_id;
};

template<TypeIdentifier::Value I>
struct TypeTraits
{
    static constexpr TypeIdentifier::Value Id = I;
    static constexpr bool is(TypeIdentifier::Integer id) { return (Id == id); }
    static bool is(TypeIdentifier type_identifier) { return (Id == type_identifier.id()); }

    // And conversion functions
};


namespace TypeIdentifierDispatch {

template <typename Functor, TypeIdentifier::Value I, TypeIdentifier::Value ... Ids> struct Evaluate;

template <typename Functor>
struct Evaluate<Functor, TypeIdentifier::Unknown> {
    static typename Functor::result_type
    apply(TypeIdentifier::Integer id, const Functor&) {
        throw std::logic_error("Unknown Type");
    }
};

template <typename Functor, TypeIdentifier::Value I, TypeIdentifier::Value ... Ids>
struct Evaluate {
    static typename Functor::result_type
    apply(TypeIdentifier::Integer id, const Functor& functor) {
        if(TypeTraits<I>::is(id))
            return functor.template apply<TypeTraits<I>>();
        else return Evaluate<Functor, Ids...>::apply(id, functor);
    }
};

template <typename Functor, TypeIdentifier::Value ... Ids>
inline typename Functor::result_type
evaluate(TypeIdentifier::Integer id, const Functor& functor, TypeIdentifier::ListType<Ids...>)
{
    return Evaluate<Functor, Ids...>::apply(id, functor);
}

} // namespace TypeIdentifierDispatch

template<typename Functor>
inline
typename Functor::result_type TypeIdentifier::dispatch(const Functor& functor) {
    return TypeIdentifierDispatch::evaluate(id(), functor, TypeIdentifier::List());
}



// Usage
// =====

struct Print {
    typedef void result_type;

    template <typename Traits>
    result_type apply() const {
        std::cout << "Type Identifier: " << Traits::Id << '\n';
    }
};

inline void print_identifier(unsigned value) {
    TypeIdentifier(value).dispatch(Print());
}


int main ()
{
    print_identifier(TypeIdentifier::String);
    return 0;
}

Adding a new type to the library requires adjusting TypeIdentfier and (maybe) adding a specialized TypeTraits.

Note the enum values can be arbitrary.

Answer 6

Using recursive template you can automatically generate construction equivalent to

   if (i = A)
      Trait<A>::funct(i);
   else if (i = B)
      Trait<B>::funct(i);

I think it performance is similar to switch statement. Your original example can be rewritten as below.

#include <iostream>

using namespace std;

enum MyEnum {
   A,
   B,
   END
};

template <MyEnum N>
class Trait 
{ public:
   static int funct(int i)
   { 
      cout << "You forgot to define funct" << i;
      return i; 
   } 
};

template<>
class Trait<A> {
public:
   static int funct(int i) { return i * 3; }
};

template<>
class Trait<B> {
public:
   static int funct(int i) { return i * 24; }
};

template <MyEnum idx>
int Switch(const MyEnum p, const int n)
{
   return (p == idx) ? Trait<idx>::funct(n) : Switch<(MyEnum)(idx - 1)>(p, n);
}

template <>
int Switch<(MyEnum)(0)>(const MyEnum p, const int n)
{
   return Trait<(MyEnum)(0)>::funct(n);
}

int funct(MyEnum n)
{
   return Switch<END>(n, n);
}

int main() {
   MyEnum i = B;
   cout << funct(i);
}