c++ switch vs. member function pointer vs. virtual inheritance

Question

I am trying to analyze the trade offs between various methods of achieving polymorphism. I need a list of objects with some similarities and some differences in member functions. The options I see are as follows:

1. have a flag in each object, and a switch statement in each function. The value of the flag directs each object to its specific section of each function.
2. have an array of member function pointers in the object, which are assigned upon construction. Then, I call that function pointer to get the correct member function.
3. have an virtual base class with several derived classes. One drawback to this is that my list will now have to contain pointers, and not the objects themselves.

My understanding is that the pointer lookups from the list in option 3 will take longer than the member function lookups of option 2 because of the guaranteed proximity of member functions.

What are some of the benefits/drawbacks of these options? My priority is performance over readability. Is there any other method for polymorphism?

Answer 1

1. have a flag in each object, and a switch statement in each function. The value of the flag directs each object to its specific section of each function

   OK, so this could make sense if very little code varies based on the flag. This minimises the amount of (duplicated) code which has to fit in cache, and avoids any function call indirection. Under some circumstances these benefits could outweigh the extra cost of the switch statement.

2. have an array of member function pointers in the object, which are assigned upon construction. Then, I call that function pointer to get the correct member function

   You save one indirection (to the vtable), but also make your objects bigger so fewer fit in cache. It's impossible to say which will dominate, so you'll just have to profile, but it isn't an obvious win

3. have an virtual base class with several derived classes. One drawback to this is that my list will now have to contain pointers, and not the objects themselves

   If the your code paths are different enough that separating them completely is reasonable, this is the cleanest solution. If you need to optimise it, you can either use a specialised allocator to ensure they're sequential (even if not sequential in your container), or move the objects directly into your container using a clever wrapper similar to Boost.Any. You'll still get the vtable indirection, but I'd prefer this to #2 unless profiling shows it's really a problem.

So, there are several questions you should answer before you can decide:

1. how much code is shared, and how much varies?
2. how big are the objects, and will a table of inline function pointers materially affect your cache miss stats?

and, after you've answered those, you should just profile anyway.

Answer 2

One way to achieve faster polymorphism is through the CRTP idiom and static polymorphism:

template<typename T>
struct base
{
    void f()
    {
         static_cast<T*>( this )->f_impl();
    }
};

struct foo : public base<foo>
{
    void f_impl()
    {
       std::cout << "foo!" << std::endl;
    }
};

struct bar : public base<bar>
{
    void f_impl()
    {
       std::cout << "bar!" << std::endl;
    }
};

struct quux : public base<quux>
{
    void f_impl()
    {
       std::cout << "quux!" << std::endl;
    }
};


template<typename T>
void call_f( const base<T>& something )
{
    something.f();
}

int main()
{
    foo my_foo;
    bar my_bar;
    quux my_quux;

    call_f( my_foo );
    call_f( my_bar );
    call_f( my_quux );
}

This outputs:

foo!
bar!
quux!

Static-polymorphism performs far better than virtual dispatch, because the compiler knows which function will be called at compile-time, and it could inline everything.

Even if it provides dynamic binding, it cannot perform polymorphism in the common heterogeneous-container way, because every instance of the base class is a different type.
However, that could be achieved with something like boost::any.