A standard way to avoid virtual functions

Question

I have a library where there is a lot of small objects, which now all have virtual functions. It goes to such an extent that the size of the pointer to a virtual function table can exceed the size of the useful data in the object (it can often be just a structure with a single float in it). The objects are elements in a numerical simulation on a sparse graph, and as such cannot be easily merged / etc.

I'm not concerned as much about the cost of the virtual function call, rather about the cost of the storage. What is happening is that the pointer to the virtual function table is basically reducing the efficiency of the cache. I'm wondering if I would be better off with a type id stored as an integer, instead of the virtual function.

I cannot use static polymorphism, as all of my objects are in a single list, and I need to be able to perform operations on items, selected by an index (which is a runtime value - therefore there is no way to statically determine the type).

The question is: is there a design pattern or a common algorithm, that can dynamically call a function from an interface, given a list of types (e.g. in a typelist) and a type index?

The interface is defined and does not change much, but new objects will be declared in the future by (possibly less-skilled) users of the library and there should not be a large effort needed in doing so. Performance is paramount. Sadly, no C++11.

So far, I have perhaps a silly proof of concept:

typedef MakeTypelist(ClassA, ClassB, ClassC) TList; // list of types

enum {
    num_types = 3 // number of items in TList
};

std::vector<CommonBase*> uniform_list; // pointers to the objects
std::vector<int> type_id_list; // contains type ids in range [0, num_types)

template <class Op, class L>
class Resolver { // helper class to make a list of functions
    typedef typename L::Head T;

    // specialized call to op.Op::operator ()<T>(p)
    static void Specialize(CommonBase *p, Op op)
    {
        op(*(T*)p);
    }

    // add a new item to the list of the functions
    static void BuildList(void (**function_list)(CommonBase*, Op))
    {
        *function_list = &Specialize;
        Resolver<Op, typename L::Tail>::BuildList(function_list + 1);
    }
};

template <class Op>
class Resolver<Op, TypelistEnd> { // specialization for the end of the list
    static void BuildList(void (**function_list)(CommonBase*, Op))
    {}
};

/**
 * @param[in] i is index of item
 * @param[in] op is a STL-style function object with template operator ()
 */
template <class Op>
void Resolve(size_t i, Op op)
{
    void (*function_list[num_types])(CommonBase*, Op);
    Resolver<Op, TList>::BuildList(function_list);
    // fill the list of functions using the typelist

    (*function_list[type_id_list[i]])(uniform_list[i], op);
    // call the function
}

I have not looked into the assembly yet, but I believe that if made static, the function pointer array creation could be made virtually for free. Another alternative is to use a binary search tree generated on the typelist, which would enable inlining.

Answer 1

I ended up using the "thunk table" concept that I outlined in the question. For each operation, there is a single instance of a thunk table (which is static and is shared through a template - the compiler will therefore automatically make sure that there is only a single table instance per operation type, not per invokation). Thus my objects have no virtual functions whatsoever.

Most importantly - the speed gain from using simple function pointer instead of virtual functions is negligible (but it is not slower, either). What gains a lot of speed is implementing a decision tree and linking all the functions statically - that improved the runtime of some not very compute intensive code by about 40%.

An interesting side effect is being able to have "virtual" template functions, which is not usually possible.

One problem that I needed to solve was that all my objects needed to have some interface, as they would end up being accessed by some calls other than the functors. I devised a detached facade for that. A facade is a virtual class, declaring the interface of the objects. A detached facade is instance of this virtual class, specialized for a given class (for all in the list, operator [] returns detached facade for the type of the selected item).

class CDetachedFacade_Base {
public:
    virtual void DoStuff(BaseType *pthis) = 0;
};

template <class ObjectType>
class CDetachedFacade : public CDetachedFacade_Base {
public:
    virtual void DoStuff(BaseType *pthis)
    {
        static_cast<ObjectType>(pthis)->DoStuff();
        // statically linked, CObjectType is a final type
    }
};

class CMakeFacade {
    BaseType *pthis;
    CDetachedFacade_Base *pfacade;

public:
    CMakeFacade(BaseType *p, CDetachedFacade_Base *f)
        :pthis(p), pfacade(f)
    {}

    inline void DoStuff()
    {
        f->DoStuff(pthis);
    }
};

To use this, one needs to do:

static CDetachedFacade<CMyObject> facade;
// this is generated and stored in a templated table
// this needs to be separate to avoid having to call operator new all the time

CMyObject myobj;
myobj.DoStuff(); // statically linked

BaseType *obj = &myobj;
//obj->DoStuff(); // can't do, BaseType does not have virtual functions

CMakeFacade obj_facade(obj, &facade); // choose facade based on type id
obj_facade.DoStuff(); // calls CMyObject::DoStuff()

This allows me to use the optimized thunk table in the high performance portion of the code and still have polymorphically behaving objects to be able to conveniently handle them where performance is not required.

Answer 2

CRTP is a compile time alternative to virtual functions:

    template <class Derived> 
    struct Base
    {
        void interface()
        {
            // ...
            static_cast<Derived*>(this)->implementation();
            // ...
        }

        static void static_func()
        {
            // ...
            Derived::static_sub_func();
            // ...
        }
    };

    struct Derived : Base<Derived>
    {
        void implementation();
        static void static_sub_func();
    };

It relies on the fact that definition of the member are not instantiated till they are called. So Base should refer to any member of Derived only in the definition of its member functions, never in prototypes or data members