interface overhead

Question

I've a simple class that looks like Boost.Array. There are two template parameters T and N. One drawback of Boost.Array is, that every method that uses such an array, has to be a template with parameter N (T is OK). The consequence is that the whole program tends to be a template. One idea is to create an interface (abstract class with only pure virtual functions) that only depends on T (something like ArrayInterface). Now every other class only access the interface, and therefore needs only the template parameter T (which in contrast to N, is more or less always known). The drawback here is the overhead of the virtual call (more the missed opportunity to inline calls), if the interface is used. Until here only facts.

template<typename T>
class ArrayInterface {
public:
    virtual ~ArrayInterface() {};
    virtual T Get(int i) = 0;
};

template<typename T, int N>
class Array : ArrayInterface<T> {
public:
    T Get(int i) { ... }
};

template<typename T, int N>
class ArrayWithoutInterface {
public:
    T Get() { ... }
};

But my real problem lies somewhere else. When I extend Boost.Array with an Interface, a direct instantiation of Boost.Array gets slow (factor 4 in one case, where it matters). If I remove the interface, Boost.Array is as fast as before. I understand, if a method is called through ArrayInterface there is an overhead, that is OK. But I don't understand why the a call to a method gets slower if there is only an additional interface with only pure virtual methods and the class is called directly.

Array<int, 1000> a;
a.Get(0); // Slow

ArrayWithoutInterface<int, 1000> awi;
awi.Get(0); // Fast

GCC 4.4.3 and Clang 1.1 show the same behavior.

Answer 1

Two reasons:

• late binding is slow
• virtual methods cannot be inlined

Answer 2

This behaviour is expected: you’re invoking a virtual method. Whether you’re invoking it directly or via a base class pointer isn’t relevant at first: in both cases, the call has got to go through the virtual function table.

For a simple call such as Get (that simply dereferences an array cell, presumably without bounds checking), this can indeed make a factor 4 difference.

Now, a good compiler could see that the added indirection isn’t necessary here since the dynamic type of the object (and hence the method call target) is known at compile time. I’m mildly surprised that GCC apparently doesn’t optimize this (did you compile with -O3?). Then again, it’s only an optimization.

Answer 3

I'd disagree with your conclusion that 'the whole program tends to be a template': it looks to me like you're trying to solve a non-problem.

However, it's unclear what you mean by 'extend Boost.Array with an interface': are you modifying the source of boost::array by introducing your interface? If so, every array instance you are creating has to drag a vtable pointer along, whether or not you use the virtual methods. The existence of virtual methods may also make the compiler wary of using aggressive optimizations on non-virtual methods possible in a purely header-defined class.

Edited: ...and of course, you are using the virtual method. It takes pretty advanced code analysis techniques for the compiler to be certain a virtual call can be optimized away.

Answer 4

If you have a virtual method that never gets extended, it could be quite possible that the compiler is optimizing out the virtual part of the methods. During a normal non-virtual method call, the program flow will go directly from the caller to the method. However, when the method is marked virtual, the cpu must first jump to a virtual table, then find the method you're looking for, and then jump to that method.

Now this normally isn't too noticeable. If the method you're calling takes 100ms to execute, even if your virtual table lookup takes 1ms, it's not going to matter. But if, in the case of an array, your method takes 0.5ms to execute that 1ms performance drop is going to be quite noticeable.

There's not much you can do about it, except don't extend Boost.Array, or rename your methods so they don't override.