Alternatives to an Object Pool?

Question

I'm not quite sure that I need an object pool, yet it seems the most viable solution, but has some un-wanted cons associated with it. I am making a game, where entities are stored within an object pool. These entities are not allocated directly with new, instead a std::deque handles the memory for them.

This is what my object pool more or less looks like:

struct Pool
{  
    Pool()
        : _pool(DEFAULT_SIZE)
    {}

    Entity* create()
    {
        if(!_destroyedEntitiesIndicies.empty())
        {
            _nextIndex = _destroyedEntitiesIndicies.front();
            _destroyedEntitiesIndicies.pop();
        }

        Entity* entity = &_pool[_nextIndex];
        entity->id = _nextIndex;
        return entity;
    }

    void destroy(Entity* x)
    {
        _destroyedEntitiesIndicies.emplace(x->id);
        x->id = 0;
    }

private:

    std::deque<Entity> _pool;
    std::queue<int> _destroyedEntitiesIndicies;
    int _nextIndex = 0;
};

If I destroy an entity, it's ID will be added to the _destroyedEntitiesIndicies queue, which will make it so that the ID will be re-used, and lastly it's ID will be set to 0. Now the only pitfall to this is, if I destroy an entity and then immediately create a new one, the Entity that was previously destroyed will be updated to be the same entity that was just created.

i.e.

Entity* object1 = pool.create(); // create an object
pool.destroy(object1); // destroy it

Entity* object2 = pool.create(); // create another object
// now object1 will be the same as object2

std::cout << (object1 == object2) << '\n'; // this will print out 1

This doesn't seem right to me. How do I avoid this? Obviously the above will probably not happen (as I'll delay object destruction until the next frame). But this may cause some disturbance whilst saving entity states to a file, or something along those lines.

EDIT:

Let's say I did NULL entities to destroy them. What if I was able to get an Entity from the pool, or store a copy of a pointer to the actual entity? How would I NULL all the other duplicate entities when destroyed?

i.e.

Pool pool;
Entity* entity = pool.create();

Entity* theSameEntity = pool.get(entity->getId());

pool.destroy(entity);

// now entity == nullptr, but theSameEntity still points to the original entity

Answer 1

This question seems to have various parts. Let's see:

(...) If I destroy an entity and then immediately create a new one, the Entity that was previously destroyed will be updated to be the same entity that was just created. This doesn't seem right to me. How do I avoid this?

You could modify this method:

void destroy(Entity* x)
    {
        _destroyedEntitiesIndicies.emplace(x->id);
        x->id = 0;
    }

To be:

void destroy(Entity *&x)
    {
        _destroyedEntitiesIndicies.emplace(x->id);
        x->id = 0;
        x = NULL;
    }

This way, you will avoid the specific problem you are experiencing. However, it won't solve the whole problem, you can always have copies which are not going to be updated to NULL.

Another way is yo use auto_ptr<> (in C++'98, unique_ptr<> in C++-11), which guarantee that their inner pointer will be set to NULL when released. If you combine this with the overloading of operators new and delete in your Entity class (see below), you can have a quite powerful mechanism. There are some variations, such as shared_ptr<>, in the new version of the standard, C++-11, which can be also useful to you. Your specific example:

auto_ptr<Entity> object1( new Entity ); // calls pool.create()
object1.release();                      // calls pool.destroy, if needed

auto_ptr<Entity> object2( new Entity ); // create another object

// now object1 will NOT be the same as object2
std::cout << (object1.get() == object2.get()) << '\n'; // this will print out 0

You have various possible sources of information, such as the cplusplus.com, wikipedia, and a very interesting article from Herb Shutter.

Alternatives to an Object Pool?

Object pools are created in order to avoid continuous memory manipulation, which is expensive, in those situations in which the maximum number of objects is known. There are not alternatives to an object pool that I can think of for your case, I think you are trying the correct design. However, If you have a lot of creations and destructions, maybe the best approach is not an object pool. It is impossible to say without experimenting, and measuring times.

About the implementation, there are various options.

In the first place, it is not clear whether you're experiencing performance advantages by avoiding memory allocation, since you are using _destroyedEntitiesIndicies (you are anyway potentially allocating memory each time you destroy an object). You'll have to experiment with your code if this is giving you enough performance gain in contrast to plain allocation. You can try to remove _destroyedEntitiesIndicies altogether, and try to find an empty slot only when you are running out of them (_nextIndice >= DEFAULT_SIZE ). Another thing to try is discard the memory wasted in those free slots and allocate another chunk (DEFAULT_SIZE) instead.

Again, it all depends of the real use you are experiencing. The only way to find out is experimenting and measuring.

Finally, remember that you can modify class Entity in order to transparently support the object pool or not. A benefit of this is that you can experiment whether it is a really better approach or not.

class Entity {
public:
    // more things...
    void * operator new(size_t size)
    {
        return pool.create();
    }

    void operator delete(void * entity)
    {
    }

private:
    Pool pool;
};

Hope this helps.

Answer 2

If you want an Entity instance only to be reachable via create, you will have to hide the get function (which did not exist in your original code anyway :) ).

I think adding this kind of security to your game is quite a bit of an overkill but if you really need a mechanism to control access to certain parts in memory, I would consider returning something like a handle or a weak pointer instead of a raw pointer. This weak pointer would contain an index on a vector/map (that you store somewhere unreachable to anything but that weak pointer), which in turn contains the actual Entity pointer, and a small hash value indicating whether the weak pointer is still valid or not.

Here's a bit of code so you see what I mean:

struct WeakEntityPtr; // Forward declaration.
struct WeakRefIndex { unsigned int m_index; unsigned int m_hash; }; // Small helper struct.
class Entity {
    friend struct WeakEntityPtr;
private:
    static std::vector< Entity* > s_weakTable( 100 );
    static std::vector< char > s_hashTable( 100 );
    static WeakRefIndex findFreeWeakRefIndex(); // find next free index and change the hash value in the hashTable at that index
struct WeakEntityPtr {
private:
    WeakRefIndex m_refIndex;
public:
    inline Entity* get() {
        Entity* result = nullptr;

        // Check if the weak pointer is still valid by comparing the hash values.
        if ( m_refIndex.m_hash == Entity::s_hashTable[ m_refIndex.m_index ] )
        {
            result = WeakReferenced< T >::s_weakTable[ m_refIndex.m_index ];
        }

        return result;
    }
}

This is not a complete example though (you will have to take care of proper (copy) constructors, assignment operations etc etc...) but it should give you the idea what I am talking about.

However, I want to stress that I still think a simple pool is sufficient for what you are trying to do in that context. You will have to make the rest of your code to play nicely with the entities so they don't reuse objects that they're not supposed to reuse, but I think that is easier done and can be maintained more clearly than the whole handle/weak pointer story above.