Click here to Skip to main content
15,867,305 members
Articles / Programming Languages / C++

O(1) Object Pool in C++

Rate me:
Please Sign up or sign in to vote.
4.76/5 (41 votes)
21 Apr 2014CPOL6 min read 147.8K   1.6K   83   75
A C++ memory/object pool that's always O(1) for allocations and deallocations.

Introduction

I started to write an article regarding Garbage Collection in C++ and one of my comparisons was that real garbage collected languages may be faster than C++ in some situations because they allocate memory in blocks, which makes the allocation of many small objects become extremely fast, and this doesn't happen in C++.

Well, actually we can do the same in C++ but it is not automatic, so it is up to us to use it. To do that we should use some kind of memory or object pooling.

I looked for some existing implementations and I actually didn't like them. Boost, for example, has a pool that's fast to allocate memory but that's slow to free memory if we want to control when we destroy each object. So, I decided to create my own implementation, which I am going to present here.

The Solution

This solution is made of a single template class, named ObjectPool. I can say that choosing between naming the class "object pool" and "memory pool" is a little problematic. As the solution doesn't keep a certain number of objects already initialized, we can say that it is only a memory pool, so the cost to invoke the constructor and the destructor of individual objects will continue to happen. Yet I didn't want to say it is a "memory pool", as users will request objects, not raw memory, from the pool. Maybe I should find another name that doesn't cause confusion but, for now, it is called ObjectPool.

The implementation is like this:

  • An initial amount of memory is allocated (by default, it is a block capable of holding 32 objects, aligned as a pointer [4-bytes for 32-bit computers and 8-bytes for 64-bit computers]) and there's a reference to a "first deleted" object set to NULL;
  • Each time a new object is requested the code first checks if there's a pointer for a first deleted object. If there is, then that's the address that will be used and the first pointer will point to the "next" free object (which is the content at that pointer location). If there's no deleted object that we can reuse, then we check if we still have place in our memory block. If not, a new block of memory is requested (which doubles in size, with an specific limit). In any case, we will call the constructor of the object at the address that we chose and then we will return it;
  • To delete an object, it is pretty simple. We invoke the destructor and then we will consider the object as a pointer. Such pointer will be set to point to the actual "first free" object then its address will be put as the first deleted item;
  • When we delete the pool itself, it will free the first block and, as each block frees the next one, it will end-up freeing all blocks.

So, we can summarize things like this:

  • All object allocations are O(1). Surely in some cases memory needs to be allocated, which can take some time, but the performance of such allocation is not directly affected by the number of already allocated items as we put a limit on how big the blocks can become;
  • All object destructions are O(1), as we call the destructor and simply "swap pointers";
  • It is not important how many objects we have deleted. The pool will keep all memory blocks allocated until the pool itself is deleted;
  • When we delete the pool, the memory blocks are free but the destructor of the inner items are not called, so it is up to us to delete each item before destroying the pool (if we need to call the object destructor at all).

And there are the alternative methods that actually don't initialize or destroy the objects. Those methods do all the work for "allocating" or "deallocating" an object from the pool but don't call the constructor or the destructor. This may be useful if we need to call a specific, non-default constructor or if we know that the object doesn't have a destructor (or for some reason we don't want to call it).

When is this pool useful?

  • When we have a "work" to do that allocates/deallocates many objects and we know that we can keep the memory allocated until the end of such work (most loops enter in this category);
  • When we know that we have a limited number of objects that will be in memory at the same time, yet we keep "allocating" and "deallocating" them.

Using the code

To use the code we must initialize the pool giving the initial capacity and the maximum size for the other blocks. If we don't give any parameter, the defaults of 32 (for the initial capacity) and 1 million (for the maximum block size) are used.

So, a line like the following will initialize our pool in the stack (or statically) using those defaults:

C++
ObjectPool<Test> pool;

Then, to allocate an object we do:

C++
Test *test = pool.New();

And to deallocate an object we do:

C++
pool.Delete(test);

If we don't want to use the default constructor, we can do:

C++
T *unitializedObject = pool.GetNextWithoutInitializing();

// And then we can call an appropriate constructor:
Test *test = new (uninitializedObject) Test(/*... parameters here...*/);

And if we don't want to allow the destructor to be called but we want to return the memory to the pool, we can use:

C++
pool.DeleteWithoutDestroying(test);

Obviously, we should use the appropriate class instead of Test and the appropriate variable names instead of test.

