C++ object pool

Question

I am a beginner and would like to build a pool. I made some research and found out that if my software has heavy object create and delete part, I should use a pool because of performance. I made some function to get a T from the pool and reset it, and would like to know if it works correctly. I tried my implementation, but it seems a bit slow. How can i improve this? The pool allocating Ts on the stack in an array, every in-use object has a stored pointer and the free() reset the objects through the pointers. I made a function for a full reset as well. I've found out that I should use a smart pointer, but first i would like to build a simple pool from my own. As a first improvement i would like to use a placement new for the vector to avoid the use of the heap.

#include <array>
#include <vector>
#include <algorithm>
#include <iostream>

//------------------------------------------------------------------------------

template<class T,int N>
class Pool
{
public:
    Pool();

    T* get();
    void free(T* t);
    void reset();
    int available()const{ return N - used.size(); } //   number of free Ts

private:
    T default_T{};    //  reset helper
    std::array<T,N> allocated{};
    std::vector<T*> used;
};
//------------------------------------------------------------------------------

template<class T, int N>
T* Pool<T,N>::get()
//  get a T from the pool;  return 0 if no free Ts
{
    if(available()<1)
    {
        std::cerr << "Pool exhausted! Free memory!\n";
        return 0;
    }

    T* t{nullptr};
    for(unsigned int i=0; i<allocated.size(); ++i)
    {
        auto p = std::find(used.begin()+i,used.end(),&allocated[i]);
        if(p==used.end())
        {
            t = &allocated[i];
            used.push_back(t);
            return t;
        }

    }

    return t;
}

//------------------------------------------------------------------------------

template<class T,int N>
void Pool<T,N>::free(T* t)
//  return a T given out by get() to the pool and reset it to default
{
    auto p = std::find(used.begin(),used.end(),t);
    if(*p==t)
    {
        *t = default_T;
        used.erase(p);
    }
}

//------------------------------------------------------------------------------

template<class T,int N>
void Pool<T,N>::reset()
//  return ALL T given out by get() to the pool
{
    for(auto& r: allocated)
        free(&r);
}

Answer 1

First of all I recommend being very much afraid of premature optimization.

If interested see e.g. http://c2.com/cgi/wiki?PrematureOptimization

Pool might make sense for some types (usually those with very high cost of creation) and might make almost no sense at all for others. Optimization is almost always a compromise between effectiveness and complexity and I avoid unnecessary complexity like the plague. But enough of my rant.

I am not sure I understand your plan of incorporating placement new and I will comment on the current solution. Your template is general and I wouldn't try to assume any use case and my notes are going to be just as general.

int

int is most probably not the correct type in interface for neither N nor return type of available().

template<class T,int N> class Pool

int available()

Hint: What should be done if someone passes negative value?

Since you are using std::array in implementation and this template has corresponding parameter of type std::size_t you might consider that a candidate. You might also think about zero value - it might or might not make sense for your use case (that's your choice).

std::vector

In get() and free() methods you are searching for some specific element in Pool::used. std::vector is not very fast data structure for looking up elements. But if you expect N to be "kind of big" you might consider other containers from STL. Maybe std::set or std::unordered_set if you are using C++11. This unfortunately depends on your use case which I don't know.

This Q might be of interest for you:

https://stackoverflow.com/questions/6985572/which-is-the-fastest-stl-container-for-find

t in get()

I would slightly prefer eliminating local variable t from get() method as it might simplify implementation a bit. This is subjective. YMMV.

for(unsigned int i=0; i<allocated.size(); ++i)
{
    auto p = std::find(used.begin()+i,used.end(),&allocated[i]);
    if(p==used.end())
    {
        used.push_back(&allocated[i]);
        return &allocated[i];
    }

}

return nullptr;

condition in get()

Basically the condition in get() might be equivalent to

if(p != used.end())

That might be faster because you are not dereferencing the iterator p but more importantly is probably more familiar to other developers.

simplification of reset()

If I haven't overlooked anything reset() in it's current state is equivalent to

template<class T,int N>
void Pool<T,N>::reset()
//  return ALL T given out by get() to the pool
{
    allocated.clear();
}

just a thought about free()

For any object you free up you return pointer to the same default constructed instance. Once again I don't know you use case for Pool but I must admit it looks a tiny bit scary as I am worried about what would happen if client (user) of your Pool starts actually working with these pointers. This will be a shared instance through possibly many pointers which might be very difficult to work with. I would be more inclined to look for more fool proof interface and might consider storing nullptr to t or not changing it at all.

Answer 2

Overview

The first point I would make is that all the containers can be customized to use alternative allocators (like Pool allocators). So rather than write something exceedingly custom I would try and write a standard allocator that uses a pool.

The second point. C++ is highly optimized for small object creation and destruction. Unless your class is very special the standard allocators will pretty darn fast and beating them will be hard.

Design Review:

Your allocator does a linear search across the whole pool in both allocation and deallocation. To be blunt that's pretty bad and your allocation time is just going to get worse as your pool gets larger.

Also you return already constructed objects. When the objects are released they are not destroyed (so the state you get an object can be indeterminate). Most allocator systems I have seen give you some correctly aligned raw bytes and expect you to return raw bytes (ie the destructor has been called). You can't call the destructor before you return the object as the get returns an already constructed object.

Code Review

Don't write comments like this

//  get a T from the pool;  return 0 if no free Ts

I think I can see that from the name. Your comment should explain WHY not WHAT. I should be able to see that WHAT from the well written code. The problem is that code and comments can diverge over time (as bug fixes are applied) if they are describing WHAT. If you explain WHY that will usually remain the same.

What happens if I change the code to return nullptr now the comments and code are different but it still works. Does the next person change the code or the comments.

Error Codes

        // I would throw an exception
        std::cerr << "Pool exhausted! Free memory!\n";
        return 0;

Errors codes are fine within a contained class that has its own unit tests. But error codes that escape an interface boundry are a bad idea. It assumes the person using your code is as good as you and will check the error code and take appropriate action (Hint: They don't). Throw an exception. This way the code will not break if they forget to check for the error.

Complexity

This looks like an O(N^2) loop.

    T* t{nullptr};
    for(unsigned int i=0; i<allocated.size(); ++i)
    {
        auto p = std::find(used.begin()+i,used.end(),&allocated[i]);
        // STUFF
    }

Why not just a find()?
Even better why have search at all. Have a free list. Drop the head item from the free list and return it. When returning a value add it back to the head of the free list.

NOTE: I am not talking about an explicit list structure here. You can have an array of objects. And an array of index values. Then the array of free items is contains the next element in the list.

// Example of a free list.

std::array<T, N>    objects;
std::array<int, N>  freeList;
int freeListHead;

Pool()
   : freeListHead(0)
{
    for(int loop = 0; loop < N; ++loop)
    {
        freeList[loop] = loop + 1;
    }
}
T* get()
{
    T* result = &objects[freeListHead];
    freeListHead = freeList[freeListHead];
}
void put(T* obj)
{
    int offset = std::distance(&objects[0], obj);
    freeList[offset] = freeListHead;
    freeListHead = offset;
}

You assume that properties of T

You are assuming T has a copy assignment operator. In this brave new world of movable objects this is not the case.

        *t = default_T;

Complexity in reset.

void Pool<T,N>::reset()
{
    for(auto& r: allocated)
        free(&r);
}

It seems logical. But the free() contains a find(). Because you need to reset all the items you can do that first then jsut reset the container that holds the iterators then you have the same affect.

void Pool<T,N>::reset()
{
    for(auto& r: allocated)
        *r = default_T;
    allocated.reset();
}