Generating an interface without virtual functions?

Question

I'm coding a game engine and I have this class set up for objects:

class SceneManager //controls everything in the "world" game
{
    public:
        void Add(SceneObject* object); //adds to the vector
    private:
        vector<SceneObject*> _worldObjects; //the vector that contains all of them
}

And all classes I work on the game inherit from SceneObject:

class SceneObject
{
    public: 
        virtual void Draw() = 0;
}

class Image : public SceneObject
{ }
class Sprite : public SceneObject
{ }
class Model3D : public SceneObject
{ }

So I know I can call Draw() for all objects in my vector. But I've been working on optimizations and I'm trying to get rid of all inheritance and virtual functions, and use composition instead, since they can't be inlined and seems to be a major performance issue when performed on a per-object basis.

I'm looking for some C++ technique that I can use to be able to store a bunch of SceneObjects in my vector, and then call Draw() on it and it properly draws the object related to it. This will also work for the Update() function I'm using as virtual.

So this code:

void SceneManager::Add(SceneObject* object)
{
    _worldObjects.push_back(object);
}
void SceneManager::DrawTheWorld()
{
    for(unsigned int i = 0; i < _worldObjects.size(); i++)
    {
        _worldObjects[i]->Draw(); //SceneObject's being called
    }
}

...would become:

void SceneManager::Add(Image* image)
{
    SceneObject* object = new SceneObject();
    //link object to image somehow, tried to use it as a member of image
    _worldObjects.push_back(object);
}
void SceneManager::DrawTheWorld()
{
    for(unsigned int i = 0; i < _worldObjects.size(); i++)
    {
        //_worldObjects[i]->
        //I need somehow to be able to get the pointer back to the original class
        //It can be an image, sprite, model3d, anything
    }
}

I don't think if I add a switch or if/elses and removing the virtual I'd gain any performance, so I'm trying to figure if there's a clean way to deal with this.

Any ideas?

you should watch the last part of [Seasoning C++](http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning) by Sean Parent — sehe, Sep 17 '13 at 20:55
Does the call itself add that much overhead to bother about it? Have you profiled? — Luchian Grigore, Sep 17 '13 at 21:05
I suspect memory locality is more important than the virtual call overheads. For example, if you can keep the collection mostly sorted by type, and perhaps have pools of same-type objects, it could improve performance a lot - mainly because of the instruction cache and maybe some branch prediction improvements, but also because of locality of access to virtual tables and the objects. It may even make sense to move the "hottest" fields out of the objects to separate arrays. — , Sep 17 '13 at 21:06
@Steve314 this is usually true. That's why splitting out the collections by subtype is a popular suggestion — sehe, Sep 17 '13 at 21:15

sehe · Accepted Answer · 2013-09-18T07:25:23.230

You can use free functions to model the drawable aspect of your objects:

#include <iostream>

class Image { };
class Sprite { };
class Model3D { };

namespace draw_aspect
{
    void draw(Image const& image)     { std::cout << "drawing image\n";   } 
    void draw(Sprite const& sprite)   { std::cout << "drawing sprite\n";  } 
    void draw(Model3D const& model3D) { std::cout << "drawing model3D\n"; } 
}

Now, either use three separate vectors (this could well be most optimal, depending on the ordering relationship between the objects across collections?), or consider a variant type vector:

1. Using variant types

#include <boost/variant.hpp>
using SceneObject = boost::variant<Image, Sprite, Model3D>;

namespace draw_aspect {    

    struct draw_visitor : boost::static_visitor<> {
        template <typename T> void operator()(T const& t) const { draw(t); }
    };

    void draw(SceneObject const& sobj) { 
        static const draw_visitor _vis;
        boost::apply_visitor(_vis, sobj);
    }
}

A complete proof of concept of the latter: Live on Coliru

#include <vector>

class SceneManager //controls everything in the "world" game
{
    public:
        void Add(SceneObject v) { _worldObjects.emplace_back(std::move(v)); }
        friend void draw(SceneManager const& sm) { return sm.draw(); }
    private:
        void draw() const {
            for(auto& sobj : _worldObjects)
                draw_aspect::draw(sobj);
        } 
        std::vector<SceneObject> _worldObjects; //the vector that contains all of them
};

int main()
{
    SceneManager sman;

    sman.Add(Image());
    sman.Add(Sprite());
    sman.Add(Model3D());
    sman.Add(Image());

    draw(sman);
}

Outputs

drawing image
drawing sprite
drawing model3D
drawing image

2. Separate collections

The alternative using separate vectors: Live on Coliru

class SceneManager //controls everything in the "world" game
{
    public:
        void Add(Image v)   { _images  .emplace_back(std::move(v)); }
        void Add(Sprite v)  { _sprites .emplace_back(std::move(v)); }
        void Add(Model3D v) { _model3Ds.emplace_back(std::move(v)); }

        friend void draw(SceneManager const& sm) { return sm.draw(); }
    private:
        void draw() const {
            for(auto& sobj : _images)   draw_aspect::draw(sobj);
            for(auto& sobj : _sprites)  draw_aspect::draw(sobj);
            for(auto& sobj : _model3Ds) draw_aspect::draw(sobj);
        } 
        std::vector<Image> _images;
        std::vector<Sprite> _sprites;
        std::vector<Model3D> _model3Ds;
};

int main()
{
    SceneManager sman;

    sman.Add(Image());
    sman.Add(Sprite());
    sman.Add(Model3D());
    sman.Add(Image());

    draw(sman);
}

Note that the output is different (ordering):

drawing image
drawing image
drawing sprite
drawing model3D

score 1 · Answer 2 · answered Sep 18 '13 at 07:39

Solving your specific petition is one thing that others have already done.

However, I think you should take a step back and consider the whole picture. Is this a wise step to take? Any possible alternative to virtual functions will introduce maintainability problems, i.e., difficulty to modify and even to understand code.

The question is: is this really necessary? Will it really compensate?

Virtual functions involve derreferencing two pointers instead of only one. And yes, it is true it won't be inlined. I don't think, however, this being a real issue. I would indeed concentrate in algorithm-level optimization, and waste all other approaches before removing virtual funcions.

Take into account that at least one solution involves converting virtual functions to regular functions (not member functions), removing the well-known advantage of a virtual function (i.e., the class of the object itself) vs. a chain of if's.

That's said, it is your call.

Most guides for optimization when dealing with graphics do recommend the same things, and although I don't blindly follow the guidelines "because they say so", they do have a point when they mention you don't really need to if you develop a clever code design. As an example, the answers to separate by type make the code much easier to maintain and change and easier on readability for future programmers who might work on this. I think that this should be considered on a case basis like you said, but I disagree that removing it will make it harder, in this case I think it got easier overall. — Danicco, Sep 18 '13 at 18:52

score 0 · Answer 3 · answered Sep 17 '13 at 20:59

Since you seem to have a fixed number types, it seems a reasonable approach would be the use of one vector per type and applying the operations separately for each type: processing a sequence of heterogeneous objects will amount to some disruption whether it is using virtual functions are not. Putting the framework of how the respective objects are called into a function template will conveniently deal with the commonality.

Generating an interface without virtual functions?

3 Answers3

1. Using variant types

2. Separate collections

Linked