3
\$\begingroup\$

I am currently implementing an object buffer, which stores all the objects used in the game at one place. All other components of the game, like the user interface, the level loader, etc, add objects to this buffer and then the objects are accessed by the rendering engine to render them all at once.

I need to store the graphics object in the object buffer contiguously in memory, so that i can take advantage of cpu caching while rendering. I also need to have stable pointers to the objects stored in the buffer as they have to be editable by their pointers by the components that created them, like the user interface must be able to access the graphics it put into the buffer in response to mouse movement with a pointer to that graphic.

These are the reasons i could not use either std::lists, which are not contiguous, or std::vectors, which invalidate all pointers when they reallocate. One data container i found useful was the std::deque, which though doesn't have complete contiguity, does allow some and keeps pointers valid, but what i wanted to ask was is

is there any other data structure out there which is better at what i want?

As far as i understand deques, they are implemented as vectors of arrays of all definite sizes. Is there a data structure that is able to allocate arrays with increasing size, like vector does?

\$\endgroup\$
  • 2
    \$\begingroup\$ you could preallocate (vector::reserve(int)) the vector \$\endgroup\$ – ratchet freak Nov 29 '14 at 19:01
  • \$\begingroup\$ besides that "take advantage of cpu caching"? sounds like you are trying to optimize prematurely, put a profiler on it and see what about rendering takes the most time and fix that \$\endgroup\$ – ratchet freak Nov 29 '14 at 19:05
  • 4
    \$\begingroup\$ its sad that "premature optimization" became a hype thing to say.. Choosing the right data structures for the job is just part of being a good engineer. cache friendliness is extremely important in game development. I second what ratcher freak advises as an optimal solution for speed, but the deque is not a bad one either! \$\endgroup\$ – Grimshaw Nov 29 '14 at 19:11
  • \$\begingroup\$ Can you describe what this data is? Vertex and index buffers or something higher order? \$\endgroup\$ – Steven Dec 1 '14 at 1:03
  • 1
    \$\begingroup\$ Can the modules that use pointers be changed to use indexes instead? Then you can use a vector and address objects by vector[index] instead of by pointer. \$\endgroup\$ – Zan Lynx Dec 2 '14 at 0:46
2
\$\begingroup\$

First, your concerns are definitely valid and this is not "premature optimization."

The problem is, std::deque::insert invalidates all iterators and references, so deque is not actually useful for this. What I did to solve this problem is create a wrapper data structure around std::vector (I called it a perma_vector) that stores a vector of std::pair<int, T>. The vector is in increasing order by integer. When you insert something, it pushes it at the end, with an integer one greater than the previous last element. This integer is wrapped in an "perma-ref" object and returned. The upshot of this is that you can pass in the "perma-ref" and look up an object in logarithmic time (via std::lower_bound). They are never invalidated unless the object itself is deleted.

Some concerns with this: You will have to put some thought into what interface you expose to maintain the data structure's invariants. You will probably have an interface similar to, but slightly smaller than, a std::vector. You will also have to write your own iterator class, (although you might be able to get around that with a two vectors instead of a vector of pairs.) Also, it might behoove you to make it easy to switch the underlying data structure. You might find that having a deque is better if you're adding or removing a lot of stuff.

PS. My code isn't that great and I'm not going to clean it up and post it unless this gets a ton of votes.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ We can help you clean up your code at CodeReview ;) \$\endgroup\$ – glampert Dec 1 '14 at 4:14
  • \$\begingroup\$ Due to missing code I may misunderstand you, but where is the benefit towards something simple like std::vector<std::shared_ptr<T>> ? \$\endgroup\$ – Tobias Wollgam Jul 13 '19 at 21:06
  • \$\begingroup\$ And one remark to the invalidation of iterators and references by std::deque::insert: if one only use push_front or push_back or insert at front or back there is no invalidation. \$\endgroup\$ – Tobias Wollgam Jul 13 '19 at 21:20
1
\$\begingroup\$

I am assuming you are using something like OpenGL for your graphics (Correct me if I am wrong about this), so a typical, minimal data structure for rendering a game object would be:

struct RenderData
{
    //Ctor
    RenderData(GameObject* p)
        :owner(p), 
         meshHandle(0), 
         numVerts(0) 
    {
        meshHandle = owner->getMesh();
        numVerts = owner->getVerts();
        transform = owner->getTransform();
        colour = owner->getColour();
    }
    // Member data
    GameObject* owner;
    unsigned int meshHandle; // This is the vertex array object (VAO) handle
    unsigned int numVerts; // Number of vertices in the mesh
    mat4 transform; // for homogeneous 3D transformations
    vec4 colour; //assumes RGBA
};

So when a new object is added to a collection of renderables, you emplace it, like so:

void addRenderable(GameObject* o)
{
    renderables.emplace_back(o);
}

Then, when you wish to render (render code ommitted):

void renderScene()
{
    for (size_t i = 0; i < renderables.size(); ++i)
    {
        renderObject(renderables[i]); //renderObject takes a const RenderData& as argument, 
        //or replace with rendering code here.
    }
}

This way, the memory in the vector is contiguous, and so the CPU can decide on the most efficient fetches from memory, reducing cache misses to a minimum.

If you need to remove a gameObject (and order is not important), then you need to ensure that the memory remains contiguous:

void remove(GameObject* p)
{
    // linear search and remove
    for (size_t i = 0; i < renderables.size(); ++i)
    {
        if (renderables[i].owner->getID()==p->getID())
        {
            renderables[i] = std::move(renderables.back());
            renderables.resize(renderables.size()-1);
            return;
        }
    }
}

Of course, this all assumes you wish to have a collection of renderables, that is persistent between frames, but you could still use this technique on a frame by frame basis, and populate the vector based on some rule/logic.

Because the struct I used in my example effectively proxy's for the actual game object, it is throwaway, so can be safely destroyed without affecting the actual gameobject, or causing memory leaks.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.