The source code of the pool is this:

C++
template<typename T>
class DefaultMemoryAllocator
{
public:
  static inline void *Allocate(size_t size)
  {
    return ::operator new(size, ::std::nothrow);
  }
  static inline void Deallocate(void *pointer, size_t size)
  {
    ::operator delete(pointer);
  }
};

template<typename T, class TMemoryAllocator=DefaultMemoryAllocator>
class ObjectPool
{
private:
  struct _Node
  {
    void *_memory;
    size_t _capacity;
    _Node *_nextNode;

    _Node(size_t capacity)
    {
      if (capacity < 1)
        throw std::invalid_argument("capacity must be at least 1.");

      _memory = TMemoryAllocator::Allocate(_itemSize * capacity);
      if (_memory == NULL)
        throw std::bad_alloc();

      _capacity = capacity;
      _nextNode = NULL;
    }
    ~_Node()
    {
      TMemoryAllocator::Deallocate(_memory, _itemSize * _capacity);
    }
  };

  void *_nodeMemory;
  T *_firstDeleted;
  size_t _countInNode;
  size_t _nodeCapacity;
  _Node _firstNode;
  _Node *_lastNode;
  size_t _maxBlockLength;

  static const size_t _itemSize;

  ObjectPool(const ObjectPool<T, TMemoryAllocator> &source);
  void operator = (const ObjectPool<T, TMemoryAllocator> &source);

  void _AllocateNewNode()
  {
    size_t size = _countInNode;
    if (size >= _maxBlockLength)
      size = _maxBlockLength;
    else
    {
      size *= 2;

      if (size < _countInNode)
        throw std::overflow_error("size became too big.");

      if (size >= _maxBlockLength)
        size = _maxBlockLength;
    }

    _Node *newNode = new _Node(size);
    _lastNode->_nextNode = newNode;
    _lastNode = newNode;
    _nodeMemory = newNode->_memory;
    _countInNode = 0;
    _nodeCapacity = size;
  }

public:
  explicit ObjectPool(size_t initialCapacity=32, size_t maxBlockLength=1000000):
    _firstDeleted(NULL),
    _countInNode(0),
    _nodeCapacity(initialCapacity),
    _firstNode(initialCapacity),
    _maxBlockLength(maxBlockLength)
  {
    if (maxBlockLength < 1)
      throw std::invalid_argument("maxBlockLength must be at least 1.");

    _nodeMemory = _firstNode._memory;
    _lastNode = &_firstNode;
  }
  ~ObjectPool()
  {
    _Node *node = _firstNode._nextNode;
    while(node)
    {
      _Node *nextNode = node->_nextNode;
      delete node;
      node = nextNode;
    }
  }

  T *New()
  {
    if (_firstDeleted)
    {
      T *result = _firstDeleted;
      _firstDeleted = *((T **)_firstDeleted);
      new(result) T();
      return result;
    }

    if (_countInNode >= _nodeCapacity)
      _AllocateNewNode();

    char *address = (char *)_nodeMemory;
    address += _countInNode * _itemSize;
    T *result = new(address) T();
    _countInNode++;
    return result;
  }

  // This method is useful if you want to call a non-default constructor.
  // It should be used like this:
  // new (pool.GetNextWithoutInitializing()) ObjectType(... parameters ...);
  T *GetNextWithoutInitializing()
  {
    if (_firstDeleted)
    {
      T *result = (T *)_firstDeleted;
      _firstDeleted = *((T **)_firstDeleted);
      return result;
    }

    if (_countInNode >= _nodeCapacity)
      _AllocateNewNode();

    char *address = (char *)_nodeMemory;
    address += _countInNode * _itemSize;
    _countInNode++;
    return (T *)address;
  }
  void Delete(T *content)
  {
    content->~T();

    *((T **)content) = _firstDeleted;
    _firstDeleted = content;
  }
  void DeleteWithoutDestroying(T *content)
  {
    *((T **)content) = _firstDeleted;
    _firstDeleted = content;
  }
};

template<typename>
const size_t ObjectPool<t,>::_itemSize = ((sizeof(T) + sizeof(void *)-1) / sizeof(void *)) * sizeof(void *);
</t,></typename>

Thread-safety

The presented code is not thread-safe but this actually makes it faster. So, if we use it in a static variable or to pass it to other threads, it is up to us to use some kind of locking.

