Optimize template replacement of a switch

Question

I have a lot of custom datatypes in one of my projects which all share a common base class.

My data (coming from a database) has a datatype which is distinguished by an enum of the base class. My architecture allows a specific datatype to be specialized with a derived class or it can be handled by the base class.

When I construct one my specific datatypes I normally call the constructor directly:

Special_Type_X a = Special_Type_X("34.34:fdfh-78");
a.getFoo();

There is some template magic which also allows constructing it like this:

Type_Helper<Base_Type::special_type_x>::Type a =  Base_Type::construct<Base_Type::special_type_x>("34.34:fdfh-78");
a.getFoo();

For some values of the type enum there might be no specialization so

Type_Helper<Base_Type::non_specialized_type_1>::Type == Base_Type

When I'm fetching data from the database the datatype isn't known at compile time so there's a third way to construct the datatypes (from a QVariant):

Base_Type a = Base_Type::construct(Base_type::whatever,"12.23@34io{3,3}");

But of course I want the correct constructor to be called, so the implementation of that method used to look like:

switch(t) {
     case Base_Type::special_type_x:  
        return Base_Type::construct<Base_Type::special_type_x>(var);

     case Base_Type::non_specialized_type_1:  
        return Base_Type::construct<Base_Type::non_specialized_type_1>(var);              

     case Base_Type::whatever:  
        return Base_Type::construct<Base_Type::whatever>(var);     

     //.....
}

This code is repetitive and since the base class can handle new types (added to the enum) as well, I came up with the following solution:

// Helper Template Method
template <Base_Type::type_enum bt_itr>
Base_Type construct_switch(const Base_Type::type_enum& bt, const QVariant& v)
{
  if(bt_itr==bt)
    return Base_Type::construct<bt_itr>(v);
  return construct_switch<(Base_Type::type_enum)(bt_itr+1)>(bt,v);
}

// Specialization for the last available (dummy type): num_types
template <>
Base_Type construct_switch<Base_Type::num_types>(const Base_Type::type_enum& bt, const QVariant&)
{
  qWarning() << "Type" << bt << "could not be constructed";
  return Base_Type(); // Creates an invalid Custom Type
}

And my original switch statement is replaced with:

return construct_switch<(Base_Type::type_enum)0>(t,var);

This solution works as expected.

The compiled code is however different. While the original switch statement had a complexity of O(1) the new approach results in a O(n) complexity. The generated code recursively calls my helper method until it finds the correct entry.

Why can't the compiler optimize this properly? Are there any better ways to solve this?

Similar problem: Replacing switch statements when interfacing between templated and non-templated code

I should mention that I would like to avoid C++11 and C++14 and stick to C++03.

Answer 1

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.

Answer 2

Are all the functions inline? I'd expect a reasonable compiler to optimize the if tree into a switch, but only if the ifs are in the same function. For portability, you might not want to rely on this.

You can get O(1) with an indirect function call by having construct_switch populate a std::vector<std::function<Base_Type(const QVariant&)>> with lambda functions that do the construction and then dispatch off that.