Is it possible to avoid use of virtual method call in this case?

Question

I have a type of data that must be stored in a contiguous array which is iterated over for the purpose of updating that data. The tricky part is that I want to have the possibility to dynamically change the way any object is updated.

This is what I have come up with so far:

struct Update {
    virtual void operator()(Data & data) {}
};

struct Data {
    int a, b, c;
    Update * update;
};

struct SpecialBehavior : public Update {
    void operator()(Data & data) override { ... }
};

I would then assign every data object some type of Update. Then during update all data gets passed to its own update functor:

for (Data & data : all)
   data->update(data);

This is as far as I understand called the Strategy Pattern.

My question: is there some way to do this more efficiently? Some way to achieve the same flexibility without the cost of calling a virtual method?

Answer 1

What is the overhead of a virtual function call? Well, the implementation must do two things:

1. Load the vtable pointer from the object.
2. Load the function pointer from the vtable.

---

That is precisely two memory indirections. You can avoid exactly one of the two by placing the function pointer directly within the object (avoiding the lookup of the vtable pointer from the object), which is the approach given by ralismarks answer.

This has the downside that it only works well for a single virtual function, if you add more, you will bloat your objects with the function pointers, leading to higher pressure on your caches, and hence likely degrading performance. As long as you are just replacing a single virtual function, that's fine, add three more and you have bloated your object by 24 bytes.

---

The second memory indirection cannot be avoided unless you ensure that the compiler can derive the real type of Update at compile time. And since it seems to be the whole point of using the virtual function to perform the decision at run time, you are out of luck: Any attempt to "remove" that indirection will yield worse performance.

(I say "remove" in quotes because you can certainly avoid looking up a function pointer from memory. The price will be that you are executing something like a switch() or else if() ladder on some type identifying value loaded from the object, which will turn out to be more costly than just loading the function pointer from the object. The second solution in ralismarks answer does this explicitly, while the std::variant<> approach by Vittorio Romeo hides it within the std::variant<> template. The indirection is not really removed, it's just hidden in even slower operations.)

Answer 2

You could possibly use a function pointer instead.

struct Data;

using Update = void (*)(Data &);

void DefaultUpdate(Data & data) {};

struct Data {
    int a, b, c;
    Update update = DefaultUpdate;
};

void SpecialBehavior(Data & data) { ... };
// ...
Data a;
a.update = &SpecialBehaviour;

This avoids the cost of a virtual function, but still has the cost of a using function pointer (which is less). Since C++11, you can also use non-capturing lambdas (which are implicitly convertible to function pointers).

a.update = [](Data & data) { ... };

---

Alternatively, you can use an enum and a switch statement.

enum class UpdateType {
    Default,
    Special
};

struct Data {
    int a, b, c;
    UpdateType behavior;
};

void Update(Data & data) {
    switch(data.behavior) {
        case UpdateType::Default:
            DoThis(data);
            break;
        case UpdateType::Special:
            DoThat(data);
            break;
    }
}