Personally I think that we should not have a real static pool and, if needed, we should have a pool per thread. This will avoid the performance degradations caused by locking.

Sample

The sample is an application that keeps creating and deleting 100 objects 1 million times, then it shows how much time it takes to finish the job, using the pool and using normal new and delete calls.

Of course this is not a real situation, but it shows how fast the pool can be compared to normal new/delete calls. It is up to you to use it in better situations.

Version History

  • 12, April, 2014: Added a memory allocator parameter to the template, the default one uses the new/delete operators instead of malloc/free, declared the copy constructor/copy operator as private to avoid the default implementation, made the constructor explicit and changed the delete of the memory blocks to be in a while instead of being recursive to avoid excessive use of the stack;
  • 21, March, 2014: Corrected a bug (double allocation) in the constructor;
  • 19, March, 2014: Initial version.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior) Microsoft
United States United States
I started to program computers when I was 11 years old, as a hobbyist, programming in AMOS Basic and Blitz Basic for Amiga.
At 12 I had my first try with assembler, but it was too difficult at the time. Then, in the same year, I learned C and, after learning C, I was finally able to learn assembler (for Motorola 680x0).
Not sure, but probably between 12 and 13, I started to learn C++. I always programmed "in an object oriented way", but using function pointers instead of virtual methods.

At 15 I started to learn Pascal at school and to use Delphi. At 16 I started my first internship (using Delphi). At 18 I started to work professionally using C++ and since then I've developed my programming skills as a professional developer in C++ and C#, generally creating libraries that help other developers do their work easier, faster and with less errors.

Want more info or simply want to contact me?
Take a look at: http://paulozemek.azurewebsites.net/
Or e-mail me at: paulozemek@outlook.com

Codeproject MVP 2012, 2015 & 2016
Microsoft MVP 2013-2014 (in October 2014 I started working at Microsoft, so I can't be a Microsoft MVP anymore).

Comments and Discussions

 
GeneralRe: A couple of things Pin
Paulo Zemek1-Apr-14 3:36
mvaPaulo Zemek1-Apr-14 3:36 
GeneralRe: A couple of things Pin
Bill_Hallahan13-Apr-14 13:18
Bill_Hallahan13-Apr-14 13:18 
GeneralRe: A couple of things Pin
Paulo Zemek13-Apr-14 13:23
mvaPaulo Zemek13-Apr-14 13:23 
GeneralRe: A couple of things Pin
Bill_Hallahan14-Apr-14 16:40
Bill_Hallahan14-Apr-14 16:40 
GeneralRe: A couple of things Pin
Paulo Zemek14-Apr-14 16:52
mvaPaulo Zemek14-Apr-14 16:52 
GeneralRe: A couple of things Pin
Bill_Hallahan15-Apr-14 16:25
Bill_Hallahan15-Apr-14 16:25 
GeneralRe: A couple of things Pin
Paulo Zemek15-Apr-14 16:45
mvaPaulo Zemek15-Apr-14 16:45 
GeneralRe: A couple of things Pin
Bill_Hallahan15-Apr-14 17:15
Bill_Hallahan15-Apr-14 17:15 
Paulo Zemek wrote:
The sizeof(T) in the DefaultMemoryAllocator will not work with char, which is used in the example.

I don't want to put the minimum size requirement in the allocator, as it should be independent of the ObjectPool, yet the pool really requires any type to be aligned as a pointer.

The alignment always belongs in the allocator. Alignment is a property of the platform memory system, not of the type T. In any event, if you want it in the ObjectPool, it can be passed into the Allocate function, or another template parameter can be added to the DefaultMemoryAllocator for the alignment size.

For example:

C++
template<typename T>
class DefaultMemoryAllocator
{
public:
     static inline T * Allocate(size_t capacity, size_t alignment_in_bytes)
     {
         size_t size_aligned_type = sizeof(T);
         size_t mult = size_aligned_type / alignment_in_bytes;
         diff = size_aligned_type - (mult * alignment_in_bytes);
         size_aligned_type += diff;
         return (T *)::operator new(capacity * size_aligned_type, ::std::nothrow);
     }
     static inline void Deallocate(T *pointer)
     {
         ::operator delete(pointer);
     }
};


Of course, placement new, which calls malloc, will return an aligned pointer, so there is no need to worry about the first item.

But, sizeof(char) should be fine without doing any alignment. An array of char is fine, you can increment addresses by one and point to the next character. So now I do not understand what issue you are referring to. In any event, handling the size of the object in the ObjectPool class does not make sense to me - that is the exclusive domain of the allocator. Everything else in the C++ memory system is designed that way.

Perhaps there is something that I don't understand. If so, the DefaultMemoryAllocator I posted could be changed slightly to accomodate those changes without any limitation to the DefaultMemoryAllocator or the ObjectPool. Avoiding the casting has benefits I mention below, particularly avoiding the use of "void *" in the code.
Paulo Zemek wrote:
I do not do casts to (void *). I use void * to calculate the size of a pointer. And the char * is needed because I want to sum a value that may not the the size of T. Also note that in some situations I do a cast to T **. This is because a deleted item becomes "linked list" of deleted items (so, it is a pointer to the next free item).

I did not write you "cast to void *". I wrote change the "declaration" of "void *" to "T *".

Using void * has issues when storing class instances in C++. If your type uses multiple inheritance, and you can't always control that if you use third-party code, then casting to "T *" from "void *" and then trying to cast again to one of the inherited types might not do what you expect. void * should be avoided in C++ whenever possible. (There are articles about this, I'll try to find one). In this case, there is no benefit to using "void *", so why use it?
Paulo Zemek wrote:
Also, remember that how many casts this code does is not important. Changing the cast from one place to another but adding another template class is not really making things better. The important is if users will need to cast the results of the pool or not. And they don't. As I don't use variadic templates, they may require to use the emplacement new, but that's all.

As I mentioned above, C++, casting can result in bugs if casting from "void *" to a type that uses multiple inheritance.

Also, casts make code harder to read because the actual type stored is not clear throughout the code. Casts are sometimes necessary, but should be avoided.

modified 15-Apr-14 23:57pm.

GeneralRe: A couple of things Pin
Paulo Zemek15-Apr-14 17:45
mvaPaulo Zemek15-Apr-14 17:45 
GeneralRe: A couple of things Pin
Bill_Hallahan15-Apr-14 18:50
Bill_Hallahan15-Apr-14 18:50 
GeneralRe: A couple of things Pin
Paulo Zemek16-Apr-14 3:09
mvaPaulo Zemek16-Apr-14 3:09 
GeneralRe: A couple of things Pin
Bill_Hallahan16-Apr-14 15:19
Bill_Hallahan16-Apr-14 15:19 
GeneralRe: A couple of things Pin
Stefan_Lang24-Apr-14 5:06
Stefan_Lang24-Apr-14 5:06 
AnswerRe: A couple of things Pin
Paulo Zemek12-Apr-14 2:53
mvaPaulo Zemek12-Apr-14 2:53 
GeneralRe: A couple of things Pin
Florian Rappl12-Apr-14 6:16
professionalFlorian Rappl12-Apr-14 6:16 
GeneralRe: A couple of things Pin
Paulo Zemek12-Apr-14 6:39
mvaPaulo Zemek12-Apr-14 6:39 
GeneralRe: A couple of things Pin
Florian Rappl12-Apr-14 7:06
professionalFlorian Rappl12-Apr-14 7:06 
QuestionYou can find another implementation .... Pin
Stefan_Lang25-Mar-14 5:54
Stefan_Lang25-Mar-14 5:54 
GeneralMy vote of 5 Pin
Volynsky Alex23-Mar-14 10:05
professionalVolynsky Alex23-Mar-14 10:05 
GeneralRe: My vote of 5 Pin
Paulo Zemek23-Mar-14 11:02
mvaPaulo Zemek23-Mar-14 11:02 
GeneralRe: My vote of 5 Pin
Volynsky Alex23-Mar-14 13:07
professionalVolynsky Alex23-Mar-14 13:07 
QuestionThere is a bug in the code Pin
Alessandro Vergani20-Mar-14 23:16
Alessandro Vergani20-Mar-14 23:16 
AnswerRe: There is a bug in the code Pin
Paulo Zemek21-Mar-14 1:17
mvaPaulo Zemek21-Mar-14 1:17 
AnswerRe: There is a bug in the code Pin
Paulo Zemek21-Mar-14 2:45
mvaPaulo Zemek21-Mar-14 2:45 
GeneralRe: There is a bug in the code Pin
Alessandro Vergani21-Mar-14 5:56
Alessandro Vergani21-Mar-14 5:56 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.